Division of two numbers without using division operator

I was trying an efficient solution for this problem for sometime and came up with this.

The logic is simple, just left shift (multiply by 2) the divisor till it reaches dividend/2, then continue this routine with the the difference between dividend and divisor and divisor till the point when dividend is less than divisor or the difference is zero. Its similar to the way binary search is used to find an element in a sorted list. Confused! go through the below recursive procedure in python.

#Division of two numbers without using division operator

dividend = int(raw_input("Enter the dividend:"))
divisor  = int(raw_input("Enter the divisor:"))
tempdivisor = divisor
remainder = 0

def division (dividend, divisor):

    global remainder

    quotient = 1
      
    if divisor == dividend:
        remainder = 0
        return 1
    elif dividend < divisor:
        remainder = dividend
        return 0
   
    while divisor <= dividend:
       
        #Here divisor < dividend, therefore left shift (multiply by 2) divisor and quotient
        divisor = divisor << 1
        quotient = quotient << 1        

    #We have reached the point where divisor > dividend, therefore divide divisor and quotient by two
    divisor = divisor >> 1
    quotient = quotient >> 1
   
    #Call division recursively for the difference to get the exact quotient
    quotient = quotient + division(dividend - divisor, tempdivisor)
            
    return quotient

print "%s / %s: quotient = %s" % (dividend, tempdivisor, division(dividend, divisor))
print "%s / %s: remainder = %s" % (dividend, tempdivisor, remainder)
Comments:

Nice way to look at division!
Never thought of it this way!

When you refer to this algorithm as being efficient, do you have some metrics as to how it compares in terms of
run-time, with regular divison in C for example?
Ofcourse, the algo by nature will give widely differing runtimes, based on the actual numerator and denominator. But one should be able to make a comparision on the average and/or for the worst case scenario.

Regards,
Vellachi

Posted by Vellachi on October 19, 2007 at 09:21 AM IST #

I thought this solution may be efficient though I didn't have any metrics for the same. I know that division would be fast using bit shifting and thats how I arrived at this solution.

Anyway this is just for learning purpose, to know about some fundamental computer algorithms.

Posted by Prasanna Seshadri on October 21, 2007 at 05:04 PM IST #

plz send c++ programe

Posted by guest on October 15, 2008 at 10:24 AM IST #

show me the code!!!

Posted by yanyan on January 21, 2009 at 02:39 AM IST #

l

Posted by guest on March 15, 2010 at 07:43 PM IST #

Nice idea. I think the worst case run time is O((log n)\^2)

Posted by RG on April 21, 2010 at 09:17 PM IST #

Ahhhh.... this is pretty much long division in binary base instead of base of 10.

Posted by Datta on June 09, 2010 at 02:10 AM IST #

How about since division is nothing but a subsequent subraction,
subtract the divisor from dividend until either you reach zero or a value that is less than the divisor.

write down special cases before you jump into the while loop

//not tested

num = dividend; count =0;
if(dividend == divisor) return 1;
if(divisor == 0) return -1;
if(divisor > dividend) return 0;
else
do
{
num -= divisor;
count ++;
}while(num < divisor)

return count;

here returning the quotient

Posted by veeru on November 08, 2010 at 06:29 AM IST #

Hi,
I dont understand that why are you interested in first making the divisor greater than the dividend , and then making it less than the divident. What is the logic behind doing things the way u are doing it.

Posted by zhang on March 14, 2011 at 04:53 AM IST #

Post a Comment:
  • HTML Syntax: NOT allowed
About

prasanna

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today