I looked around and found other questions that had answers but none of them address the scope of this particular question., including this question, and also this one.

I have to compute the LCM of large ranges of numbers in an efficient way. I didn’t look too in-depth at those other questions because they don’t deal with ranges of numbers that are as large as the ones this algorithm must process.

The code I’ve got right now can calculate the LCM of every number between 1 and 350000 in about 90 seconds. (The resulting number is some 76000 decimal digits long). I hope to eventually be able to scale it over ranges that are millions or maybe even billions of elements long.

It will probably be paralellized eventually. With some algorithms this won’t be hard at all, for others it will be trickier (if, for example, the algorithm uses the currently generated LCM to compute primality for other parts of its computation)

Here it is:

public static BigInteger getLCMOfRange(BigInteger lower, BigInteger upper)
{
    BigInteger M = BigInteger.ONE;
    BigInteger t;
    
    // long l = System.currentTimeMillis();
    // System.out.println("Calculating LCM of numbers up to " + upper + "...");
    for (; lower.compareTo(upper) != 1; lower = lower.add(BigInteger.ONE))
    {
        t = M.gcd(lower);
        if (t.compareTo(lower) == 0)
            continue;
        M = M.multiply(lower).divide(t);
    }
    // System.out.println("Done.  Took " + (System.currentTimeMillis() - l) + " milliseconds.  LCM is " + M.bitCount()+ " bits long.");
    return M;
}

Note that unlike a typical for loop, this function operates over [lower, upper] instead of [lower, upper). This behavior is intentional.

A bit of supporting math is that the LCM of some set of numbers product of the set of prime factors from which any one of the numbers can be produced without requiring any outside of the pool. If my range is [1,20], I can represent that in the following way:

1: 1         6:  3*2      11: 11       16: 2^4
2: 2         7:  7        12: 3*2^2    17: 17
3: 3         8:  2^3      13: 13       18: 3^2*2
4: 2^2       9:  3^2      14: 7*2      19: 19
5: 5         10: 5*2      15: 5*3      20: 5*2^2

LCM{[1,20]}: 2^4*3^2*5*7*11*13*17*19 = 232792560

Are there any more efficient ways to compute an LCM over such a large range?

I don’t care if the algorithm someone suggests is very memory-heavy, time performance is much more important (and also more expensive) than memory performance in this case.

This is not a homework question.

Question

What is the most efficient way to calculate the LCM of a very large range of numbers? This algorithm needs to operate on prohibitively wide ranges of numbers and must thus be carefully optimized.

Addendum 1

A closely related question is: What’s the most efficient way to calculate the logarithm of one BigInteger (base another BigInteger)? The resulting value can be truncated to the nearest integer.

Answer

This is the layout of the algorithm. I assume that you always start from 1:

Find prime numbers in the range. You can use Eratosthenes sieve for 350000. For bigger range of number, you’d need segmented sieve.
For each prime number p, use logarithmic function to find the largest exponent e that p^e is within the range. Multiply p^e to the LCM. (The optimization details is up to your implementation)

Why is it correct?

For numbers in the form p^e where p is prime, and e >= 1, due to step 2, has been include in the LCM, so p^e | LCM.
Other numbers will have the form N = p₁^e₁p₂^e₂…p_n^e_n (where p_i are pairwise distinct primes numbers and e_i >= 1), which is larger or equal to p_i^e_i (for all i from 1 to n). Since p_i^e_i | LCM, due to previous argument, N | LCM.

What’s the most efficient algorithm to calculate the LCM of a range of numbers?

Question

Addendum 1

Advertisement

Answer