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, 2ny, 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 2ny 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
Locked
