Approximate LCM of reals

Question

Is there an efficient algorithm to find the approximate LCM of a list of reals? More precisely, given an epsilon, find the least L such that it is atmost epsilon away from a multiple of each real in the list.

Answer 1

I think a slightly modified version of the standard algorithm should work. The problem of finding the LCM of a list of numbers boils down to the problem of finding the GCD of two numbers. As a reminder, Euclid's algorithm is

let gcd a b =
    if b = 0 then a
    else gcd b (a % b)

The idea behind modifying this algorithm, given an epsilon for the reals, is to note that equality at 0 cannot be achieved in the general case, only bounded by epsilon. So, the base step must be if abs b < eps then a. Next, the induction step is exactly the same, except that the modulo for the reals is not defined. Several approaches are possible, the simplest of which is to define an "approximate modulo" function:

let approxMod a b =
    a - floor (a / b) * b

As far as I know, this is the usual way of doing this, but it doesn't exploit the epsilon bound. I think this is the best naive thing we can do. The modified GCD would therefore be as follows:

let gcd a b eps =
    if abs b < eps then a
    else gcd b (approxMod a b) eps

This function is close to $\mathcal O(\log(\min(a, b)))$, like its counterpart for the integer. Now you probably know how GCD and LCM are related, and how to apply them to a list of numbers. Here's some Python code if you want (I have not tested it):

import math

def modf(a, b):
    return a - math.floor(a / b) * b

def gcd(a, b, eps):
    if abs(b) < eps:
        return a
    return gcd(b, modf(a, b), eps)

def lcm(a, b, eps):
    return a * b / gcd(a, b, eps)

def lcm_list(nums, eps):
    from functools import reduce
    return reduce(lambda x, y: lcm(x, y, eps), nums)

This does not give us a total complexity of $\mathcal O(n\log(\min{\text\{\text{elems}\}}))$ operations (where $n$ is the number of elements in the list $\text{elems}$). Since the time complexity of the GCD is independent of the elements in the list, we might expect lcm_list to behave in a linear way multiplied by some function $f(\{\text{elems}\})$. Since I don't know that much about complexity analysis, I'd rather not get ahead of myself. I would be delighted if anyone could help improve this answer.