Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# Long Division

Posted on 2004-09-27
Medium Priority
659 Views
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!
0
Question by:eternal_21
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 9
• 6
• 2
• +7

LVL 13

Accepted Solution

SteH earned 400 total points
ID: 12161363
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

LVL 10

Author Comment

ID: 12161538
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

LVL 13

Expert Comment

ID: 12161641
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

LVL 9

Assisted Solution

rjkimble earned 400 total points
ID: 12162098
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

LVL 10

Author Comment

ID: 12162215
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

LVL 27

Assisted Solution

d-glitch earned 400 total points
ID: 12162501
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

LVL 27

Expert Comment

ID: 12162613
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

LVL 27

Expert Comment

ID: 12162733
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

LVL 10

Author Comment

ID: 12162765
> 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

LVL 10

Author Comment

ID: 12162771
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

LVL 22

Assisted Solution

grg99 earned 400 total points
ID: 12162862
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

LVL 27

Expert Comment

ID: 12163031
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

LVL 27

Expert Comment

ID: 12163078
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

LVL 10

Author Comment

ID: 12163159
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

LVL 27

Expert Comment

ID: 12163358
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

LVL 22

Expert Comment

ID: 12163482
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

LVL 27

Expert Comment

ID: 12163527
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

LVL 6

Assisted Solution

Sergio_Hdez earned 400 total points
ID: 12168926
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

LVL 101

Expert Comment

ID: 12173240
Search this forum for BIGINT

mlmcc
0

LVL 27

Expert Comment

ID: 12180812
>> 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

LVL 48

Expert Comment

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

LVL 9

Expert Comment

ID: 12255962
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

LVL 27

Expert Comment

ID: 12545121
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

LVL 10

Author Comment

ID: 12672231
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

LVL 75

Expert Comment

ID: 13974168
For the record, I have reminded the questioner that this question remains open.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to reâ€¦
This article covers the basics of data encryption, what it is, how it works, and why it's important. If you've ever wondered what goes on when you "encrypt" data, you can look here to build a good foundation for your personal learning.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templaâ€¦
###### Suggested Courses
Course of the Month4 days, 10 hours left to enroll