The Word-RAM

A machine program executed instruction by instruction on a random-access machine: registers, a flat memory of w-bit words holding values in [0 .. 2w), and a program counter. Every executed instruction costs one time unit, so the cost of a run is simply the number of instructions executed. The program below sorts MEM[0..N) — but nothing in the machine knows that.

Delay 180ms
Instruction 0 / 0
Memory  ·  MEM[0], MEM[1], MEM[2], …
memory cell
cell being read
cell being written
fixed by a completed pass (smallest bubble to the front)
Registers  ·  R1, …, Rr
The machine model
  • Unlimited memory MEM[0], MEM[1], MEM[2], … and a fixed number of registers R1, …, Rr.
  • Every cell and register holds one w-bit word, i.e. a number in [0 .. 2w); arithmetic is modulo 2w. No register in this program ever has to leave that range.
  • Instructions: load and store Ri := MEM[Rj], MEM[Rj] := Ri; arithmetic and bitwise operations on registers; conditional and unconditional jumps.
  • Cost: the number of executed instructions — one time unit each.
  • Execution starts at the first program line and ends when the program counter leaves the program.
Status
Press  Step  to begin.
RAM program
The same algorithm in pseudocode
One pseudocode line corresponds to a small constant number of machine instructions — which is exactly what licenses counting pseudocode steps instead of RAM instructions.
Cost
Edit / paste the memory contents
Whitespace- or comma-separated integers; they are placed in MEM[0..N) and R1 is set to N, which is what the program's two comment lines assume. The program also assumes N ≥ 2: for N = 1 the initialisation R5 := R3 − 1 already leaves the array, and the simulator will say so rather than pretend otherwise. Since words are unsigned, a negative input is stored as 2w − |v|; try w = 8 with values beyond 255 to watch inputs wrap.