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. 
In reply to this post by cadet1620
Just about to start chapter 9, and so was reading through various posts on chapter 9 (the space invaders looks amazing, pitty we can't see the .jack rather than the .vm but hey code protection) when i came across this post.
I couldn't be bothered to go through it all by hand, go converted the program to C and used gdb to keep a track of the variables: #include <stdio.h> unsigned int divide(unsigned int x, unsigned int y) { unsigned int q; 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; } int main (int argc,char*argv[]) { printf("21/7=%d",divide(73,7)); // should be 10r3 printf("21/5=%d",divide(34,5)); // should be 6r4 printf("21/5=%d",divide(109,10)); // r should be 10r9 return 0; } I've just included the output for divide(34,5) (q is a ridiculous number because it's undefined at that point in the running) divide (x=34, y=5) at divtest.c:7 9: q = 3221221956 8: y = 5 7: x = 34 6: q = 3221221956 5: y = 5 4: x = 34 9: q = 3221221956 8: y = 5 7: x = 34 6: q = 3221221956 5: y = 5 4: x = 34 divide (x=34, y=10) at divtest.c:7 9: q = 3085252641 8: y = 10 7: x = 34 6: q = 3085252641 5: y = 10 4: x = 34 9: q = 3085252641 8: y = 10 7: x = 34 6: q = 3085252641 5: y = 10 4: x = 34 divide (x=34, y=20) at divtest.c:7 9: q = 3221221892 8: y = 20 7: x = 34 6: q = 3221221892 5: y = 20 4: x = 34 9: q = 3221221892 8: y = 20 7: x = 34 6: q = 3221221892 5: y = 20 4: x = 34 divide (x=34, y=40) at divtest.c:7 9: q = 3087006448 8: y = 40 7: x = 34 6: q = 3087006448 5: y = 40 4: x = 34 9: q = 3087006448 8: y = 40 7: x = 34 6: q = 3087006448 5: y = 40 4: x = 34 9: q = 0 8: y = 40 7: x = 34 6: q = 0 5: y = 40 4: x = 34 9: q = 0 8: y = 40 7: x = 34 6: q = 0 5: y = 40 4: x = 34 9: q = 0 8: y = 20 7: x = 34 6: q = 0 5: y = 20 4: x = 34 9: q = 0 8: y = 20 7: x = 34 6: q = 0 5: y = 20 4: x = 34 9: q = 1 8: y = 20 7: x = 34 6: q = 1 5: y = 20 4: x = 34 9: q = 1 8: y = 20 7: x = 34 6: q = 1 5: y = 20 4: x = 34 9: q = 1 8: y = 10 7: x = 34 6: q = 1 5: y = 10 4: x = 34 9: q = 1 8: y = 10 7: x = 34 6: q = 1 5: y = 10 4: x = 34 9: q = 3 8: y = 10 7: x = 34 6: q = 3 5: y = 10 4: x = 34 9: q = 3 8: y = 10 7: x = 34 6: q = 3 5: y = 10 4: x = 34 9: q = 3 8: y = 5 7: x = 34 6: q = 3 5: y = 5 4: x = 34 9: q = 6 8: y = 5 7: x = 34 6: q = 6 5: y = 5 4: x = 34 9: q = 6 8: y = 5 7: x = 34 6: q = 6 5: y = 5 4: x = 34 main (argc=1, argv=0xbffff324) at divtest.c:24 At no point is any variable q,x or y 4 which should be the reminder.. What am i missing ? I tried making q global, because maybe there was something to do with C being strongly typed and jack not, and maybe something was being lost in a some subtlety of jack I didn't know about, but no effect.. The remainder seems to get a bit lost ish in the description (of the OP) about solution 3.. And how is that all more efficient than just: remainder = dividend  (result * divisor). (Only 1 multiplication (and a minus)) People who have much more experience than me seem to think this is marvellous, but I can't get it to give the desired result. The function gives the correct result, but NOT the remainder. To be fair maybe this does work in jack, (it's taken me an hour or two to get to this point) I'll try it in jack (which would be a proper test and see what happens), but I don't know jack yet ! (Don't look too hard ;) ) Anyway any help much appreciated with my error in understanding. Thank you. Regards 
Free forum by Nabble  Edit this page 