Swift中双精度的LCM算法

Question

我需要将一个双精度数组转换为整数,同时保持它们的比率相同并尽可能简单.例如,[0.7,0,-0.7]应该变为[1,0,-1]并且[24,12,0]应该变为[2,1,0].我不确定这是否会涉及获得双打的最小公倍数,如果是这样的话怎么办呢？

Answer 1

首先,浮点数没有GCD或LCM.您必须先将输入转换为有理数.

这并不像听起来那么容易,因为小数部分0.7不能完全表示为二进制浮点数,而是存储为类似于0.69999999999999996a的东西Double.所以如何从那里到达并不是完全明显的7/10.

因此有必要指定精度.然后,您可以使用 连续分数 来有效地创建(有限或无限)分数h _n/k _n序列,它们是给定实数x的任意良好近似值.

以下是这个JavaScript实现 到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(var a : Int, var b : Int) -> Int {
    while b != 0 {
        (a, b) = (b, a % b)
    }
    return abs(a)
}

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

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

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

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

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 = maxElement(map(numbers) { abs($0) } )
    let rats = map(numbers) { rationalApproximationOf($0/maximum) }

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

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