Prasanna

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)

Posted at 07:00PM Sep 09, 2007 by prasanna in Useful Code  |  Comments[4]