Make delicious recipes!

Efficient Division



Problem: Without using divide operator, write a function to divide two integers.


Solution: A naive division implementation would be subtracting in a while loop and returning the number of loopCounts.


static int divide (int x, int y)
{
    int loopCount=0;
    while (x>=y)
    {
        x -= y;
        loopCount++;
    }
    return loopCount;
}



But this is not efficient as the loop runs x/y times.

To understand bitwise operation, let us take an example:
Suppose we want to divide 66 by 6
Then it can be done as follows:
6 x 11 = 66

6 x (8 + 2 + 1) = 66

6x23 + 6x21 + 6x20 = 66

6 x (1011)b = 66

6<<3 + 6<<1 + 6<<0 = 66
This implies that if we just subtract powers of y from x, we can do an efficient divide.


static int divide (int x, int y)
{
    int powerY = y;
    int power = 1;
    int loopCount=0;
    while (powerY < x)
    {
        powerY <<= 1;
        power <<= 1;
        loopCount++;
    }

    int quotient=0;
    while (powerY > 0)
    {
        powerY >>= 1;
        power >>= 1;
        if (x >= powerY)
        {
            x -= powerY;
            quotient += power;
        }
    }

    System.out.println("loopCount = " + 2*loopCount);
    return quotient;
}



Beauty of the above solution is that it runs log(2*y/x) times which is much more efficient than the first solution.

To appreciate this difference, observe that if you divide 100 by 1, the first function iterates 100 times while the second one only iterates 14 times.
As x/y increases, this difference becomes more and more prominent.





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal