Link to home
Start Free TrialLog in
Avatar of eternal_21
eternal_21

asked on

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!
ASKER CERTIFIED SOLUTION
Avatar of Member_2_1001466
Member_2_1001466

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of eternal_21
eternal_21

ASKER

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).
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!
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
SOLUTION
Avatar of d-glitch
d-glitch
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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
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.
> 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'
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).
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.

                                                                   
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.
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.
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
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.
There a BIGINT calculator on line.  Source code is available.  They might have some useful background for you.

                                                               http://www.acme.com/software/bigint/
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Search this forum for BIGINT

mlmcc
>> 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.

 
Have you looked at the GNU bc-library ( http://www.gnu.org/software/bc/bc.html ) which does excatly that.
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
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.
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!
For the record, I have reminded the questioner that this question remains open.