Classic binary division algorithm 67 / 5 = 13 R 2
1) Align MSB of divisor (y) with dividend (x), count required shifts (n).
x 01000011
y 00000101 n 0
00001010 1
00010100 2
00101000 3
01010000 4
2) Repeated conditional subtraction, N+1 times.
01000011
1010000 q 0 (MSB)
1000011
101000 1
11011
10100 1
0111
1010 0
0111
101 1
10
This is hard to implement in Jack because there is no easy way to right shift the divisor after conditional subtraction.
Solution 1:
Notice that all of the shifted divisor values that are needed during the conditional subtraction were available
during the left shifting that was done to align the MSBs. These values, 2^{n}y, can be cached in an array during the alignment loop so they can be used in the subtraction loop.
/**
* Compute x / y using the classic division algorithm
* using an array to cache y * 2^n values.
*/
unsigned int div1(unsigned int x, unsigned int y)
n = 0
while y <= x
y2n[n] = y
y = y * 2
n = n + 1
q = 0
while n > 0
q = q * 2
n = n  1
if y2n[n] <= x
x = x  y2n[n]
q = q + 1
return q // Remainder in x if needed.
Solution 2:
 The 2^{n}y values are stored into the array in increasing order in the top half of div1() and used (and discarded) in decreasing order in the lower half of the program.
 y is not used in the lower half.
 The lower half always loops exactly the same number of times as the upper half.
 The initialization, q = 0, can be done when the upper while breaks, instead of before starting the lower while loop. (Sometimes a blank line can have semantic content!)
These facts allow div1() to be reformulated into a recursive algorithm. The computations in the upper while loop will be done on the way down the recursion. Computing the q bits will be done on the way back up.
There is a bit of bother because x is changing in the lower loop. The recursive function needs to return q and x.
/**
* Recursively compute x / y using the classic division
* algorithm using the stack to cache y * 2^n values.
*
* Because the x value (partial remainder) is changing in the lower
* loop of div1(), it must also be returned from the recursive call.
*/
(unsigned int, unsigned int) div2(unsigned int x, unsigned int y)
if y > x
q = 0
return (q, x)
(q, x) = div2(x, y * 2)
q = q * 2
if y <= x
x = x  y
q = q + 1
return (q, x) // Outermost call returns remainder in x.
Solution 3:
In most programming languages, it is not convenient to return two values from a function.
Fortunately, the remainder (new x value) can always be computed from the current x value, the y value passed into the recursive call and q value returned by the recursive call.
x′ = x  q 2y.
This is significantly less efficient than div2() because reconstructing x requires multiplication.
/**
* Recursively compute x / y using the classic division
* algorithm using the stack to cache y * 2^n values.
*
* This version eliminates the need for returning the partial
* remainder by recomputing it after the recursive call. This
* is less efficient because this recomputation requires a
* multiplication.
*/
unsigned int div3(unsigned int x, unsigned int y)
if y > x
q = 0
return q
q = div3(x, y * 2)
x = x  q * y * 2
q = q * 2
if y <= x
q = q + 1
return q
The Nand2Tetris Algorithm

Move the q = q * 2 into the following if , adding an else clause.

Swap the sense of the if test and the if and else clauses.

Do a bit of simple algebra to combine the x = x  ... and the if test.
And that's the Nand2Tetris divide() algorithm.
unsigned int divide(unsigned int x, unsigned int y)
if y > x
q = 0
return q
q = divide(x, y * 2)
if x  q * y * 2 < y
q = q * 2
else
q = q * 2 + 1
return q