Cは内部的にKaratsubaアルゴリズムを使用して2つの整数を掛けますか？

Question

Cが2つのn-bitsの整数を乗算するとき、内部で通常のO(n^2)の乗算アルゴリズムを使用していますか、またはKaratsubaの乗算アルゴリズムのバリエーションを使用していますか？

Answer 1

いいえ、Karatsubaアルゴリズムの「ブックキープ」オーバヘッドは高すぎ、複雑すぎます。たとえ機械語レベルでブレーク・アウェイ再帰的な深さを達成したとしても、乗算器よりもはるかに多くのシリコンを消費します。ハードウェア暗号アクセラレータやFPGAは、十分に大きな値をとる価値がありますn。それでも、暗号の必要性に役立つためには、損益分岐点が高すぎるかもしれません。無料のランチはありません。

スペクトルのもう一方の端に、私たちは、漸近的に高速なアルゴリズムが実際に完済し始めるしきい値値を定義GMP libraryでgmp-mparam.hファイルで見ることができます。 「Karatsuba」は、より一般的なToom-Cookアルゴリズムの2×2のケースです。 BroadwellやSkylake CPUのようなモンスターでさえ、スレッショルドは約28 'ワード、すなわち1792ビットです。これは、（再帰的に）キャリー伝播を伴う3つの結果を一緒に戻すオーバーヘッドが原因です。これらのスレッショルドは、命令のスループットが増加するにつれて高くなります。