9

私は周りを見回して、答えのある他の質問を見つけましたが、この特定の質問の範囲に対処するものはありません。

効率的な方法で広範囲の数値の LCM を計算する必要があります。他の質問は、このアルゴリズムが処理しなければならないほど大きな数値範囲を扱っていないため、あまり詳しく調べませんでした。

私が今持っているコードは、約 90 秒で 1 から 350000 までのすべての数値の LCM を計算できます。(結果の数値は、10 進数で 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 ループとは異なり、この関数は [lower, upper) ではなく [lower, upper] に対して動作することに注意してください。この動作は意図的なものです。

数学をサポートするビットは、いくつかの数値セットの 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 を計算するより効率的な方法はありますか?

誰かが提案するアルゴリズムが非常にメモリを大量に消費するかどうかは気にしません。この場合、時間のパフォーマンスはメモリのパフォーマンスよりもはるかに重要です (また、より高価です)。

これは宿題の質問ではありません。

質問

非常に大きな範囲の数値の最小公倍数を計算する最も効率的な方法は何ですか? このアルゴリズムは、法外に広い範囲の数値を操作する必要があるため、慎重に最適化する必要があります。

補遺1

密接に関連する質問は次のとおりです。ある BigInteger の対数を計算する最も効率的な方法は何ですか (別の BigInteger を底にします)。結果の値は、最も近い整数に切り捨てられます。

4

2 に答える 2

3

これがアルゴリズムのレイアウトです。私はあなたが常に1から始めると仮定します：

  1. 範囲内の素数を見つけます。Eratosthenes sieve を 350000 に使用できます。より大きな範囲の数値を使用するには、セグメント化された sieveが必要です。

  2. 各素数 p について、対数関数を使用して、peが範囲内にある最大の指数eを見つけます。最小公倍数にp eを掛けます。(最適化の詳細は実装次第です)

なぜそれが正しいのですか？

  • p が素数で、e >= 1である形式 p eの数については、ステップ 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 から n までのすべての i に対して)。以来 p i e i | LCM、前の引数により、N | LCM。
于 2012-08-15T22:04:38.213 に答える
2

これは@nhahtdhの回答の一般化です

最初のステップでは、上限以下のすべての素数を見つけます。

次に、各素数 p を取り、底 p 表記で下限と上限の両方を書き留めます。2 つの数値で異なる最大桁は、LCM に含める必要がある p の指数です。下限が1の場合、これは他の答えと自明です。

このアルゴリズムの複雑さは範囲の長さには依存せず、上限の大きさのみに依存することに注意してください。

于 2012-08-15T23:03:27.313 に答える