2つの数値の乗算は一定時間アルゴリズムですか？

Question

私が書くと仮定、

int a = 111; 
int b = 509; 
int c = a * b; 

だから、 '* b' を計算するための時間の複雑さは何ですか？乗算演算はどのように実行されますか？この機能コンパイル

Answer 1

：gcc -O3 -march=native -m64 -fomit-frame-pointer -Sで

int f(int a, int b) { 
    return a * b; 
} 

は私に次のアセンブリを与える：

f: 
    movl %ecx, %eax 
    imull %edx, %eax 
    ret 

最初の命令（movl）は最初の引数を読み込み、2番目の命令（imull）は、第二のロード最初の引数と掛け合わせると、結果が返されます。

実際の乗算はimullで行われます。これはCPUの種類によってCPUの処理に一定の時間がかかります。

Agner Fog's instruction timing tablesを見ると、各命令にかかる時間がわかります。ほとんどのx86プロセッサでは小さな定数のようですが、64ビット引数と結果を持つAMD K8のimul命令は4-5 CPUサイクルと表示されます。私はそれが測定上の問題か本当に変わる時間かどうかはわかりません。

また、実行時間以外の要素も含まれています。整数はプロセッサを通過して移動し、乗算するために適切な場所に移動する必要があります。これと他のすべての要素がレイテンシを生み出します。これはAgner Fogの表にも記載されています。キャッシュの問題など、他の問題もあります。これはまた、人生を難しくします。実行することなく、どれくらい速く実行されるか簡単に言うのは簡単ではありません。

---

x86のみのアーキテクチャではありません、それはCPUの非一定の時間乗算を持っているそこのアーキテクチャそこにある実際には考えられないではありません。これは、乗算を使用するアルゴリズムがこれらのプラットフォーム上のタイミング攻撃の影響を受けやすい暗号化に特に重要です。

Answer 2

ほとんどの一般的なアーキテクチャでの乗算自体は一定です。レジスタのロード時間は、変数の位置（L1、L2、RAMなど）によって異なる場合がありますが、サイクル数は一定になります。これは、特定の精度を達成するために追加のサイクルを必要とするかもしれないsqrtのような操作とは対照的です。

あなたは、命令がAMD、インテル、VIAのためにここにコストを得ることができます。http://www.agner.org/optimize/instruction_tables.pdf

Answer 3

void myfun() 
{ 
int a = 111; 
int b = 509; 
int c = a * b; 
} 

デ一部を組み立てる：

movl $111, -4(%ebp) 
movl $509, -8(%ebp) 
movl -4(%ebp), %eax 
imull -8(%ebp), %eax 

あなたはそれがすべてimull命令に依存して見ることができるように、特にCPUのサイクルをフェッチ、デコード、実行します。

Answer 4

時間の複雑さによって、aとbの桁数に依存するかどうかを推測していますか？したがって、CPUクロックサイクル数は、2 * 3か111 * 509のどちらを乗算したかによって異なります。はい、それは変わると思います。そのアーキテクチャが乗算演算をどのように実装し、中間結果がどのように格納されるかによって異なります。 これを行うには多くの方法がありますが、binary adder/subtractor回路を使用して乗算を実装するのがシンプル/プリミティブな方法です。 a * bの乗算は、n桁のバイナリ加算器を使用してb回にaを加算します。同様に、a/bの除算bはaからaに0になるまで減算されますが、商と剰余を格納するためのスペースが必要になります。あなたの例では

Answer 5

、コンパイラが乗算し、あなたのコードは、あなたが

int c = a * 509; 

見えるようにあなたの例を変更した場合、コンパイラはあなたを書き換える決めるかもしれません

int c = 56499; 

ようになりだろうコードのように

int c = a * (512 - 2 - 1); 
int c = (a << 9) - (a << 1) - a; 

コンパイラは、シャツを乗算命令のコストに使用し、最良の選択肢を選ぶ。 速い多重命令が与えられれば、それは通常1または多分2シフトがより速くなることを意味します。

数値が大きすぎて整数（32ビット）に収まらない場合は、任意の精度の 算術ルーチンでは、O（n^2）とO（n log n）の間の時間を使用します.nは32数字を保持するために必要なビット部分。