Swift中的小数到分数转换

Question

我正在构建一个计算器，并希望它自动将每个小数
转换为分数。因此，如果用户计算出答案
为“ 0.333333…” 的表达式，它将返回“ 1/3”。对于“ 0.25”，它将返回“ 1/4”。
使用GCD（小数到小数
转换），我已经弄清楚了如何将任何有理数，终止
小数转换为小数，但这不适用于任何重复的小数
（如.333333）。

堆栈溢出的所有其他功能在Objective-C中。但是我需要
在我的快速应用程序中添加一个功能！因此，此版本的翻译版本会很不错！

关于如何将有理数或重复数/无理
数的小数转换为分数的任何想法或解决方案（例如，将“ 0.1764705882…”转换为3/17）都将是
不错的选择！

Answer 1

如果你想显示的计算，有理数的结果的话，唯一的100％正确的解决办法是使用合理的算术在所有
的计算，即所有中间值存储为一对整数(numerator, denominator)，和所有加法，乘法，除法，等
有使用有理数规则完成。

一旦将结果分配给二进制浮点数（例如）Double，信息就会丢失。例如，

let x : Double = 7/10

在商店x的近似的0.7，因为该数量不能被精确地作为表示Double。从

print(String(format:"%a", x)) // 0x1.6666666666666p-1

可以看到x拥有价值

0x16666666666666 * 2^(-53) = 6305039478318694 / 9007199254740992
                           ≈ 0.69999999999999995559107901499373838305

So a correct representation of x as a rational number would be
6305039478318694 / 9007199254740992, but that is of course not what you
expect. What you expect is 7/10, but there is another problem:

let x : Double = 69999999999999996/100000000000000000

assigns exactly the same value to x, it is indistinguishable from 0.7
within the precision of a Double.

So should x be displayed as 7/10 or as
69999999999999996/100000000000000000 ?

As said above, using rational arithmetic would be the perfect solution. If
that is not viable, then you can convert the Double back to a rational
number with a given precision. (The following is taken from Algorithm for
LCM of doubles in
Swift.)

Continued Fractions are an
efficient method to create a (finite or infinite) sequence of fractions h
n/kn that are arbitrary good approximations to a given real number x , and
here is a possible implementation in Swift:

typealias Rational = (num : Int, den : Int)

func rationalApproximationOf(x0 : Double, withPrecision eps : Double = 1.0E-6) -> Rational {
    var x = x0
    var a = floor(x)
    var (h1, k1, h, k) = (1, 0, Int(a), 1)

    while x - a > eps * Double(k) * Double(k) {
        x = 1.0/(x - a)
        a = floor(x)
        (h1, k1, h, k) = (h, k, h1 + Int(a) * h, k1 + Int(a) * k)
    }
    return (h, k)
}

Examples:

rationalApproximationOf(0.333333) // (1, 3)
rationalApproximationOf(0.25)     // (1, 4)
rationalApproximationOf(0.1764705882) // (3, 17)

The default precision is 1.0E-6, but you can adjust that to your needs:

rationalApproximationOf(0.142857) // (1, 7)
rationalApproximationOf(0.142857, withPrecision: 1.0E-10) // (142857, 1000000)

rationalApproximationOf(M_PI) // (355, 113)
rationalApproximationOf(M_PI, withPrecision: 1.0E-7) // (103993, 33102)
rationalApproximationOf(M_PI, withPrecision: 1.0E-10) // (312689, 99532)

Swift 3 version:

typealias Rational = (num : Int, den : Int)

func rationalApproximation(of x0 : Double, withPrecision eps : Double = 1.0E-6) -> Rational {
    var x = x0
    var a = x.rounded(.down)
    var (h1, k1, h, k) = (1, 0, Int(a), 1)

    while x - a > eps * Double(k) * Double(k) {
        x = 1.0/(x - a)
        a = x.rounded(.down)
        (h1, k1, h, k) = (h, k, h1 + Int(a) * h, k1 + Int(a) * k)
    }
    return (h, k)
}

Examples:

rationalApproximation(of: 0.333333) // (1, 3)
rationalApproximation(of: 0.142857, withPrecision: 1.0E-10) // (142857, 1000000)

Or – as suggested by @brandonscript – with a struct Rational and an
initializer:

struct Rational {
    let numerator : Int
    let denominator: Int

    init(numerator: Int, denominator: Int) {
        self.numerator = numerator
        self.denominator = denominator
    }

    init(approximating x0: Double, withPrecision eps: Double = 1.0E-6) {
        var x = x0
        var a = x.rounded(.down)
        var (h1, k1, h, k) = (1, 0, Int(a), 1)

        while x - a > eps * Double(k) * Double(k) {
            x = 1.0/(x - a)
            a = x.rounded(.down)
            (h1, k1, h, k) = (h, k, h1 + Int(a) * h, k1 + Int(a) * k)
        }
        self.init(numerator: h, denominator: k)
    }
}

Example usage:

print(Rational(approximating: 0.333333))
// Rational(numerator: 1, denominator: 3)

print(Rational(approximating: .pi, withPrecision: 1.0E-7))
// Rational(numerator: 103993, denominator: 33102)