Solved

Long Division

Posted on 2004-09-27
29
635 Views
Last Modified: 2012-06-21
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
Comment
Question by:eternal_21
  • 9
  • 6
  • 2
  • +7
29 Comments
 
LVL 13

Accepted Solution

by:
SteH earned 100 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

by:eternal_21
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

by:SteH
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

by:rjkimble
rjkimble earned 100 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

by:eternal_21
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

by:d-glitch
d-glitch earned 100 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

by:d-glitch
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

by:d-glitch
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

by:eternal_21
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

by:eternal_21
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

by:grg99
grg99 earned 100 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

by:d-glitch
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
What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 27

Expert Comment

by:d-glitch
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

by:eternal_21
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

by:d-glitch
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

by:grg99
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

by:d-glitch
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

by:Sergio_Hdez
Sergio_Hdez earned 100 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 100

Expert Comment

by:mlmcc
ID: 12173240
Search this forum for BIGINT

mlmcc
0
 
LVL 27

Expert Comment

by:d-glitch
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

by:hernst42
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

by:jhshukla
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

by:d-glitch
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

by:eternal_21
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

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

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
Internet Business Fax to Email Made Easy - With eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, fr…
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now