精度を損なうことなく、大きな数値を迅速かつ正確に二乗するにはどうすればよいでしょうか?

精度を損なうことなく y = x^2 を迅速に計算する

問題:入力 bignum x が与えられた場合符号なし 32 ビット整数の配列として表され、y = x^2 を計算します。

初期アプローチ:質問作成者が提案した最初のアプローチでは、y = x*x を計算して複数の乗算を排除します。ただし、これには次のようないくつかの欠点があります。

カラツバ乗算:カラツバ乗算は、乗算演算を高速化する分割統治アルゴリズムです。これには 3 つの再帰ステップがあります:

入力を小さなチャンクに分割します
• 各チャンクに再帰ステップを適用します
• 結果を結合します

このアプローチにより、乗算の時間の複雑さが軽減されるため、乗算のパフォーマンスが大幅に向上します。 O(n^2) から O(n^log2(3)).

修正シェーンハーゲ シュトラッセン乗算 (NTT):次を使用して修正されたシェーンハーゲ シュトラッセン アルゴリズムNTT (Number Theoretic Transform) を使用すると、乗算演算をさらに高速化できます。周波数領域での乗算の実行に依存しています。

ただし、オーバーフローの問題により、NTT の使用には制限があります。 NTT 入力/出力ベクトル サイズは、入力 bignum の最大許容サイズによって制限されます。質問作成者が提供する実装では、NTT は乗算と二乗の両方に使用され、オペランドのサイズに応じてしきい値が異なります。

結論:

の場合数値が小さい場合、著者の高速二乗アプローチが最良の選択肢です。数値が大きい場合は、カラツバまたは NTT の乗算がより効率的になります。さまざまな最適化を通じて、NTT の乗算は、特定のしきい値を超えるとカラツバよりも高速になりました。

未解決の質問:

著者は、次のようなより効率的なアルゴリズムが存在する可能性があることを認めています。見落とされていた。特定のユースケースとデータサイズの範囲ごとに最適なアプローチを特定するには、さらなる調査と実験が必要です。

以上が精度を損なうことなく、大きな数値を迅速かつ正確に二乗するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。