How do I exactly convert a float to a fraction?

Question

I was searching how to convert a float to the simplest fraction that would convert back to it and found this answer.

Problem is, the Python implementation given relies on the as_integer_ratio facility in the python standard library, which isn't present in Rust. I asked about this in a comment and found out about f64::frexp but I'm not sure I understand how it works, as its documentation is quite cryptic (to me at least):

Breaks the number into a normalized fraction and a base-2 exponent, satisfying:
self = x * 2^exp
0.5 <= abs(x) < 1.0

And on top of that, it's an unstable feature.

What should I do?

Answer 1

The complicated thing about float-to-fraction conversion is that all floats are already rationals with a power-of-two denominator, but that probably isn't so useful. What you are looking for is "best rational approximation", to find the closest rational to a target float value within some max denominator.

The algorithm (described in the link) has some clever continued fractions math behind it, but not too difficult to put into code. Here is a small C library that implements it:

• Header: number_util.h
• Source: number_util.c
• Unit test: number_util_test.c

Example use:

#include "number_util.h"

int numerator;
int denominator;
RationalApproximation(M_PI, 1000000, NULL, &numerator, &denominator);
printf("%d/%d\n", numerator, denominator); 
// Prints: 3126535/995207 (= 3.14159265...)

This is hopefully straightforward to port or wrap for use in other languages.

Answer 2

Algorithm apart, I guess the easiest way would be to use something working already, like the fraction crate:

From the example

use std::str::FromStr;
use fraction::{Fraction, Sign};  // choose the type accordingly with your needs (see prelude module docs)

fn main() {
    // There are several ways to construct a fraction, depending on your use case

    let f = Fraction::new(1u8, 2u8);  // constructs with numerator/denominator and normalizes the fraction (finds least common denominator)
    assert_eq!(f, Fraction::new_generic(Sign::Plus, 1i32, 2u8).unwrap());  // with numerator/denominator of different integer types
    assert_eq!(f, Fraction::from(0.5));  // convert from float (f32, f64)
    assert_eq!(f, Fraction::from_str("0.5").unwrap());  // parse a string

    // Raw construct with no extra calculations.
    // Most performant, but does not look for common denominator and may lead to unexpected results
    // in following calculations. Only use if you are sure numerator/denominator are already normalized.
    assert_eq!(f, Fraction::new_raw(1u64, 2u64));
}