Split f64 into numerator/denominator?

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 :slight_smile:

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 f64s or sometimes f80s 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.