ios - Swift 中小数到分数的转换

Question

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

与此有关的堆栈溢出的所有其他函数都在 Objective-C 中。但我需要在我的 swift 应用程序中添加一个函数!所以这个的翻译版本( https://stackoverflow.com/a/13430237/5700898 )会很好!

关于如何将有理数或重复/无理数小数转换为分数(即将“0.1764705882...”转换为 3/17)的任何想法或解决方案都很棒!

Answer 1

如果要将计算结果显示为有理数那么唯一 100% 正确的解决方案是在所有计算中使用有理算术，即所有中间值都存储为一对整数(分子，分母)，并且所有加法、乘法、除法等是使用有理数规则完成的数字。

一旦结果被分配给二进制 float 例如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

因此，x 作为有理数的正确表示是6305039478318694/9007199254740992，但这当然不是你期望的。您期望的是 7/10，但还有另一个问题:

let x : Double = 69999999999999996/100000000000000000

为x分配完全相同的值，它与0.7 精度为 Double。

那么x应该显示为7/10还是69999999999999996/100000000000000000？

如上所述，使用有理算术将是完美的解决方案。如果这不可行，那么您可以将 Double 转换回具有给定精度的有理数。(以下内容摘自Algorithm for LCM of doubles in Swift。)

Continued Fractions是创建(有限或无限)分数序列 h_n/k_n 的有效方法，这些分数是给定实数的任意良好近似值数字x，下面是 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)
}

示例:

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

默认精度为 1.0E-6，但您可以根据需要进行调整:

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版本:

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)
}

示例:

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

或者 - 正如 @brandonscript 所建议的 - 使用 struct Rational 和初始化器:

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)
    }
}

使用示例:

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

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