# Division by parts algorithm? (not Calculus)

• Oct 13th 2012, 04:18 AM
rortiz81
Division by parts algorithm? (not Calculus)
I have a Computer Science problem. I already asked on the very popular CS site Stack Overflow and they gave me garbage for an answer. I have to divide two arrays up to 30 digits in length. The arrays represent a large integer and each element in the array can hold a number from 0-9. So to represent the number, say 180, the array would look like this A0-A26 = 0 <-- leading zeros, then A27 = 1, A28 = 8 A29 = 0. Because I have to work with two arrays, I have to create an algorithm to compute the quotient of the dividend and one digit from the divisor at a time.

I know this works with multiplication. For instance, we know that 12 * 12 = 144, but we can break the method down into parts by figuring out that 10 * 12 = 120 and 2 * 12 = 24. 120 + 24 = 144. I have an algorithm that does just this. I need to do the equivalent for division. Exactly what I did was this I got 2 * 12 = 24, then I got 1 * 12 = 12 but I shifted it to the left by one and threw in a zero to pad it and it became 120. The 24 and 120 were stored in a table of rows and columns, then I just added up the columns. This EXACTLY what we did as kids in school. We calculate the product for the 1's place, then the 10's, then the hundreds, but all were doing is an iterative process of taking each digit in the "bottom" (or smaller number) and multiplying it by each number in the top, and we shift the product of each to the left by n where n is the digit offset in the number 10^n (so for the 1's place it's 10^0 or no shift, 10's is 10^1 or shifted by 1).

Say I want to find 180 / 15. The answer is 12 because 12 * 15 = 180. So I got to the point now I can get the quotient "by parts" thus: If I divide 180 by 5 I get 36. Then I divide 180 by 10 to get 18. However my train gets derailed here. I cannot for the life of me figure out how to extrapolate 12 from 10 and 18. I have tried subtracting, cross multiplying, I have looked up division algorithms, abacus math, modular arithmetic, short division, restoring, non-restoring, SRT, Newton, Euclidean, ect. I know the answer may lie in something I already read, but I am either not smart enough or too tired to get it. With multiplication, the total is the sum of the parts (products of one number times each digit in the other), but it doesn't seem to follow that division is equal to the total of the difference of the parts (quotients of dividend and every digit in the divisor). I know division is pretty much the opposite of multiplication, and I know multiplication is just repeated addition, so division is just repeated subtraction. UGH. I just go round and round. (Headbang)

When we do long division, we don't layout the process quite the same way as with multiplying two big numbers. Long division works by using the WHOLE divisor and seeing how many times it will fit into the dividend. I need to break that work up into EACH digit in the divisor, then subtract, shift, take the log of, or ... SOMETHING. I used 180 / 15 = 12 because it's easy to understand. Unfortunately this doesn't even take remainders into account, which I know will play a part. In multiplication, the carry gets added to the next product, unless it's at the end of the number, then it's just written down (ex: 2 * 99 = 198, the 8 being the 8 from 2 * 9 = 18 and the 19 being (2*9) + carry (1) = 19, the last 1 is not carried but just added to the left of 9), but in division the remainder acts as a kind of "reciprocal" of the carry and is used to evaluate the next division and subtraction. Right now I am ignoring the remainder if it represents the fractional part of the quotient because I don't know what to do with it.

PLEASE HELP. I am so lost. I have been working on this problem for days now. It feels like the answer is right around the corner. It is the last bit of homework I need to submit and it's late :( I am usually so good at problem solving but just can't do this on my own. Sorry about the wall of text, but I wanted to be exact so you know what I need. Also, if Number Theory is the wrong place to post this I apologize; this sub-forum was my best guess. I know the geniuses here on MHF can make Stack Overflow look like amateurs ...
• Oct 13th 2012, 05:26 PM
rortiz81
Re: Division by parts algorithm? (not Calculus)
Really?
• Jan 24th 2013, 02:19 PM
davidwees
Re: Division by parts algorithm? (not Calculus)
This is probably too late for you, but I wrote an arbitrary precision division calculator in JavaScript. See Javascript Calculator. If you view the source of the page, you may be able to reconstruct the algorithm and convert it to C.