Binary long division algorithm

Question

I have been trying to recreate the following algorithm in java:

Set quotient to 0
Align leftmost digits in dividend and divisor
Repeat
If that portion of the dividend above the divisor is greater than or equal to the divisor
Then subtract divisor from that portion of the dividend and
Concatentate 1 to the right hand end of the quotient
Else concatentate 0 to the right hand end of the quotient
Shift the divisor one place right
Until dividend is less than the divisor
quotient is correct, dividend is remainder
STOP

This can also be found here:

Here is my code:

public class Division {
    public static void main(String[] args) {
        int quotient =0;
        int a = 123;
        int b = 5;
        int bfirst = b;
        String a1 = Integer.toBinaryString(a);
        String b1 = Integer.toBinaryString(b);
        int aLength = a1.length();
        int bLength = b1.length();
        int power = aLength - bLength;
        b =(int) Math.pow(b, power);    

        while(a > bfirst) {
            if(a >= b) {
                a = a-b;
                quotient = quotient*2+1;
                b = b/2;
            } else {
                quotient = quotient*2;
                b = b/2;
            }
        }
        System.out.println(quotient);
    }
}

It sometimes returns answers which are right, but other times will not. Any ideas?

Solution 1

I believe

b = (int) Math.pow(b, power);    

should be

b = (int) (b * Math.pow(2, power));

The variable b appears to be the current digit to be compared with, and got subtracted by a. You are doing binary division, and in the code following this line I found this value were only divided by 2. In this case, Math.pow(b, power) does not make sense.

---

Furthermore, there is a missing step. Because a - b will bring all the values down to the end and get a < bFirst, all ending zeroes are not counted into quotient, as we have already exited the loop.

Replace

a = a-b;
quotient = quotient*2+1;
b = b/2;

with

bLength = Integer.toBinaryString(b).length();
int bfirstLength = Integer.toBinaryString(bfirst).length();
a = a-b;
quotient = quotient*2+1;
b = b/2;
if (a < bfirst) {
    quotient = quotient * (int)Math.pow(2, bLength - bfirstLength);
}

To account for missing zeroes of the quotient.

---

Furthermore there is an Off-by-one-error.

while (a > bfirst) {

should be

while (a >= bfirst) {

If a is divisible by b, long division should go ahead and subtract the remaining dividend, instead of stopping the procedure.

---

Finally, number of binary digits in a number can be computed by

(int) (Math.ln(a) / Math.ln(2)) + 1

---

Last, try to make use of System.out.println inside your algorithm when debugging, it helps a lot and let you precisely know where your algorithm goes wrong. Better, if you know how and is available (usually integrated into IDEs), use a debugger.

And, the last one, do the algorithm by hand with some examples before coding - this can definitely help you understand how the algorithm works.

The entire thing, with debug statements: http://ideone.com/JBzHdf

Solution 2

Your algorithm isn't quite correct. It will fail if the quotient has trailing zeros because the loop stops before it has appended them. A correct algorithm is:

let q = 0
shift divisor left until divisor > dividend (k bits)
while k > 0
  k = k - 1
  divisor = divisor >> 1
  if dividend >= divisor
     q = (q << 1) + 1
     dividend = dividend - sd
  else
     q = q << 1
return q

You should really use integers (type long in fact) and the shift operators << and >>. They make this much easier (not to mention faster) then the string operations.

Since an answer is already accepted, here is Java for the algorithm above in case of interest.

public static long div(long dividend, long divisor) {
    long quotient = 0;
    int k = 0;
    while (divisor <= dividend && divisor > 0) {
        divisor <<= 1;
        k++;
    }
    while (k-- > 0) {
        divisor >>= 1;
        if (divisor <= dividend) {
            dividend -= divisor;
            quotient = (quotient << 1) + 1;
        }
        else quotient <<= 1;
    }
    return quotient;
}