I am looking for something with a signature like

`fn f64_to_fraction(num:f64) -> (u64, u64)`

does this exist in the standard library or battle-tested crate somewhere?

I am looking for something with a signature like

`fn f64_to_fraction(num:f64) -> (u64, u64)`

does this exist in the standard library or battle-tested crate somewhere?

There is nothing like this in `std`

AFAICT. However, in general, this is a hard problem.

Floating-point numbers are rationals of which the denominator is *always* some power of 2. However, people generally expect them to use as (an approximation to) real numbers, including rationals with other prime factors in their denominator.

For example, if you create `let third: f64 = 1.0 / 3.0;`

it would be a realistic expectation that `f64_to_fraction()`

return `(1, 3)`

. However, since 1/3 is not exactly representable, this is not possible without specifying some sort of tolerance or a degree of simplification/"rationalization", within which you wish to decrease the prime factors in the numerator and the denominator.

What is your use case, what do you need this for? If you are fine with the "always a power of two" interpretation, you might be able to do something like this:

```
fn gcd(mut x: u64, mut y: u64) -> u64 {
while y > 0 {
let rem = x % y;
x = y;
y = rem;
}
x
}
fn to_rational(x: f64) -> (i64, u64) {
let log = x.log2().floor();
if log >= 0.0 {
(x as i64, 1)
} else {
let num: i64 = (x / f64::EPSILON) as _;
let den: u64 = (1.0 / f64::EPSILON) as _;
let gcd = gcd(num.abs() as u64, den);
(num / gcd as i64, den / gcd)
}
}
```

2 Likes

Floating points numbers aren't Real numbers.

There's the `fraction`

crate which has both a `Fraction`

and `Decimal`

type. With the associated `From`

trait implemented for a number of types. Those types have a significant runtime cost*.

*measure your use case, "significant" is a relative term

1 Like

my use case is going from a f64 into a more robust type, like a Decimal implementation which allows conversion from either a String or Fraction, figured a Fraction might be faster

I get that, but in which application are you using these types? Do you need to solve the harder problem, i.e., convert an approximation of a rational number to the original exact representation with some tolerance?

It's probably fine for it to be a bit lossy for my use-case here

I don't know of a crate off-hand, but some key phrases to search for if you want to try and find one or implement it yourself would be "continued fraction" or Stern-Brocot. Here's a Wikipedia article, and another. By making an algorithm to traverse the tree quickly, you can come up with good rational approximations to floating point numbers, corresponding to the best rational approximations as represented by continued fractions.

I can't share any code directly, but let me try and sketch the algorithm. This will be very informally sketched.

Start with a left numerator and denominator of `0`

and `1`

, and a right numerator and denominator of `1`

and `0`

. The `input`

is the value you're trying to find a rational for. At any given step, the approximate rational is the sum of the left and right numerator over the sum of the left and right denominator.

If the input is less than `1.0`

, you go left:

`input = input / (1.0 - input)`

- right numerator = 1 * left numerator + right numerator
- right denomintator = 1* left denominator + right denominator

If it's greater you go right:

`input = input - 1.0`

- left numerator = left numerator + right numerator * 1
- left denominator = left denominator + right numerator * 1

When you converge on `input == 1.0`

, you're close to an optimal approximation.

Going one step at a time is slow, though. If you're much less than `1.0`

, you want to go left about `1.0 / input`

times (but fudge this quantity, because floating point). `x = x / (1 - x)`

applied `n`

times is `x = x / (1 - n * x)`

.

If you're much more than `1.0`

, you want to go right about `input`

times (but again, fudge it). `x = x - 1`

applied `n`

times is... I'll let you figure this one out.

For the numerator and denominator adjustments, replace `* 1`

with `* n`

.

For some inputs, this algorithm will find rationals that are "equal" to your input as far as a conversion to `f64`

s or sometimes `f80`

s are concerned (the latter is not available in Rust). For other inputs, there won't be a perfect solution.

Examples:

value | f64 | f80 |
---|---|---|

`e` |
`353613854 / 130087267` |
`11468283630 / 4218945773` |

`pi` |
`325994779 / 103767361` |
`8717442233 / 2774848045` |

`sqrt2` |
`131836323 / 93222358` |
`6333631924 / 4478554083` |

ln2 | ` 210336831 / 303451903` |
`7344280705 / 10595557352` |

You can also get some "useful" approximations better than `pi ~= 22/7`

like `pi ~= 355/113`

with this approach by examining the approximations closest to `1.0`

/ closest to the switches between going left and going right.

5 Likes

You can do this in `num-rational`

with `from_float`

to create a `BigRational`

(`Ratio<BigInt>`

) with all the precision that the floating point mantissa allows. For other `Ratio<T>`

, there's also `approximate_float`

.

3 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.