### Division of two numbers without using division operator

#### By prasanna on Sep 09, 2007

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)

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)

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

Vellachion 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 Seshadrion October 21, 2007 at 05:04 PM IST #plz send c++ programe

Posted by

gueston October 15, 2008 at 10:24 AM IST #show me the code!!!

Posted by

yanyanon January 21, 2009 at 02:39 AM IST #l

Posted by

gueston March 15, 2010 at 07:43 PM IST #Nice idea. I think the worst case run time is O((log n)\^2)

Posted by

RGon 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

Dattaon 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

veeruon 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

zhangon March 14, 2011 at 04:53 AM IST #