将浮点数转换为分数

1. Introduction

In this tutorial, we’ll show how to convert a float into a fraction. Additionally, we’ll cover the case where we need to use an approximate solution or restrict the denominator to get a human-readable fraction.

2. Floats and Fractions

In this problem, we have a float and want to convert it into a fraction where .

For instance, if we have a float , the fraction we’d like to get is . With , we expect .

We’ll focus on the case where because we can handle negative floats in the same way. Additionally, we’ll restrict to since covering the case is straightforward: we convert to a fraction and add it to .

3. Exact Fractions

Perhaps the simplest way to approach this problem is to convert into a fraction whose denominator is a power of 10. For example:

   

We do that by repeatedly multiplying with 10 until its decimal part gets equal to zero:

algorithm ConvertFloatToPowerOfTenFraction(x):
    // INPUT
    //    x = the float in [0, 1] to convert into a fraction
    // OUTPUT
    //    (p, 10^n) = the fraction form p /10^n of x,
    //        where the denominator is a power of ten and p >= 0

    n <- 0
    p <- x

    while p - floor(p) > 0:
        p <- 10 * p
        n <- n + 1

    return p / 10^n

3.1. Example

For instance, this is how our algorithm would handle :

   

It stops when the decimal part gets equal to zero and outputs as the result.

3.2. The Coprime Numerator and Denominator

However, the numerator and denominator in the above example aren’t coprime. Sometimes, we want to simplify the fraction as much as possible. We do that by dividing the numerator and denominator with their greatest common divisor (GCD). For instance, since the GCD of 35 and 100 is 5, we divide both by 5 and get as the fraction form of .

We can find the GCD with the Euclidean Algorithm. Division with the GCD ensures that the output fraction’s numerator and denominator are coprime:

algorithm ConvertFloatToCoprimeFraction(x):
    // INPUT
    //    x = the float to convert into a fraction, where x is in [0, 1]
    // OUTPUT
    //    (p, q) = the fraction form p / q of x with p >= 0 and q > 0,
    //        where p and q are coprime

    n <- 0
    p <- x

    while p - floor(p) > 0:
        p <- 10 * p
        n <- n + 1

    r <- find the GCD of p and 10^n using the Euclidean Algorithm
    p <- p / r
    q <- 10^n / r

    return (p, q)

4. Approximate Fractions

However, floating-point numbers can be inaccurate. For example, even though we set to , the actual value stored in a float variable could be or . That would cause the above algorithms to output unreadable fractions such as:

   

4.1. Truncating Input Floats to the First Few Significant Digits

We can avoid such fractions by considering only the first few digits after the dot. If we take into account only digits, we can get a better-looking fraction whose absolute error is less than . However, the precision we require will depend on the use case. So, could give us acceptable fractions in one case, whereas even would make them imprecise in another.

To get approximate fractions, we need to tweak the above approach a bit:

algorithm ConvertFloatToApproximateFraction(x, m):
    // INPUT
    //    x = the float to convert into a fraction, x in [0, 1]
    //    m = the number of decimal digits to consider
    // OUTPUT
    //    (p, q) = the fraction form p / q of x,
    //        where p and q are coprime and |x - p/q| <= 10^(-m)

    n <- 0
    p <- x

    while p - floor(p) > 0 and n ≤ m:
        p <- 10 * p
        n <- n + 1

    r <- find the GCD of p and 10^n using the Euclidean Algorithm
    p <- p / r
    q <- 10^n / r

    return (p, q)

How would this algorithm handle with ? The while-loop would stop when . At that point, would be equal to . The Euclidean Algorithm would output as the GCD of and . After dividing both by , we’d get as the final result.

4.2. Restricting the Denominator

Sometimes, even the above approach can fail us. For instance, with and , we get the fraction . The problem is that it isn’t human-friendly. Humans don’t have an understanding of , so fractions with such denominators are confusing.

Instead, a better solution would be or . One way to handle this is to set to a low value: 1, 2, or 3. But, even that could give us “unreadable” fractions such as or .

We can address this issue by restricting the denominator to a human-friendly integer such as 10, 100, or 20. To do so, we first let the algorithms above give us a fraction (exact or approximate). Then, we post-process it by changing the denominator into the desired number.

Formally, if is our fraction, and we want to use the denominator , we transform the fraction as follows:

(1)  

Then, we round the numerator to the nearest integer and get a fraction with the denominator we wanted.

4.3. Example

Let’s say that we got using one of the above methods. To change the denominator to , we apply rule (1):

   

As we can see, looks human-friendlier than .

However, we paid for readability with precision. When we rounded 42.0289 to 42, we introduced an additional error. So, this method is adequate only if such a trade-off is acceptable.

5. Conclusion

In this article, we showed four ways of converting a float into a fraction: two exact techniques and two approximate. Which one we choose depends on our requirements regarding precision and readability.