【一覧表あり】2の累乗の指数的爆発を解説【多重ループ処理に注意】

こんにちは。iQeda [@iQeeeda] です。

2 の累乗は「2^0 = 1 からはじまって、数を 2 倍にしていく」だけの単純な計算です。
しかし、この 2^n は時折大きな問題になって物事を解決できなくしてしまいます。

今回は 2 の累乗数が引き起こす「指数的爆発」について説明します。

指数的な爆発とは
- 【一覧表】2 の累乗数
- 多重ループが処理パフォーマンスを下げる理由
倍々ゲーム
- 5 個のチェックボックスの組み合わせ
- 30 個のチェックボックスの組み合わせ
知っておくと便利な 2 の冪(べき)の表

指数的な爆発とは

厚さ 1mm の紙があります。
この紙は無限に 2 つ折りできる柔軟性があり、2 つ折りするたびに厚さが 2 倍になるとします。

月と地球の距離は約 39 万km ですが、この紙を何回 2 つ折りしたら月に到達するでしょうか。

【一覧表】2 の累乗数

厚さ 1 mm の紙を折ると、厚さ 2 mm (2^1) ,
厚さ 2 mm の紙を折ると、厚さ 4 mm (2^2) ,
厚さ 4 mm の紙を折ると、厚さ 8 mm (2^3) になります。

これは単純な 2^n の計算なので一覧表にしてみましょう。

2^n	値	備考
`2^0`	1	単位は mm
`2^1`	2
`2^2`	4
`2^3`	8
`2^4`	16
`2^5`	32
`2^6`	64
`2^7`	128
`2^8`	256
`2^9`	512
`2^10`	1024	1m 超え
`2^11`	2048
`2^12`	4096
`2^13`	8192
`2^14`	16384
`2^15`	32768
`2^16`	65536
`2^17`	131072
`2^18`	262144
`2^19`	524288
`2^20`	1048576	1km 超え
`2^21`	2097152
`2^22`	4194304
`2^23`	8388608
`2^24`	16777216
`2^25`	33554432
`2^26`	67108864
`2^27`	134217728
`2^28`	268435456
`2^29`	536870912
`2^30`	1073741824	1000km 超え
`2^31`	2147483648
`2^32`	4294967296
`2^33`	8589934592
`2^34`	17179869184
`2^35`	34359738368
`2^36`	68719476736
`2^37`	137438953472
`2^38`	274877906944
`2^39`	549755813888	ここで 39 万km を超える
`2^40`	1099511627776

なんと 1mm の紙をたった 39 回折るだけで、月に到達してしまうことが分かりました。

数を 2 倍にしていく操作を繰り返すと、少ない試行回数でも急激に数が増加します。
このような現象を「指数的な爆発」「指数的な増加」「指数関数的な増大」「組み合わせ論的爆発」といいます。

これはちょっとスケールが大きくなるだけで問題解決が困難になったりするので注意が必要です。

多重ループが処理パフォーマンスを下げる理由

例えばプログラミングでは「多重ループ処理すると処理がすごく重くなる」場合があります。
最悪の場合はフリーズします。これも指数的な爆発が起きやすいことが理由です。

ちなみに 2^n は指数的な爆発は起きますが、n2 では指数的な爆発は起きません。

倍々ゲーム

5 個のチェックボックスの組み合わせ

下記のような設定オプションがあるとします。

Option 1 Option 2 Option 3 Option 4 Option 5

これはどのチェックボックスをオン・オフにするかによって、
動作するプログラムの振る舞いが変わるものです。

すべてのチェックボックスのオン・オフ組み合わせをテストしないといけない場合、
テストは全部でいくつ必要になるでしょう？

答え

チェックボックスの状態はオン・オフの 2 種類しかありません。
なのでチェックボックスの数が n 個であれば、2^n の状態パターンが存在します。

チェックボックスの数が 5 個のときは 2^5 で 32 パターンの状態が存在することがわかります。
よって 32 個のテストが必要になります。

30 個のチェックボックスの組み合わせ

チェックボックスの数が 30 個の場合はどうなるでしょうか。
答えは 2^30 で 1073741824 。10 億 7374 万 1824 個のテストが必要です。

すべての可能性を「しらみつぶし」でテストするのは現実的ではない

実際、なんかしらのアプリのオプションで 30 個を超える設定項目を目にすることはあります。

そのようなとき 1 個 1 個の設定項目が互いにどんな影響を及ぼしあうのか、
すべてのパターンをテストするのは現実的ではありません。

一般的にテストは厳選します。
数を絞りすぎるとテストの意味はないですし、多すぎると指数的な爆発を起こすので注意しましょう。

ブルート・フォース・アタックとは

コンピュータの暗号化・復号化では「鍵」と呼ばれるランダムなビット列を使います。
大事な情報は「鍵」によって暗号化して、「鍵」を知っている人だけに復号化されます。

しらみつぶしに「鍵」を作っては試す暗号解読方法を「ブルート・フォース・アタック」といいます。

ビット長と安全性の関係

鍵のビット長が長いほど、ブルート・フォース・アタックするのに時間がかかります。

3 ビットの場合

たとえば、もし鍵のビット長が 3 ビットであれば 2^3 で 8 つの鍵パターンしかありません。

上記 8 パターンを試すだけで暗号文が解読できてしまうのです。

鍵の生成は指数的な爆発を利用している

鍵のビット長が 4 ビットであれば 2^4 で 16 つの鍵パターン、
鍵のビット長が 5 ビットであれば 2^5 で 32 つの鍵パターン、
鍵のビット長が 6 ビットであれば 2^6 で 64 つの鍵パターン…となります。

しかし、この程度のビット数では重要な秘密が守れるわけがないので、
現在では 256 ビット以上の鍵が使われます。

さて、ここで 1 ビット増えるごとに鍵のパターンが 2 倍になっていることがわかります。
鍵の生成には「指数的な爆発」が起きているのです。

512 ビットにもなると、宇宙が生まれて現在に至るまで試しても解読できない桁数になります。
指数の小ささには油断しないようにしましょう。

知っておくと便利な 2 の冪(べき)の表

最後に 2 の冪の表を紹介します。
スケーラビリティやメモリの制限がある問題の多くで役に立つので、暗記しておくと便利です。

2の冪	厳密な値	近似値	MG・GBなど
2^7	128
2^8	256
2^10	1024	千	1KB
2^16	65536		64KB
2^20	1048576	百万	1MB
2^30	1073741824	十億	1GB
2^32	4294967296		4GB
2^40	1099511627776	一兆	1TB

例えば 32 ビット整数の各ビットを boolean 型の変数に割り当てるビットベクトルを一般的なマシンのメモリで組み込むことができるか、
この表で計算することができます。

各データがビットベクトルの 1 ビットを仕様するので、
データの保持には 2^32 ビット ( 2^29 バイト) 必要になります。

これは 1/2 GB のメモリに相当するので、一般的なマシンのメモリでも十分足りるでしょう。

CS シリーズ

次回

https://iqeda.com/posts/%E3%80%90%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E3%80%91%E6%8E%A2%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%80%8C%E3%83%90%E3%82%A4%E3%83%8A%E3%83%AA%E3%82%B5%E3%83%BC%E3%83%81/

前回

https://iqeda.com/posts/%E3%80%90%E5%86%8D%E5%B8%B0%E7%9A%84%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%80%91%E5%86%8D%E5%B8%B0%E3%83%BB%E5%B8%B0%E7%B4%8D%E3%81%AE%E9%81%95%E3%81%84%E3%82%92%E8%A7%A3%E8%AA%AC%E3%80%90/