Swift 中双打的 LCM 算法

Question

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

Answer 1

（已为 Swift 4 及更高版本更新代码。）

首先浮点数没有GCD和LCM。你必须先将输入转换为 有理数 数字。

这并不像听起来那么容易，因为像 0.7 这样的小数不能精确地表示为二进制浮点数，并且将在 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([=13=]/maximum) }

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

    // Divide the numerators by the GCD of all numerators:
    let commonNumerator = gcd(numerators)
    return numerators.map { [=13=] / 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]

Swift 中双打的 LCM 算法

Algorithm for LCM of doubles in Swift

double

int

xcode

swift