DWORD 配列として表される大きな整数を二乗するための最速のアルゴリズムは何ですか?

高速な bignum 二乗計算

この記事は、符号なし DWORD の動的配列として表現される bigint の y = x^2 を計算する最速の方法を決定することを目的としています。

問題ステートメント

bigint x の表現を次のように指定すると、 DWORD の配列:

DWORD x[n+1] = { LSW, ......, MSW };

ここで:

• n 1 は使用される DWORD の数です
• x = x[0] x[1]

精度を失わずに、できるだけ早く y = x^2 の値を見つけます。

仮定:

• 計算は C と 32 ビット整数演算を使用して実行されます。 carry.

単純なアプローチ (O(n^2) 乗算)

単純なアプローチでは、x を単独で乗算する必要があり、O(n^2) 時間がかかります。これは次のように表現できます。

y = x * x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)

積を展開すると、次のようになります。

y0     = x0*x0
y1     = x1*x0 + x0*x1
y2     = x2*x0 + x1*x1 + x0*x2
y3     = x3*x0 + x2*x1 + x1*x2
...
y(2n-3) = xn(n-2)*x(n  ) + x(n-1)*x(n-1) + x(n  )*x(n-2)
y(2n-2) = xn(n-1)*x(n  ) + x(n  )*x(n-1)
y(2n-1) = xn(n  )*x(n  )

カラツバ乗算

カラツバ アルゴリズムを使用すると、乗算を高速化することができます。 O(n^log2(3))。有望に見えますが、アルゴリズムの再帰的な性質により、大きな数に対して重大なパフォーマンス オーバーヘッドが発生する可能性があります。

最適化されたシェーンハーゲ シュトラッセン乗算

シェーンハーゲ シュトラッセン アルゴリズムは、O(分割統治法を使用した nlog(n)(log(log(n)))) アプローチ。ただし、このアルゴリズムには、オーバーフローの問題と符号なし整数のモジュラー演算の必要性による実用的な制限があります。

結論

数値が小さい場合は、単純な O(n^2) 乗算アプローチが使用されます。最も効率的です。数値が大きい場合は、Karatsuba 乗算アルゴリズムをお勧めします。 FFT (高速フーリエ変換) や NTT (数論的変換) を使用するなど、パフォーマンスを向上させるためにさらに最適化を検討できます。

以上がDWORD 配列として表される大きな整数を二乗するための最速のアルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。