xcode - Swift中 double LCM的算法

Question

我需要将 double 组转换为整数，同时保持它们的比率相同并尽可能简单。例如 [0.7, 0, -0.7] 应该变成 [1, 0, -1] 而 [24, 12, 0] 应该变成 [2, 1, 0]。我不确定这是否涉及获得 double 的最小公倍数，如果是这样，将如何完成？

Answer 1

(代码已针对 Swift 4 及更高版本更新。)

首先， float 没有GCD和LCM。你 必须先将输入转换为有理数。

这并不像听起来那么容易，因为像 0.7 这样的小数不能精确地表示为二进制 float ，并且 将在 Double 中存储为类似 0.69999999999999996 的内容。 因此，如何从那里到达 7/10 并不是很明显。

因此有必要指定一个精度。那么你也能 利用 Continued Fractions 有效地创建一个(有限或无限)分数序列h_n/k_n，它们是给定实数的任意良好近似值x.

这里是this JavaScript implementation的翻译 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.7)      // (7, 10) i.e. 7/10
rationalApproximationOf(0.142857) // (1, 7)  i.e. 1/7

我已将默认精度设置为 1.0E-6，但您可以调整它 满足您的需求。

然后您需要 GCD(最大公约数)的函数 和 LCM(最小公倍数)。下面是简单的实现:

// GCD of two numbers:
func gcd(_ a: Int, _ b: Int) -> Int {
    var (a, b) = (a, b)
    while b != 0 {
        (a, b) = (b, a % b)
    }
    return abs(a)
}

// GCD of a vector of numbers:
func gcd(_ vector: [Int]) -> Int {
    return vector.reduce(0, gcd)
}

// LCM of two numbers:
func lcm(a: Int, b: Int) -> Int {
    return (a / gcd(a, b)) * b
}

// LCM of a vector of numbers:
func lcm(_ vector : [Int]) -> Int {
    return vector.reduce(1, lcm)
}

有了所有这些实用程序，您的功能现在可以实现为

func simplifyRatios(_ numbers : [Double]) -> [Int] {
    // Normalize the input vector to that the maximum is 1.0,
    // and compute rational approximations of all components:
    let maximum = numbers.map(abs).max()!
    let rats = numbers.map { rationalApproximationOf($0/maximum) }

    // Multiply all rational numbers by the LCM of the denominators:
    let commonDenominator = lcm(rats.map { $0.den })
    let numerators = rats.map { $0.num * commonDenominator / $0.den }

    // Divide the numerators by the GCD of all numerators:
    let commonNumerator = gcd(numerators)
    return numerators.map { $0 / commonNumerator }
}

例子:

simplifyRatios([0.7, 0, -0.7])   // [1, 0, -1]
simplifyRatios([24, 12, 0])      // [2, 1, 0]
simplifyRatios([1.3, 0.26, 0.9]) // [65, 13, 45]