参考: 領域計算量と時間計算量

整数 $n$ の素数判定には自明な方法がある.

• 2, 3, $\ldots$, $n-1$ で割ってみる.
• 2, 3, $\ldots$, $\lfloor \sqrt{n} \rfloor$ で割ってみる. ( $\lfloor x \rfloor$ は $x$ を越えない最大の整数.)
• 2 以外は奇数で割る.

いずれにせよ $\sqrt{n}$ に比例する回数の割算が必要である. たとえば $n \simeq 2^{1024} \simeq 10^{308}$ のとき, $\sqrt{n} \simeq 2^{512} \simeq 10^{154}$. 計算機では 1 クロックを単位として各種の命令が実行されている. 現在の一般的な CPU の クロックは 1GHz ($10^9$Hz) 程度, すなわち単位操作を一秒間に $10^9$ 回できる程度なので, 1クロックで1回割算ができても $10^{145}$ 秒 $\simeq 3.17 \times 10^{137}$ 年程かかることになる.

$2^{1024}$ 程度の数の素因数分解は, もっとよいアルゴリズム を用いても困難であり, それが RSA 暗号の安全性の根拠となって いる.

素朴には, 計算量とは, ある大きさのデータに対して, 計算にどれだけ 時間 (ステップ数) あるいは領域 (メモリ量) がかかるかを示す量である. ここでいくつか曖昧な点がある. この点をもうすこし詳しく考察しよう.

• データの大きさ
  • 大きな数も小さな数も一つの数と見る
  • メモリ上で必要な量を単位とする.

• 1 ステップとは
  • 数の計算は 1 ステップと見る.
  • 計算機の命令を 1 ステップと見る.

例えば浮動小数演算を用いる場合には, どちらで考えても同じだが, 近似なしに正確な値を有理数で求めていく場合には注意が必要である. たとえば, 2 つの $n$ 桁の整数

$$a = \sum_{i=0}^{n-1} a_i\cdot 10^i, \quad b = \sum_{i=0}^{n-1} b_i\cdot 10^i$$

を筆算の要領で計算することを考える.

$$ab = \sum_{i=0}^{n-1} ab_i\cdot 10^i$$

を使って, $ab_i$ を計算してから $i$ 桁左にシフトしながら足して 行く. 一桁の数 $u$ に対し $au = \sum_{i=0}^n m_i\cdot 10^i$ を計算するアルゴリズムは次の通り.

$c \leftarrow 0$


for ( $i = 0$; $i < n$; $i$++ )

$t \leftarrow a_ib+c$

$m_i \leftarrow t \bmod 10$

$c \leftarrow \lfloor t/10 \rfloor$


end for

$m_n \leftarrow c$

この計算で, かけ算は $n$ 回, 10 による割算が $n$ 回必要である.

次に, $ab_i$ をシフトして足していく計算を考える. これは, 繰り上がりを無視すれば $n$ 桁の数 $\sum_{i=0}^n f_i\cdot 10^i$, $\sum_{i=0}^n g_i\cdot 10^i$ の加算と考えてよいから次のアルゴリズムで計算できる.

$c = 0$


for ( $i = 0$; $i < n$; $i$++ )

$t \leftarrow f_i+g_i+c$


if $t \ge 10$ $f_i \leftarrow t-10$, $c \leftarrow 1$


else $f_i \leftarrow t$, $c \leftarrow 0$


end for

(繰り上がりの処理)

これは, 本質的には加算が $n$ 回で計算できる. 以上の計算が $n$ 回必要になるから, $n$ 桁の数の積の計算には $n^2$ に比例するステップ数が必要になることが分かる.

$n$ 桁の整数を二つかける筆算アルゴリズムの計算量は $O(n^2)$ であった. このアルゴリズムはさらに改良可能である. 簡単な高速化アルゴリズムとして, Karatsuba アルゴリズムを紹介する. まず, 二桁の数 $a = a_1\cdot 10+a_0$ $b = b_1\cdot 10+b_0$ の積を考える. 普通にやると

$$ab = a_1b_1 \cdot 10^2 + (a_1b_0+a_0b_1) \cdot 10 + a_0b_0$$

とかけ算が 4 回現れる. これを

$$ab = a_1b_1 \cdot 10^2 + ((a_1-a_0)(b_0-b_1)+a_1b_1+a_0b_0) \cdot 10 + a_0b_0$$

と変形するとかけ算は $a_1b_1$, $a_0b_0$, $(a_1-a_0)(b_0-b_1)$ の 3 回になる. (加算は増える.) これを繰り返す. $2^n$ 桁の整数 $a$, $b$ をかける場合 の計算量を $T(2^n)$ とする.$N = 2^{n-1}$ として $a = a_1\cdot 10^N+a_0$, $b = b_1\cdot 10^N+b_0$, $0 \le a_i, b_i \le 10^N$ と書いて, 上の考察を適用する. 一桁の乗算, 加減算のコストをそれぞれ $M$, $A$ とすると,

$$T(2^n) = 3T(2^{n-1})+4\cdot 2^nA.$$

(第 2 項は「倍長」整数の加算コストを表す. $T(1)=M$ より, この漸化式を解いて,

$$T(2^n) = (M+8A)\cdot 3^n-8A\cdot 2^n.$$

よって, $T(2^n) = O(3^m)$. これより

$$T(n) = O(3^{\log_2 n}) = O(n^{\log_2 3}).$$

$\log_2 3 \simeq 1.58$ より 漸近的には筆算よりよいアルゴリズムと言える.

なお, 一変数多項式の積でも同じアルゴリズムが使える. かなり低い次数 (20 次程度) から, 通常の $O(n^2)$ アルゴリズムより高速になる.