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

user_1462604 0
Viewed 4146

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.

lcm biginteger optimization algorithm java
3 Answers

Instead of a prime generator and some explicit means to determine largest powers under the limit n (350000),
Try a modified SoE:

Use "all ones" (~0) or -1 for MULTIPRIME: has more than one distinct prime factor,
0 or 1 for CANDIDATE.
For each natural number up to l = sqrt(n), keep in sieve an integer large enough to hold l, initialised to 0 for prime candidate.
Set sieve at multiples of a prime p to p if zero, else to MULTIPRIME if not equal to p.

The Least Common Multiple is the product of all elements of sieve > CANDIDATE and not MULTIPRIME (> CANDIDATE if CANDIDATE > MULTIPRIME).

(Depending on memory system and CPU, re-assigning values or avoiding it

    sieve[p] = sieve[p] | p == p ? p : MULTIPRIME;
// or
    if (sieve[p] != MULTIPRIME)
        if (sieve[p] == CANDIDATE)
            sieve[p] = p;
        else if (sieve[p] != p)
            sieve[p] = MULTIPRIME;

may be slower.)

user_37896650
Related