A random-access machine (RAM) program that reads a whole number below 10000 and writes its digits in reverse order, so 2563 becomes 3652. Built for the TZIV course (project RAM) at FIIT STU in the 2022/23 summer semester.
Finished and archived. The report works out the unit and logarithmic time cost of every instruction.
- Reads the number N into register R1 with a single
readand rejects it if N ≥ 10000 - Splits off the last digit (R1 − ⌊R1 / 10⌋ · 10) and stores it through the pointer in R3, filling R5, R6, … until R1 reaches 0
- Writes the stored digits to the output tape from R5 upwards through a second pointer in R4, which gives the reversed number
- 32 instructions in ram.ram, no subroutines: one loop to split the digits, one to write them
flowchart TD
A["Read N into R1"] --> B{"N ≥ 10000?"}
B -->|yes| R["Reject"]
B -->|no| C{"R1 = 0?"}
C -->|no| D["Store the last digit of R1 in the register R3 points to"]
D --> E["R1 = ⌊R1 / 10⌋, R3 + 1"]
E --> C
C -->|yes| F["Write the register R4 points to, R4 + 1"]
F --> G{"R3 − R4 > 0?"}
G -->|yes| F
G -->|no| H["Halt"]
From the report and timeComplexity.xlsx, with n the number of digits:
| Measure | Result |
|---|---|
| Time, unit cost | 23n + 10 steps, O(n) |
| One digit / four digits | 32 / 101 steps (report summary, 23n + 9) |
| N ≥ 10000 | rejected after 8 steps |
| Space | 5 + ⌊log₁₀ N⌋ registers, O(log N) |
The summary line in the report and its per-instruction table differ by one step (23n + 9 against 23n + 10). The logarithmic cost of each instruction is in the same table.
Load ram.ram into SimStudio, put a number on the input tape and run it. With 2563 on the input, the output tape reads 3652.
SimStudio RAM program (ram.ram). Cost tables in Excel, report in Word.
- documentation.pdf: project report with the cost of every instruction (Slovak); documentation.docx is its source
- Opačný ciferný zápis.md: the assignment (Slovak)
- timeComplexity.xlsx: unit and logarithmic cost per instruction
- Artur_Kozubov_randomAccessMachine.zip: the submitted archive (report,
ram.ram, cost table)
CC BY-NC-ND 4.0: share it with credit, but no changes and no commercial use. Don't hand it in as your own coursework.
