Derivation of the recursive division algorithm

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Derivation of the recursive division algorithm

cadet1620
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, 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
Reply | Threaded
Open this post in threaded view
|

Re: Derivation of the recursive division algorithm

ybakos
NICE ONE.
Reply | Threaded
Open this post in threaded view
|

Re: Derivation of the recursive division algorithm

emsoss
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
Reply | Threaded
Open this post in threaded view
|

Re: Derivation of the recursive division algorithm

cadet1620
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
Reply | Threaded
Open this post in threaded view
|

Re: Derivation of the recursive division algorithm

emsoss
It took a while. But after several mind bending attempts i finally understand it. so in a nutshell the expression x-2qy 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.