Archived

This topic is now archived and is closed to further replies.

walkingcarcass

Float-to-fraction

Recommended Posts

As an excercise I have been writing an arithmatic library for fractions (2 ints A and B interpreted as A/B). I thought it might be useful to try and convert floating point numbers into fractions which would make decimals, square roots etc much nicer. My first idea was to successively multiply the float by integers until the result is very nearly an integer, but as you can imagine it can be pretty damn slow for some numbers. I cant see an obvious speedup (maybe its just a forest-for-the-trees situation) and there should be some kind of early check for results likely to be as nasty as 2863411517/2863411277. ******** I am not the Iraqi information minister.

Share this post


Link to post
Share on other sites
I hope you realize that such a conversion will never be perfect. How do you hope to express a square root as a fraction?

But ignoring infinte sequences (even recurring), I would suggest keeping the same method, but done slightly differently. Start by multiplying the float by N! where N is a number around say 20. Test to see if this is within a certain amount of an integer. If not... try a larger value of N. Give up when N reaches a given size or when float*N! is greater than 9 digits (or however long the mantissa in a float is). It is important to allow it to give up, as any realistic fraction converter would just approximate nasty fractions to nice ones. There is not enough data in a float to do it to many digits.

Once you have this integer, call it A. Then the fraction will
be A/N!. You can cancel down if you feel bloody minded, but then you are back to where you are started with doing numbers one by one.

The speedup is precalculating N! so there is only one multiplication for several numbers.

NB: You may complain that you could get smaller numbers using the product from 1 to N of N, but that would not give the right ratio of primes. N! is likely to be a multiple of any non-prime a good deal higher than N, while the other isn''t.

Share this post


Link to post
Share on other sites
Aren''t all floating points stored in the binary format?

If that''s the case, it means that there is a finite number of binary digits after the point. If you know that number, n, your fraction is just the numbers after the point, divided by 2 ^ n. In decimal,

3.942 = 3 + 942 / 10 ^ 3

HTH,

Cédric

Share this post


Link to post
Share on other sites
The way to go if you want nice results quite fast:

use continued fractions...
every number can be expressed as:


1
a = n0 + ---------------------
1
n1 + ---------------
1
n2 + --------
...


This fraction can be infinite or finite, depending on the number a considered.

Ok, now the trick you should use:
take a float.
---> it's an integer part n0
---> plus a fractional part f0

take the inverse of f0.
again it's an integer part n1 and a fractional part f1.

Apply this recursively until some criteria is met (for example if ni is quite big, 1/ni -> 0 and then you can halt).

At this point you have a nice sequence of ni's which you can reduce to a single fraction A/B; it should be pretty easy since you already write the whole library.

Well that's it. Note that there's plenty of room for optimizations in the way you're gonna program this idea.

As far as I know, it's THE way to go if you want to convert float to fractions. But also notice that some floats convert badly to fraction (especially the numbers which are not in Q, like the square roots and so on...).

Hope it helps,
jods

[edited by - jods on July 6, 2003 11:44:06 AM]

Share this post


Link to post
Share on other sites
x=2/3=.6...; 10x=6.6... 10x-x=6; 9x=6; x=6/9; x=(2*3)/(3*3)=2/3. So part is recognizing repeating decimals even though they don''t infinitely repeat in floating point format and the other is to factor the numerator and denominator.

Share this post


Link to post
Share on other sites
Why not just do something like this:

If the variable has 3 decimal places.. multiply by 1000 (remove decimal places!). Then you can simply find the lowest common denominator and find the fraction.

Share this post


Link to post
Share on other sites
quote:
Original post by sadwanmage
I hope you realize that such a conversion will never be perfect. How do you hope to express a square root as a fraction?


The square root of 1.777... is 1.333... The qquare-rooter would take 1.777... as 16/9, see how now? Of course it would only work sometimes

Thanks for those ideas! sadwanmage, cedricl and jods, HOW do your brains do that? The continued fractions one is very cunning.

********


I am not the Iraqi information minister.

Share this post


Link to post
Share on other sites