Given two positive integers A and B compute the quotient and remainder without using multiplication. This is an old problem except, in optimising the algorithm we derive the long division method taught in primary school.
Problem: Given A and B, where
B>0 compute q and r such that:
A = B*q +r
r≥0 using only addition and subtraction. This is a fairly simple algorithm as shown below:
def divisor(A,B): q = 0 r = A #loop invariant : A = q*B + r while (r >= B): q,r = q+1, r-B return q,r
The time complexity is O(A/B). If A is say one million and B is 3, then the loop will executed 333,333 times. How can we reduce the number of iterations? We could reduce it by half if we deduct B twice as shown below
def divisor(A,B): q = 0 r = A #loop invariant : A = q*B + r twiceB = B + B while (r >= B): if (r >= twiceB) : q,r = q+2, r - twiceB else : q,r = q+1, r-B return q,r
Now, why do we want to reduce only twice? Why not four times or eight or more? If we allow multiplication or division by the radix then we can use the following procedure. Multiplication of a number by the radix is trivial because it means moving the digits of number left or right.
def divisor(A,B): q,r=0,A q0,r0=1,B radix=2 #loop invariant r0 = B * q0 while r0*radix ≤ A: q0,r0=radix*q0, radix*r0 #loop invariant : A = q*B + r while r≥B: #loop invariant : A = q*B + r while r0≤r: q,r = q+q0, r-r0 q0,r0 = q0/radix, r0/radix return q,r
Notice that the above algorithm works even if the radix is ten, or in other words all numbers are represented in decimal. In Line 6, we are pushing B to the left until it is just less than A.
q0 keeps track of how much B is being shifted left. Notice that if the radix were two the while loop in Line 11 is a conditional statement. To prove that the loop invariant holds note that
r0 = B * q0
(q+q0)*B + r-r0 = q*B + r +(q0*B -r0) = q*B + r = A (QED)
Thus dear reader you now have the algorithm that was taught to you in primary school in Python-esque code.
while loop commencing at Line 9 computes the most significant digit or bit of the quotient at the first iteration.;the next most significant bit at the next iteration and so on. Hence the number of iterations can be at most log(A/B). The inner loop at Line 11 is executed at most
radix times. Hence the time complexity is O(log(A/B)).