Какой самый эффективный алгоритм для вычисления LCM диапазона чисел?

Я огляделся и нашел другие вопросы, на которые были даны ответы, но ни один из них не касался объема этого конкретного вопроса, включая этот вопрос, а также этот.

Я должен вычислить LCM больших диапазонов чисел эффективным способом. Я не слишком подробно изучил эти другие вопросы, потому что они не имеют дело с диапазонами чисел, которые столь же велики, как те, которые должен обрабатывать этот алгоритм.

Код, который я получил прямо сейчас, может вычислить LCM каждого числа от 1 до 350000 примерно за 90 секунд. (Итоговое число составляет около 76000 десятичных цифр). Я надеюсь, что в конечном итоге смогу масштабировать его по диапазонам, которые составляют миллионы или даже миллиарды элементов.

Это, вероятно, будет парализовано в конце концов. С некоторыми алгоритмами это совсем не сложно, для других это будет сложнее (если, например, алгоритм использует текущий сгенерированный LCM для вычисления первичности для других частей своего вычисления)

Вот:

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

Обратите внимание, что в отличие от типичного цикла for, эта функция работает над [нижний, верхний] вместо [нижний, верхний). Такое поведение является преднамеренным.

Поддержка математики состоит в том, что LCM некоторого набора чисел является продуктом набора простых факторов, из которого может быть произведено любое из чисел, не требуя какого-либо за пределами пула. Если мой диапазон [1,20], я могу представить это следующим образом:

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

Существуют ли более эффективные способы вычисления LCM в таком большом диапазоне?

Мне все равно, если алгоритм, который кто-то предлагает, очень загружает память, производительность в этом случае гораздо важнее (а также дороже), чем производительность памяти в этом случае.

Это не домашнее задание.

Вопрос

Каков наиболее эффективный способ расчета LCM для очень большого диапазона чисел? Этот алгоритм должен работать в непомерно широких диапазонах чисел и поэтому должен быть тщательно оптимизирован.

Приложение 1

С этим тесно связан вопрос: как наиболее эффективно рассчитать логарифм одного BigInteger (основать другой BigInteger)? Полученное значение может быть усечено до ближайшего целого числа.

Источник

3 ответа

Решение

Это макет алгоритма. Я предполагаю, что вы всегда начинаете с 1:

  1. Найти простые числа в диапазоне. Вы можете использовать сито Eratosthenes для 350000. Для большего диапазона числа вам понадобится сегментированное сито.

  2. Для каждого простого числа p используйте логарифмическую функцию, чтобы найти наибольший показатель e, который находится в диапазоне. Умножьте p на LCM. (Детали оптимизации зависят от вашей реализации)

Почему это правильно?

  • Для чисел в форме p e, где p простое, а e >= 1, из-за шага 2 было включено в LCM, поэтому p e | LCM.
  • Другие числа будут иметь вид N = p 1 e 1 p 2 e 2... p n e n (где p i - попарно различные простые числа и e i > = 1), которое больше или равно p i e i (для всех я от 1 до п). Так как p i e i | LCM, из-за предыдущего аргумента, N | LCM.
Источник

Это обобщение ответа @nhahtdh

Первый шаг, найдите все простые числа, которые меньше или равны верхней границе.

Затем возьмите каждое простое число p и запишите нижнюю и верхнюю границу в базовой записи p. Наибольшая цифра, которая отличается в этих двух числах, - это показатель степени p, который нужно включить в свой LCM. Если нижняя граница равна 1, это тривиально так же, как другой ответ.

Обратите внимание, что сложность этого алгоритма не зависит от длины диапазона, только от величины верхней границы.

Источник

Вместо простого генератора и некоторых явных средств для определения наибольших мощностей при пределе  n  (350000)
попробуйте модифицированный SoE:

Используйте "все" ( ~0) или -1 для MULTIPRIME: имеет более одного простого делителя,
0 или 1 для CANDIDATE.
Для каждого натурального числа до  l  =sqrt(n) оставьте в сите целое число, достаточно большое, чтобы вместить l , инициализированное равным 0 для первого кандидата .
Установите решето в кратных простому числу p до p , если оно равно нулю, иначе в MULTIPRIME, если оно не равно p .

Наименьшее общее кратное — это произведение всех элементов решета > КАНДИДАТ, а не МНОЖЕСТВЕННОЕ (> КАНДИДАТ, если КАНДИДАТ > МНОЖЕСТВО).

(В зависимости от системы памяти и ЦП, переназначение значений или отказ от них

          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;

может быть медленнее.)

Источник
Другие вопросы по тегам