Algorithm for LCM of doubles in Swift

问题:

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?

回答1:

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

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.

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.

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

Examples:

rationalApproximationOf(0.7)      // (7, 10) i.e. 7/10
rationalApproximationOf(0.142857) // (1, 7)  i.e. 1/7

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

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

Examples:

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]