Administrator

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:
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. 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
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 
NICE ONE.

hello Mark,
you lost me on the repeated conditional subtraction on the second row. where you wrote: 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 is this a subtraction? if so shouldn't the answer be 01011 instead of 11011. Thank you 
Administrator

Yes, it's subtraction. The conditional subtraction step is to subtract if it won't underflow, otherwise copy down the original value.
There are likely other typos, especially spelling and grammar, do please report them. This one's OK, however. 1000011 = 67  101000 = 40  11011 = 27 Mark 
It took a while. But after several mind bending attempts i finally understand it. so in a nutshell the expression x2qy is how one can compute the remaining x after successive subtractions. if it is greater than y, it means y can be subtracted from x again. if not, than return twice the quotient q.
Thank you Mark. 
Free forum by Nabble  Edit this page 