# Long Division

I am having a problem with long division, and hoping you guys can help me out.  I am trying to write an algorithm to do long division on strings on numbers.
I'll use 520 / 15 as an example:
_________________________
1x10^1 + 5x10^0 | 5x10^2 + 2x10^1 + 0x10^0

How do I do this?  I don't even know how to find the first digit!
LVL 10
###### Who is Participating?

x

Commented:
52(0) /15 = 3 1st digit
3 * 15 = 45
7 0 / 15  =  4 (2nd digit)
4 * 15 =   60
10(.0) / 15 = (.) 6 (3rd digit and after decimal place
6 * 15 =     9(.)0
1.0(0) / 15 = 6 (...)
0

Author Commented:
Sorry, I wasn't specific enought, I guess.... I am working with just strings, so I only can divide 1 number at a time. i.e.: I cannot divide 52 by 15, but I can divide 5 by 1.

The problem is apparent when I try to do 9982212323412433749874383281739875934 / 12143427921734231412432134, because I can't fit 12143427921734231412432134 into any variable (i.e. Int32, Int64).
0

Commented:
I don't see how a division could be done by putting the divisors digits apart. Using the divisors prime factors could be an option and divide by any of them. But I might missing some division tricks/algorithms here!
0

Commented:
The standard trick is to divide by all the digits, because there's no real shortcut to doing that. Starting with the dividend, you take enough digits to create a number that is larger than or equal to the divisor. Then you figure out the correct digit multiplier, multiply the divisor by that and subtract. Then you add the next digit and repeat. That's the gist of it. I'll let you work out the details.
0

Author Commented:
The details is where I am having the problem :)  To give you a little more info, I have created the ubiquitous "BigInt" class...

The class contains an array of numbers, representing (n1)x2^0 + (n2)x2^1 + (n3)x2^2 + ...

Adding and multiplying them is easy (here is my add code, for example):

// Trim is a function that strips all 'leading zeros'.

private static uint[] Add(uint[] x, uint[] y)
{
x = Trim(x);
y = Trim(y);

uint[] z = new uint[(x.Length > y.Length ? x.Length : y.Length) + 1];

ulong c = 0;
for(int e = 0; e < z.Length; e++)
{
ulong ux = e < x.Length ? (ulong)x[e] : 0u;
ulong uy = e < y.Length ? (ulong)y[e] : 0u;
ulong uz = ux + uy + c;

z[e] = (uint)uz; //(uz << 32) >> 32
c = uz >> 32;
}

return Trim(z);
}

And I have build a subtract function.  But the divide method is KILLING me!  I have do divide a 'two digit' by a 'two digit' number, that is okay because I can do that operation in ulong (Int64)... but if I have to divide by a three digit number or more, how can I handle this?

How would you do 400 / 150 if you only knew the times tables up to 9 x 9 (or maybe 10 x 10)? And COULD NOT do something like 40 / 15, you could only do 4 / 1, etc.
0

Commented:
You will need to write a few subroutines:      One to mulitiply the divisor by 10^n  (just adding zeros to the right end of the string)

One to to subraction of character string numbers.

One to compare the magnitude of two character string numbers.

DIVIDEND  =>     9 982 212 323 412 433 749 874 383 281 739 875 934     approx   9.982 x 10^36

DIVISOR   =>                             12 143 427 921 734 231 412 432 134      appox   1.214 x  10^25

QUOTIENT =>                                                                                        approx  8.222 x 10^11

Add as many zeros to the divisor as you can while keeping it less than the dividend.

In this case it will be 11 zeros.

Subract the (divisor x 10^n)  from the dividend as many times as you can while keeping the difference positive.

In this case it will be 8 times.  The first estimate for the quotient will be 800 000 000 000 ( 8 followed by 11 zeros)

The difference is the remainder.

The remainder is your new dividend.  You have to repeat the process for every digit in the quotient.

The only slightly tricky part is keeping track of the decimal point.
0

Commented:
400 - 150 = 250
250 - 150  = 100    ==>  2 subractions  ==> Q1 = 2   Rem = 100

100 - 15.0 = 85
85 - 15.0 = 70
70 - 15.0 = 55
...      ==> 6 subractions  ==> Q2 = .6  Rem = 10

10 - 1.50 = 8.50

And so on.

When you've done as many digits as you want, you add up all the Q's and you'll get 1.6666
0

Commented:
You don't need a multiplication subroutine, but  your algorithm can be much more efficient if you have one.

The first thing you would do is make a table of           1 x DIVISOR
2 x DIVISOR
...
9 x DIVISOR

Then you can look up in the table to find the number to subtract rather than doing trial and error.

You can also build the table with just an addition subroutine.
0

Author Commented:
> Subract the (divisor x 10^n)  from the dividend as many times as you can while keeping the difference positive.

Is there any more efficient way to do this?  In decimal system, there is only 9 tests, but I am essentially using a numeric system of base 2^32, so I could theoretically have to subtract many, MANY times... i.e.:

255 x 2^0                                      R   68716551635 x 2^0
________________________________
16 x 2^32 + 11478 x 2^0 |  4096 x 2^32  +  1789 x 2^0

I'd have to subtract 255 times...  And this gets even worse when working with more likely numbers, I could be subtracting as many as 2^32 times per 'digit'
0

Author Commented:
Oops, just saw you last post, but as you can see that table is going to be huge (array would have a length of 4294967296).
0

Commented:
No problems, mate.  Just do it EXACTLY the way you do long division by hand.

You'll need a subtract-long routine.  It won't get called that many times (9 times max), because you can guess how many digits to grab from the numerator just by counting the lengths.

0

Commented:
The table I was talking about in my post only has 9 entries.

For each digit of the qutient you have to do the following three steps:

Figure out how to shift the divisor.
Find the element in the largest element in the table that is less that the dividend to get the digit for the quotient Qn
Subtract the table entry from the dividend to get the remainder which will be the dividend for the next iteration.

If this is a learning to program project, character string arithmetic is probably fine.

0

Commented:
If you are doing arithmetic in base two, you don't need a table at all.  Rather your table only needs one element.

You can do every thing with shifting  and subtracting.  But you have to convert all your 30 decimal digit numbers into base two.

If you need it to be fast, base two is the way to go.
0

Author Commented:
grg99,

> You'll need a subtract-long routine.  It won't get called that many times (9 times max)...

Are you sure?  I don't know if I have a clear picture of this, but I am not working in base 10, I am in base 2^32...  I am just trying to find an actual 'division algoritm' that I can use as an analogy.  I don't want to use multiple subtractions, as this could go on for a very long time.
0

Commented:
Just becuase you have iintegers up to 2^32 doesn't mean you have to use them.

If you really want to divide (9982212323412433749874383281739875934) by (12143427921734231412432134) then character string arithmetic is a perfectly fine way to go.

When grg99 said that the subtraction would be called 9 times maximum, he meant per digit.

Subtraction is the fundamental basis of division.  There are no shortcuts.  And it need not be that inefficient.

If you build a table you will have one subtraction for each digit of the quotient.  That's not bad at all
0

Commented:
Oh, I thought you were using strings.

If you're using 32-bit integers, then you just take the number of bits in the denominator, grab the same number of bits of the numerator, and subtract away.  You'll have to do some masking and shifting.  Keeping track of the binary point is a bit tricky.

One halfway-step is to do the division and subtraction one bit at a time at first.  Helps you build up confidence to see the right number come out.

Then you can work your way up to subtracting say 8, 16, and 32  bits at a time.
0

Commented:
There a BIGINT calculator on line.  Source code is available.  They might have some useful background for you.

http://www.acme.com/software/bigint/
0

Commented:
If you look for bigint division, first think division is not really suppoerted for integers... results use to be non-integers... so I suppose you want the truncated result.

Then, A/B=C with no decimals... if it is so, then B*C <= A <= B*(C+1)-1, so may be you can try to guess C value by trial-and-error.

Imagine in base 10, 2345/23=C, lenght difference between up and down numbers is 2, so result will be between 10^(2-1)+1 and 10^(2+1)+1, as 23*10 sure will be too small and 23*1000 sure will be too big.

If you work on base 2^32, things get harder as you have maaannnyyyy Cs to try, but even woith that, you can do it by succesive aproaches:

Start with an empty C value of lenght(A)-lenght(B)+1 digits, we know C will have no more than those digits! (In our example, 2345/23, the difference is 2 digits, so 3 digist are needed).

Now you have an empty candidate, we can reach the real C by guessing digits one by one. The idea is to determine first one, then second one having the first one fixed and the rest variable.

Iterate thru all 3 digits starting in the left-most one:

For each digit, start setting its max value to '9' (max digit in your base), min to '0' and actual to '5' (a mid-range digit value), then fill the rest of the digits (right side only, left side are already guessed digist) to '0' and start a loop that will end when max=min=actual, so you have this digit guessed and can move to work on second one.

In the loop for a digit guess, calculate  B*C (23*500=11500 in the example) and compare with A (2345):

A) If it is bigger, decrease the max value to actual-1 (max=5-1=4 in our example), set actual value with something in-between max and min values (between 4 and 0, 2 is the best choice) and iterate again (try with '200').

In our example, 2nd iteration will give you 23*200=4600 > A (2345), so again you set max=2-1=1, and actual between 1 and 0, so 1 is a good choice (as good as 0). 3rd try will get into the next case...

B) If it is lower, as it will happend in our 3rd try for the first digit guess (23*100=2300 < 2345), then set min=actual (min=1 in our case) and increase actual to something in-between max and min... in out 3rd try, max=1 and now min=1, so actual have to be 1 and we have ended with that loop, the program will go to the "next" digit.

May be it is a ugly approach, but you will need only a next-for with a loop inside, and each loop will need a multiplication and one or two comparations (that also can be made faster than comparing all the digits, ofcourse).

I know, it is a bad idea, but sometimes those aproaches runs more that "formal" aproaches!
0

Commented:
Search this forum for BIGINT

mlmcc
0

Commented:
>> Sergio_Hdez    division is not really suppoerted for integers... results use to be non-integers... so I suppose you want the truncated result.

A proper BIGINT division routine should give a Quotient and a Remainder

You can evaluate the Quotient using multiplications and comparisons but this would be horribly inefficent.

Multiplying an two N-digit numbers takes N N-digit additions.  Subtracting two N-digit numbers takes one N-digit subtraction.

0

Commented:
Have you looked at the GNU bc-library ( http://www.gnu.org/software/bc/bc.html ) which does excatly that.
0

Commented:
the only difference between using "normal" strings and arrays is that you have 32bit characters instead of 8bit.

instead of multiple substractions divide first digit of dividend by first digit of divisor. (or use first two digits for a better estimate.) you will land in the ballpark of how many subtractions you need to perform. multiply the divisor by the ballpark quotient and do the subtraction. (need to fine tune the quotient but i think it's easy enough) repeat for next digit ...

pre-requisite: multiplication routine
0

Commented:
Quite a bit of work from several people.  I hope we helped.

I believe the bottom line is

>>  Subtraction is the fundamental basis of division.  There are no shortcuts.
0

Author Commented:
My apologies to everyone, I have been extremely busy the past two months, and [unfortunately] have had very little time to work on this project or spend much time at all on EE.  If you leave this question open for one more week, I will review the responses and select appropriate answers sometime in the next few days.

It's long overdue, but: Thank you everyone for your help!
0

Commented:
For the record, I have reminded the questioner that this question remains open.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.