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!
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!
0
Your question, your audience. Choose who sees your identityâ€”and your questionâ€”with question security.
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.
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.
> 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'
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.
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.
> 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
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.
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!
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 ...
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.
0
Featured Post
Are you tired of cycling through the same browser tabs everyday to close the same repetitive tickets? In this webinar JumpCloud will show how you can leverage RESTful APIs to build your own PowerShell modules to kill tickets & tabs using the PowerShell command Invoke-RestMethod.
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 (...)