アルゴリズム論特論（塩田）第1回 (3) 四則演算の計算量
２進数の計算をやってみよう
- ここをクリック
- とりあえず、足し算と掛け算の問題をやってみてください。
加算器の復習
- 計算機に２進数の計算をさせるには加算器が必要です。加算器には半加算器 ( half-adder ) と全加算器 ( full-adder ) がありました。
( 計算機システム論でやりましたね。)
- Wikipedia で 加算器の構造 を見てみましょう。
四則演算の計算量
- $k$ ビットの２つの整数を足すためには、加算器を $k$ 個並べて、下の桁からの繰上りを順次上の桁用の全加算器に入力していかないといけません。
従ってその計算には $k$ に比例した時間が掛かります。つまり $O$記法で $O(k)$ の計算量を持つことがわかります。
- $k$ ビットの２つの整数の掛け算の計算量は、筆算をイメージして考えましょう。
$k$ ビットの数が $k$ 段並んでいて、それをひとつずつ足すことになるので、その計算時間は $k$ $\times$ ( $k$ ビット同士の足し算の計算時間 ) $=O(k^2)$ となります。
- ２進数の引き算は、２の補数との足し算ですので ( これも計算機システム学でやりましたね )、その計算量は足し算と同じ $O(k)$ です。
- 割り算は、筆算をイメージすれば掛け算と同様の計算時間が掛かることがわかり、計算量は $O(k^2)$ です。
以上のことと、先ほどのビット長の定理を合わせると次の定理が得られます：
Th.6 $n$ 以下の２つの自然数の四則演算の計算量は
- 加法, 減法は $O(\log n)$
- 乗法, 除法は $O(\log^2 n)$
( $n$ 以下、と言っても $n$ 程度、と言っても同じです。)
Rem.7 実際には、Python などの多倍長整数ルーティンでは「高速乗算法」が実装されていて、乗法の計算量はもっと低く抑えられています。
四則演算の計算時間を計測する Python プログラム
operations.py で実測できます。