algorithm - 大数の掛け算

Question

アルゴリズムを分析していると、通常、乗算は 1 つのコンピューター命令であると想定されていることがわかります。しかし、この仮定は、数値のサイズ (ビット数に関して) の場合には適切ではありません。乗算の最も基本的な形式では、2 つの n ビット数の乗算は通常 O(n^2) です。これに関連して、 x^n.(x の n 乗) を計算するための複雑さ (ビット操作の観点から) は何でしょうか?

説明されたアプローチでは、複雑さはnで指数関数的であるように見えます（ただし、正確な数値はわかりません）

Answer 1

もちろん、計算の複雑さはx^n、累乗と乗算の計算に使用されるアルゴリズムに依存します。二乗によって累乗ごとのべき乗を計算する場合、O(log n) の乗算が必要です。各ステップで、1 つの数値を 2 乗するか、2 つの数値を掛けて 2 つのうちの 1 つを 2 乗します。

数字がある場合、xはΘ (n*d(x)) 桁です。最後のステップで、約桁の数を 2 乗し (そして、その数に小さい方の数字を掛ける可能性があります)、アルゴリズムは、繰り返される正方形、場合、アキュムレータ付き。d(x)x^nn/2*d(x)x^(2^k)2^k <= n < 2^(k+1)

を 1 桁の数を 2乗S(m)するコストとします( 2 つの任意の 1 桁の数を掛けるmコストと同じ場合もそうでない場合もあります)。2 乗には、およそ次の値が必要です。M(m)m

S(2^(k-1)*d(x)) + S(2^(k-2)*d(x)) + S(2^(k-3)*d(x)) + ...

仕事。以来S(m) >= m、それは と の間S(2^(k-1)*d(x))です2*S(2^(k-1)*d(x))。そのため、二乗の作業は最後のステップによって支配されます。アキュムレータを使用したan の乗算の場合x^(2^s)も同様で、最終的な乗算が作業を支配します。最終的なアキュムレータは、繰り返される二乗とほぼ同じ大きさになる可能性があるため、二乗を繰り返すことによって - 乗xする総コストは次のようになります。n

Θ(M(2^k*d(x)),

ですΘ(M(n*d(x)))。単純な乗算により、M(m) = O(m^2)総コストは になりO(n^2*d(x)^2)ます。より高度な乗算アルゴリズム (からつば、Toom-Cook、Schönhage-Strassen など) を使用すると、複雑さが大幅に軽減され、O(n*d(x)*log (n*d(x)) * log log (n*d(x))).

xをn段階的に乗じてべき乗を計算する場合、 は- 桁の数と - 桁の数をM(m,k)掛けるコストを示します。要因の 1 つが常にであるため、合計コストはmkx

M(d(x),d(x)) + M(d(x),2*d(x)) + M(d(x),3*d(x)) + ... + M(d(x),(n-1)*d(x))

費用が の教科書のアルゴリズムではM(m,k) = m*k、これは合計するとn*(n-1)/2*d(x)^2になるため、総費用は再び になりΘ(n^2*d(x)^2)ます。ただし、二乗を繰り返すことによる累乗よりも定数係数が大きくなります。

ここで数回繰り返した後に発生するように、長さが大きく異なる数値を乗算する場合、私の知る限り、コストM(m,k)を大幅に削減することはできません。 ) baseでは、 が十分に大きい場合、より優れたアルゴリズムを使用して「数字」を乗算するコストを削減できますが、係数を削減することはできません。したがって、このアルゴリズムは の複雑さを持ち、 の因数は消去できません。Θ(m*k)m < krr*m <= k < (r+1)*mb^mmrO(n^2*M(d(x)))n^2

Answer 2

ウィキペディアには、さまざまな乗算アルゴリズムの複雑な時間の概要があります。

あなたの質問に答えるには、2 つの m 桁の数 (複雑さは O( m^2 ) です) を乗算する単純な教科書の方法と、数値自体を n 回掛けて累乗する単純な方法を想定すると、次のようになります。 n 回の乗算、つまり O( n * m^2 ) または単純に O( nm^2 ) の複雑さ