Hi, I am implementing my own division algorithm for a large real number library. Although speed is not an issue, there is one case in which it is extremely slow.
The core part of the algorithm finds the integer part and a proper fraction. It works by promoting both numbers to (sometimes much larger) integers and using repeated subtraction.
This algorithm is 100% correct in all my test cases, but for a certain type of test case is extremely slow:
If the dividend is much larger than the divisor.
For example, 200.0 / 0.001 gets converted to 200000 / 1.
Then, it takes 200000 repeated subtractions to get 200000 + 0/1.
Now, this is just a silly example but it shows that a large dividend and a small divisor produce a very slow result.
Is there any way to optimize my algorithm to handle this case faster?
Thanks!
Simple division is too slow
Binary long division will be faster than your current method, but since we already have a full set of arithmetic operations for 32 bit integers, we can do faster if we work with full 32 bit integers as digits (ie in base 2^32).
Author
I suppose I could, but both of those methods require a cumbersome base change from base 10.
I'm looking for an optimization to my algorithm, not an entire new one. Is that possible?
I'm looking for an optimization to my algorithm, not an entire new one. Is that possible?
Optimizing an implementation of an algorithm, without changing the logic behind it, usually means optimizing the individual steps (ie. your subtraction step). In your case, the problem most likely isn't the time it takes to do one such step though, but rather the shear number of steps required. So the only way to really get better performance is to rewrite it so that there are less steps required, which means you're going to have to change your algorithm.
But anyway, you say it requires a base change. Does this mean you are currently working in base 10? If so, then you can also use base 10 long division.
But anyway, you say it requires a base change. Does this mean you are currently working in base 10? If so, then you can also use base 10 long division.
Author
Actually, I think I figured out an optimization, and it seems to work:
Old algorithm:
Keep subtracting the divisor from the dividend until it reaches zero (or less)
The number of subtractions is the integer part of the division.
New algorithm:
Let X be (digits in dividend - digits in divisor) if that difference is at least 2, otherwise X is 1.
Keep subtracting the divisor*X from the dividend until it reaches zero (or less)
The (number of subtractions)*X is the integer part of the division.
However, this is not much of an improvement and the time still scales very quickly when the dividend gets larger than the divisor.
But I was hoping to flesh out this idea of taking care of as many subtractions as possible in one go by using multiplication. However, when I went too high (setting X to 10^(digits in dividend - digits in divisor)) it caused some calculations to be wrong.
Old algorithm:
Keep subtracting the divisor from the dividend until it reaches zero (or less)
The number of subtractions is the integer part of the division.
New algorithm:
Let X be (digits in dividend - digits in divisor) if that difference is at least 2, otherwise X is 1.
Keep subtracting the divisor*X from the dividend until it reaches zero (or less)
The (number of subtractions)*X is the integer part of the division.
However, this is not much of an improvement and the time still scales very quickly when the dividend gets larger than the divisor.
But I was hoping to flesh out this idea of taking care of as many subtractions as possible in one go by using multiplication. However, when I went too high (setting X to 10^(digits in dividend - digits in divisor)) it caused some calculations to be wrong.
Quote:Original post by xytor
I suppose I could, but both of those methods require a cumbersome base change from base 10.
I'm looking for an optimization to my algorithm, not an entire new one. Is that possible?
Wait are you not storing your huge numbers in a bit format?
Nah you want an entirely new one. Your method is extremely naive and expensive.
Author
Quote:Original post by alvaro
You learned a much faster division algorithm in elementary school. Try using that.
Repeated subtraction is the only way that I can see to do it.
Long division sounds like a great idea when we have the multiplication table memorized. But what about something like 1/245205982340? Long division seems to become impossible with a large divisor.
Author
Ah! I've figured out a way using long division and trial multiplication:
Let "partial dividend" be the first digit in dividend.For each digit "i" in dividend: For each number "j" 9 to 0: if divisor*j is less than or equal to the partial dividend: add j as the next digit of the answer. break out of loop new partial dividend is: (( partial dividend - (answer's newest digit * divisor) ) * 10) + ("i+1"th digit of dividend)This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
