Division Algorithm

Question

I've just started with a Design Analysis and Algorithms course and we've begin with simple algorithms.

There is a division algorithm which I can't make any sense of.

function divide(x,) Input: 2 integers x and y where y>=1 Output: quotient and remainder of x divided by y

  if x=0: return (q,r)=(0,0)
   (q,r)=divide(floor (x/2), y)
   q=2q, r=2r

   if x is odd: r=r+1
   if r>=y: r=r-y, q=q+1
   return(q,r)

   * floor is lower bound

We were supposed to try this algo for 110011%101 ( binary values )...I tried something and I got a weird answer...converted into decimal values and it was wrong.

So I tried it using simple decimal values instead of binary first.

x=25, y=5

This is what I'm doing

1st: q=x,r= 12,5
2nd: q=x,r= 6,5
3rd: q=x,r= 3,5
4th: q=x,r= 1,5
5th: q=x,r= 0,5

How will this thing work? Everytime I will run it, the last value of last x will be 0(condition) it will stop and return q=0,r=0

Can someone guide me where I'm going wrong...

Thanks

Answer 1

I implemented your algorithm (with obvious correction in the arg list) in Ruby:

$ irb
irb(main):001:0> def div(x,y)
irb(main):002:1>   return [0,0] if x == 0
irb(main):003:1>   q,r = div(x >> 1, y)
irb(main):004:1>   q *= 2
irb(main):005:1>   r *= 2
irb(main):006:1>   r += 1 if x & 1 == 1
irb(main):007:1>   if r >= y
irb(main):008:2>     r -= y
irb(main):009:2>     q += 1
irb(main):010:2>   end
irb(main):011:1>   [q,r]
irb(main):012:1> end
=> nil
irb(main):013:0> div(25, 5)
=> [5, 0]
irb(main):014:0> div(25, 2)
=> [12, 1]
irb(main):015:0> div(144,12)
=> [12, 0]
irb(main):016:0> div(144,11)
=> [13, 1]

It's working, so you must not be tracking the recursion properly when you're trying to hand-trace it. I find it helpful to write the logic out on a new sheet of paper for each recursive call and place the old sheet of paper on top of a stack of prior calls. When I get to a return statement on the current sheet, wad it up, throw it away, and write the return value in place of the recursive call on the piece of paper on top of the stack. Carry through with the logic on this sheet until you get to another recursive call or a return. Keep repeating this until you run out of sheets on the stack - the return from the last piece of paper is the final answer.

Answer 2

If I remember correctly, this is one of the most basic ways of doing integral division in a simple ALU. It's nice because you can run all the recursive divisions in parallel, since each division is based on just looking at one less bit of the binary.

To understand what this does, simply walk through it on paper, as Chris Zhang suggested. Here's what divide(25,5) looks like:

(x,y)=(25,5)
    divide(12, 5)
        divide(6,5)
            divide(3,5)
                divide(1,5)
                    divide(0,5) // x = 0!
                    return(0,0)
                (q,r)=(2*0,2*0)
                x is odd, so (q,r)=(0,1)
                r < y
                return(0,1)
            (q,r)=(2*0,2*1)
            x is odd, so (q,r)=(0,3)
            r < y
            return(0,3)
        (q,r)=(2*0,2*3)
        x is even
        r >= y, so (q,r)=(1,1)
        return(1,1)
    (q,r)=(2*1,2*1)
    x is even
    r < y
    return(2,2)
(q,r)=(2*2,2*2)
x is odd, so (q,r)=(4,5)
r >= y, so (q,r)=(5,0)
return(5,0)

As you can see, it work - it gives you a q of 5 and an r of 0. The part you noticed, that you'll always eventually have a 0 term is what Chris properly calls "the base case" - the case that makes the recursive call unfold.

This algorithm works with any base number for the division and the multiplication. It uses the same principle as the following: "123 / 5 = (100 + 20 + 3) / 5 = 20 + 4 + r3 = 24r3", just done in binary.

Answer 3

The function has a recursive structure, which might be why it's a bit tricky. I'm assuming there's a typo in your function declaration where divide(x,) should be divide(x, y). Given that the desired result is x/y with the remainder, let's continue. The first line in the function definition claims that IF the numerator is 0, return 0 with a remainder of 0. This makes sense: while b != 0 and a = 0, a / b = 0 for all integers. Then we set the result to a recursive call with half the original numerator and the current denominator. At some point, "half the original numerator" turns into 0 and the base case is reached. There's a bit of computation at the end of each recursive call in what seems to be tail recursion. Because we divided by 2 on each deepning, multiply by 2 to get the original result and add 1 to the remainder if it's odd. It's hard to visualize in text alone so step through it on paper with a given problem.

Mathematically, the division algorithm (it's called that) states that the remainder must be less than or equal to 5 when you input 25,5.

The algorithm gives 0, 5. This might mean to NOT consider the remainder when the quotient is 0 or there needs to be a check on the size of the remainder.

function divide(x,) Input: 2 integers x and y where y>=1 Output: quotient and remainder of x divided by y

  if x=0: return (q,r)=(0,0)
   (q,r)=divide(floor (x/2), y)
   q=2q, r=2r

   if x is odd: r=r+1
   if r>=y: r=r-y, q=q+1
   return(q,r)

   * floor is lower bound