Jump to content
  • Advertisement
Sign in to follow this  
xytor

Simple division is too slow

This topic is 2778 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Advertisement
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).

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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)



Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!