Arithmetic Division: Old wine in new bottle

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 A>0 and B>0 compute q and r such that:
A = B*q +r
where q≥0 and 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

Hence

(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.

Time Complexity

The 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)).

 

 

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s