Function libslide::math::fraction::dec2frac

pub fn dec2frac(num: f64, max_iter: u64) -> Result<(i64, u64), Dec2FracError>

Converts a decimal number to its irreducible fractional representation by walking the Stern-Brocot tree. This is equivalent to a binary search of the Farey sequence.

Algorithm

Say we are looking for a number A, where A = Whole + Decimal, Whole ∈ W, and Decimal ∈ [0, 1). Then if we can find T and B such that Decimal = T / B, A = Whole + Decimal = (Whole * B) / B + (T / B) = (Whole * B + T) / B

To find T and B we perform a binary search of irreducible fractions starting with the range [0, 1]. On each iteration of the search, we compute the mediant of the range.

mediant(A / B, C / D) = (A + C) / (B + D)

The mediant of two fractions is guaranteed to be between those two fractions, though is not always the median of those two fractions.

In the Stern-Brocot tree, the mediant of two sibling tree nodes is an irreducible fraction.

                      * ~ T / B
0 / 1 ----------------------|---------------------- 1 / 1
                          1 / 2 ~ mediant

We then bisect the search to the medaint-bound range the decimal we are interested in.

                                   * ~ T / B
0 / 1 -----------------------------|--------------- 1 / 2
                                 1 / 3 ~ mediant

We stop when the mediant is equivalent to the decimal searched for.

Failure

This algorithm is iterative and convergent, but terminates after max_iter iterations. If a fractional representation equivalent to the decimal at floating point precision cannot be found after max_iter, nothing is returned.

Examples

assert_eq!(dec2frac(0.5, 10), Some((1, 2)))
assert_eq!(dec2frac(3.14159265358979323, 10), None)
assert_eq!(dec2frac(-3.142857142857142857, 100_000), Some((-22, 7)))