Project 11

Write an assembler program Divide.asm in Hack assembly language that computes R0/R1 and R0 % R1 (that is, the result of integer division, and the remainder). You can assume without checking that 0 < R0, R1 <= 32767.

The program must keep R0 and R1 unchanged. It must store R0 / R1 in R2, and R0 % R1 in R3. It must then go into an infinite loop.

The naive algorithm for division simply subtracts R1 from R0 and increments a counter—but this is much too slow.

Instead, compute the result in rounds. Start by setting \(R2 = 0\) and \(R3 = R0\). Then, in each round, find the largest integer \(i\) such that \(R1 * 2^{i} \leq R3\). Subtract \(R1 * 2^{i}\) from \(R3\), and add \(2^i\) to the result \(R2\). The algorithm stops when \(R1 > R3\), then \(R2\) and \(R3\) are the correct answer.

Careful: It's possible that for some \(i\) you have \(R1 * 2^{i} \leq R3\), but \(R1 * 2^{i+1}\) is a negative number (because of overflow).

You can use the test script Divide.tst to check your code.

Upload Divide.asm to our submission server.