Swift中双重LCM的算法 [英] Algorithm for LCM of doubles in Swift

问题描述

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

I need to turn an array of doubles to ints while keeping their ratios the same and being as simple as possible. For example [0.7, 0, -0.7] should become [1, 0, -1] and [24, 12, 0] should become [2, 1, 0]. I'm not certain if this would involve getting the least common multiple of the doubles or not, and how would this be done if so?

推荐答案

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

First of all, there is no GCD or LCM for floating point numbers. You have to convert the input to rational numbers first.

这并不像听起来那么容易， 0.7 不能像二进制浮点数一样被表示，而
将被存储为 0.69999999999999996 一个双人。
所以这是不是很明显如何从那里得到 7/10 。

This is not as easy as it sounds, because decimal fractions like 0.7 cannot be represented exactly as a binary floating point number and would be stored as something like 0.69999999999999996 in a Double. So it is not completely obvious how to get from there to 7/10.

它是因此必须指定精度。那么你可以
使用
继续分数
有效地创建对于给定实数的任意良好近似的分数的有限或无限序列 n

It is therefore necessary to specify a precision. Then you can use Continued Fractions to efficiently create a (finite or infinite) sequence of fractions h_n/k_n that are arbitrary good approximations to a given real number x.

以下是此JavaScript实现的翻译

Here is a translation of this JavaScript implementation to 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，但您可以根据需要调整
。

I have set the default precision to 1.0E-6, but you can adjust that to your needs.

然后你需要GCD（最大公约数）
和LCM（最低公倍数）的函数。这里是简单的实现：

Then you need functions for the GCD (greatest common divisor) and LCM (lowest common multiple). Here are simple implementation:

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

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

With all these utilities, your function can now be implemented as

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]

这篇关于Swift中双重LCM的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！