Large Integer Division

Let's delve a bit deeper into an example.

	4	5	)	9	4	8

Now the first thing you do in long division is to take a guess. Here we look at 45 and say, hmmmm.... 45 probably goes into 94... maybe twice. So you put a 2 up on top, over the last digit you divided into.

					2
	4	5	)	9	4	8

Then you multiply it out and subtract.

					2
	4	5	)	9	4	8
				9	0
					4

Now you see that 4 is less than 45 so you know you're on the right track. Had you guessed 1, the subtraction would have been 49 which is greater than 45. That would indicate your guess was too low. If you had instead, guessed 3 the answer would have turned out negative (94 - 135 = -41) and you would have realized you'd guessed too high.

Now you go on to the next digit. You bring it down and now ask yourself how many times does 45 go into 48. Being the smart person you are, you guess once. So you multiply it out and subtract.

					2
	4	5	)	9	4	8
				9	0
					4	8
					4	5
						3

This time you have a result of 3. Again it is less than 45 and, since you're now out of digits, you're done. The answer is 21 with a remainder of 3.

However, had you guessed 2 instead of 1 you would have come up with a negative result and had you picked 0, the result would have been 48 which is greater than 45.

You do all of this in your head, very quickly. The computer, however, has to follow rules and programming logic to come up with a result so let's look at how we might approach this.

Recall that a / b means that a = (q x b) + r where q is the quotient and r is the remainder. Another way of looking at this is that r = a - (q x b).

So when you pick some number q, the result can be negative if the number you picked is too large. It can be a positive number greater than b which says the number you picked is too small. However, if the number is positive and less than or equal to b then you've made the correct pick.

So let's see how this might play out in an algorithm. Let's start by trying to find the first digit of the quotient. Here I'll start with 1. Now there are 3 digits in the dividend so it's possible the quotient could have 3 digits. To be safe, let me start with a quotient that has 3 digits. Here I'll append two 0's and start with q = 100.

So r = a - (q x b) = 948 - (100 x 45) = 948 - 4500 = -3552. Woops... That's negative so my selected q is a bit too big. That means my first digit (of a three digit quotient) would have to be 0. So let's cut back to two digits.

Here I'll try 1 again. Since we're using 2 digits, this becomes q = 10.

Now r = a - (q x b) = 948 - (10 x 45) = 948 - 450 = 498. That's positive but greater than our b = 45. So 10 is too small. Let's bump that 10 to a 20 (Remember, we're still trying to get that first digit. We know its not a 1 so bumping to 11 at this point won't help us.).

Ok. r = q - (q x b) = 948 - (20 x 45) = 948 - 900 = 48. Again positive and greater than 45 so we're too small. Let's bump q up to 30 and try.

This time r = a - (q x b) = 948 - (30 x 45) = 948 - 1350 = -402 is negative so we've gone too far. So 3 is too large as the first digit. That means the first digit is 2.

Now we can attack the second digit.

Let's try 1 again. So we have q = 21

Then r = a - (q x b) = 948 - (21 x 45) = 948 - 945 = 3. Voila! 3 is less than 45 so we have the result. So now we know that 45 divides 948, 21 times with a remainder of 3.

One of the noticeable things about division is that there is no well-defined number of multiplications and additions that will take place during the computation. This is unlike multiplication.

A lot depends on how close the initial guesses are. If we were dividing 2 into 9 then an initial guess of 4 would be on the money. However, if instead we started at 1 and incremented up until hitting 4, you would have done at least four computations of r = a - (q x b) instead of just one. So playing around with initial guesses can speed up the algorithm.