An Accumulator Only w Bits Wide
A machine has one accumulator that is exactly w bits wide and signed, so it
holds a value in the range -2^(w-1) to 2^(w-1) - 1 and nothing else. After
every operation the result is reduced into that range the way two's complement
hardware does it:
reduce(v, w) = ((v + 2^(w-1)) mod 2^w) - 2^(w-1)
The program has n instructions numbered from 0, and the counter and the
accumulator both start at 0.
ADD v accumulator = reduce(accumulator + v, w), counter on by 1
MUL v accumulator = reduce(accumulator * v, w), counter on by 1
JNZ v if the accumulator is not 0, counter on by v, otherwise by 1
HLT stop
The machine performs at most s steps, and one step is: if the counter is
outside 0 to n - 1, stop and report FAULT; otherwise execute the
instruction there. Print the outcome word, one of HALT, FAULT or
RUNNING, then the accumulator, separated by a single space.
``` w = 8, so the range is -128 to 127: ADD 100 / ADD 100 / HLT
0 + 100 is 100, which is in range. 100 + 100 is 200, which is not: 200 - 256 is -56. -> HALT -56 ```
``` w = 16, so the range is -32768 to 32767: ADD 32767 / ADD 1 / HLT
32767 is the largest value the register holds, and one more wraps to the smallest. -> HALT -32768 ```
## What most people try first
A mask and a sign test: keep the low w bits, and if the top of those w bits
is set, subtract 2^w. That is correct and it is how real hardware does it.
The trap is doing it with a bitwise operator in a language where bitwise
operators have their own width. In JavaScript every bitwise operator truncates
to 32 bits, so 1 << 59 is 134217728 and masking a large product is wrong
before the wrap is even applied. The formula in the statement avoids the
question entirely, because mod and subtraction have no width of their own.
The second instinct is to let the machine's own integers do the wrapping by
declaring the accumulator as a 32 bit type. That only ever works when w is
32, and w can be as small as 2.
## Why the formula is the same as truncation
Write h = 2^(w-1). Adding h shifts the target range [-h, h-1] to
[0, 2^w - 1], which is exactly the set of residues modulo 2^w. So
(v + h) mod 2^w is the unique representative of v + h in that set, and
subtracting h carries it back. Two values reduce to the same result exactly
when they differ by a multiple of 2^w, which is the defining property of
truncation to w bits, and the result always lands in the signed range
because the residue is between 0 and 2^w - 1.
## Overflow, and why there is none to find here
This is a problem about a narrow register, so it is worth being exact about the
wide one. The accumulator is always within -2^31 to 2^31 - 1, and v is at
most 10^4 in magnitude, so an intermediate product is at most about
2 * 10^13. That does not fit in 32 bits, so the intermediate must be computed
in a 64 bit type: signed overflow is undefined behaviour in C and C++, not a
defined wrap, so a 32 bit intermediate is a bug there whatever it happens to
print.
But no input in the constraint range can make a 32 bit build give a DIFFERENT
answer. The specified reduction is modulo 2^w with w at most 32, and a 32
bit build reduces modulo 2^32 first. Since 2^w divides 2^32, reducing
modulo 2^32 and then modulo 2^w gives the same residue as reducing modulo
2^w alone. The two agree at every step, for every width. That claim was
checked against 4000 random programs across widths 2, 3, 4, 8, 16, 31 and 32,
and nothing differed. So no test here is tagged as an overflow, because tagging
one would tell a student their broken code is correct.
## Cost
O(n + s) time and O(n) memory.