Addition-only variant of division algorithm

[JavaJack]

Page 251: "...the product 2 x Q x Y can be computed without any multiplication. Instead, we can rely on the value of this product in the previous recursion level..."

Can I get a hint here? During mathtest, my multiplication-using version returns 18000/6 = 3000 as expected, but my semirandom attempts at an addition-only version gives me 4095 instead of 3000, so I'm clearly doing it wrong.

[cadet1620]

I didn't see how to do it when I went through the book a couple years ago.

I just wrote a spreadsheet to show what's happening during the recursion. From this I saw a pattern that I could use. At first I thought I was going to need to return both q and 2qy from the recursive function, which is problematic in Jack. With a bit more thought I figured out how to avoid the double return values and got it working in Jack.

  x      y     q    2qy   if  ret
---------------------------------
12345      7  881  12334  F  1763
12345     14  440  12320  F   881
12345     28  220  12320  T   440
12345     56  110  12320  T   220
12345    112   55  12320  T   110
12345    224   27  12096  F    55
12345    448   13  11648  F    27
12345    896    6  10752  F    13
12345   1792    3  10752  T     6
12345   3584    1   7168  F     3
12345   7168    0      0  F     1
12345  14336    0      0  T     0

--Mark

[JavaJack]

That helped. Seems to work now, although it feels a bit kludgey (I resorted to a static for bookkeeping).