二進対数

二進対数とは

二進対数（binary logarithm）とは、数学における対数の一種で、底を2とする対数 \( \log_2 x \) のことです。これは指数関数 \( x \rightarrow 2^x \) の逆関数であり、ある数 \( x \) が2の何乗であるかを示します。二進対数は、特に計算機科学や情報理論において重要な役割を果たします。

コンピューターへの応用

情報理論

二進対数は、二進法と密接な関係があるため、計算機科学や情報理論で頻繁に用いられます。情報量の単位であるビットは、二進対数を用いて表現されます。例えば、\( n \) 個の選択肢がある場合、それを特定するために必要なビット数は \( \lceil \log_2 n \rceil \) で求められます。この文脈では、二進対数は \( \lg x \) と表記されることもあります。ただし、ISO 80000-2では、\( \lg x \) は常用対数 \( \log_{10} x \) を示すとされているため、二進対数の略記には \( \lb x \) が推奨されています。

計算の複雑性

アルゴリズムの計算量を評価する際にも、二進対数は重要な役割を果たします。例えば、ある数 \( n \) を2で繰り返し割って1以下にするために必要な回数は \( \lfloor \log_2 n \rfloor \) で求められます。この考え方は、二分探索などの多くのアルゴリズムの解析に用いられます。

二分探索では、探索範囲が操作ごとに半分になるため、サイズ \( n \) の問題を解決するために必要なステップ数は、おおよそ \( \log_2 n \) 回となります。また、\( n \) 個の要素を持つ完全二分探索木の高さは \( 1 + \log_2 n \) となります。アルゴリズムの実行時間は通常、ランダウの記号（O記法）を用いて表現されます。底の変換公式 \( \log_2 n = \frac{\log_k n}{\log_k 2} \) により、\( O(\log_2 n) \) のアルゴリズムは \( O(\log_k n) \) と表現できます。そのため、\( O(\log n) \) や \( O(n \log n) \) のような式では、対数の底は本質的な問題ではありません。

しかし、対数の底を明示する必要がある場合もあります。例えば、\( O(2^{\log_2 n}) \) と \( O(2^{\ln n}) \) は異なる計算量を表します。前者は \( O(n) \) に相当し、後者は \( O(n^{0.6931...}) \) に相当します。 \( O(n \log n) \) の計算量を持つアルゴリズムは、しばしば線形対数と呼ばれます。

アルゴリズムの例

クイックソート（平均の場合）
二分探索木
マージソート
モンジュ配列の計算

電卓での計算

一般の電卓には \( \log_2 \) のボタンがないため、自然対数 \( \ln \) や常用対数 \( \log_{10} \) のボタンを利用します。底の変換公式を用いると、 \( \log_2 n = \frac{\ln n}{\ln 2} = \frac{\log_{10} n}{\log_{10} 2} \) となり、以下の式で二進対数を計算できます。

\( \log_2 n = \ln n \times 1.442695... = \log_{10} n \times 3.321928... \)

興味深いことに、 \( \ln n + \log_{10} n \) は \( \log_2 n \) と0.6%以内の誤差で一致します。この式は、\( 2.0081359... \) を底とする対数で表現できます。

二進対数の算出

整数→整数

二進対数の整数部分を計算する場合、床関数 \( \lfloor \log_2 n \rfloor \) や天井関数 \( \lceil \log_2 n \rceil \) を用います。これらの間には、 \( \lfloor \log_2 n \rfloor = \lceil \log_2 (n+1) \rceil - 1 \) という関係があります。また、 \( \lfloor \log_2 0 \rfloor = -1 \) と定義することで、定義域を \( n \geq 0 \) に拡張できます。非負整数 \( n \) の二進表示における先頭の0の個数 \( \text{nlz}(n) \) との間には、 \( \lfloor \log_2 n \rfloor = (m-1) - \text{nlz}(n) \) の関係があります。ここで \( m \) は \( n \) のビット数です。

実数→実数

正の実数 \( x \) に対して、二進対数は次の2段階で計算されます。

1. 整数部分 \( \lfloor \lb x \rfloor \) を計算します。
2. 小数部分を計算します。

整数部分の計算は、\( 2^n \leq x < 2^{n+1} \) を満たす整数 \( n \) を求めることで行います。このとき、\( 1 \leq x/2^n < 2 \) となるため、小数部分を \( \text{lb}(x/2^n) \) と定義します。

\( y = x/2^n \) と置くと、\( \text{lb} x = n + \text{lb} y \) となります。小数部分 \( \text{lb} y \) は、掛け算と割り算のみを用いて再帰的に計算できます。

計算手順は以下の通りです。

1. \( 1 \leq y < 2 \) から始めます。\( y = 1 \) ならば、小数部分は0で終了です。
2. \( y > 1 \) ならば、\( y \) を繰り返し2乗して \( 2 \leq z < 4 \) なる実数 \( z \) を得ます。2乗した回数を \( m \) とすると、 \( z = y^{(2^m)} \) となります。
3. 対数をとり、式変形を行うと、 \( \text{lb} y = 2^{-m} + 2^{-m} \text{lb}(z/2) \) となります。
4. この \( m \) の値を記録しておきます。
5. \( y \leftarrow z/2 \) として、上記の手順を繰り返します。
6. 最終的に、 \( \text{lb} x = n + 2^{-m[1]} + 2^{-m[1]-m[2]} + 2^{-m[1]-m[2]-m[3]} + ... \) として計算できます。ここで、 \( m[i] \) は \( i \) 回目の繰り返しで2乗を行った回数です。

実際には、無限級数の計算を行う代わりに、値を2乗して2以上であれば2で割るという操作を繰り返すことで、二進対数を近似的に計算できます。

まとめ

二進対数は、計算機科学や情報理論において不可欠な概念です。アルゴリズムの解析や情報量の計算など、様々な場面で利用されています。この記事では、二進対数の定義、応用、計算方法について詳しく解説しました。