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

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

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

指数的な爆発とは

厚さ 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 の計算なので一覧表にしてみましょう。

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

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

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

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

倍々ゲーム

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

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

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

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

答え

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

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

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

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

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

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

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

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

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

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

ビット長と安全性の関係

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

3 ビットの場合

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

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

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

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

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

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

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

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

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

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

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

CS シリーズ

次回

前回