• Advertisement
Sign in to follow this  

Truncating a fraction when overflow occurs

This topic is 676 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

I use integers to represent the numerator and denominator in a fraction and always optimize using the greatest common denominator from the euclidean algorithm. No matter how many bits I use, I will sooner or later get an overflow and have to fall back on approximations. Mixing different data types at run-time would be worse than just having floats all the way like I had before.

 

Is there a way to find the best truncating number without having to brute-force test all errors with floating point approximations?

 

For example, 62000000 / 30999998 should truncate using 31000000 and become 2 / 1 marked as an approximation.

Just dividing with some number does not work since it must handle very large and very small numbers.

Share this post


Link to post
Share on other sites
Advertisement

well, you could always implement a "bignum" data type. i had one of those back in the 16 bit days.

 

all you do is take for example two int 64's, and put them side by side to make your "bignum" , so your bignum = int64 #1 * MAX_VALUE_INT64 + int64 #2.

 

then all you have to do is implement add (with carry) and negate methods.

 

subtraction is a negated add.  multiplication is repeated adds. division is repeated subtracts.

 

but just doing it all in float or double may be easier (and faster - who knows?).

Share this post


Link to post
Share on other sites
You can use mpq_class from GNU MP to represent rational numbers exactly. It uses arbitrary-precision integers for the numerator and denominator.

But the operation you are asking about is interesting to think about regardless of its practical application. I would consider using the continued fraction expression of your number. See the section titled "Best rational approximations" for details.

Informally, in your example
62000000 / 30999998 = 1 / (2 + 1 / (7749999 + 1 / 2))

Whenever a large number pops up in the continued fraction expression of a number, one can find a good approximation using a fraction by substituting that number with infinity

1 / (2 + 1 / Infinity) = 1 / (2 + 0) = 1 / 2


You can do that with irrational numbers as well:

pi = 3 + 1 / (7 + 1 / (15 + 1 / (1 + 1 / (292 + 1 / (1 + ...)))))

If you replace 292 with infinity, you get

pi ~= 3 + 1 / (7 + 1 / (15 + 1 / (1 + 0))) = 355 / 113 = 3.14159292035398230088...

Share this post


Link to post
Share on other sites

Divide both numbers by two? Which is just a right shift.

You could always right shift if your shifting out zeros (on both numbers).

If not, you get truncation, which may be still good enough approximation. (You should not shift out the last bit though)

Share this post


Link to post
Share on other sites

.NET has the BigInteger structure that could do this for me but I decided to use Visual Basic 6 to get many times better performance while still being able to design the interface quickly so I will probably have to implement something on top of 32-bit integers or find some existing library if I want to extend the numbers.

Edited by Dawoodoz

Share this post


Link to post
Share on other sites

Divide both numbers by two? Which is just a right shift.

You could always right shift if your shifting out zeros (on both numbers).

If not, you get truncation, which may be still good enough approximation. (You should not shift out the last bit though)

 

It tried that but the precision was not good enough.

Share this post


Link to post
Share on other sites

Since vertices starts to truncate after just three cuts into a cube, maybe I get the most precision from falling back on the old 64-bit float solution for vertice locations and just keep the persistent data that does not accumulate errors in fraction format.

Share this post


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

  • Advertisement