二進対数

二進対数 (にしんたいすう、英: binary logarithm)とは、2を底とする対数 $log 2 x$ のことである。これは、指数関数 $x \to 2 x$ の逆関数でもある。

情報理論

二進対数は二進法と密接に関係しているため、計算機科学や情報理論でしばしば使われる。この文脈において、二進対数は「 $lg x$ 」と表記されることがよくある^[1]。同じ関数の別の表記としてときどき（特にドイツ語で）使われるものとして「 $ld x$ 」があり、これはラテン語の Logarithmus Duālis から来ている^[2]。ただし、ISO 80000-2では「 $lg x$ 」は $log 10 x$ すなわち常用対数を示すとされており、二進対数の略記法は「 $lb x$ 」である。本稿でもこれに従う。

正整数 $n$ の二進法における桁数（すなわちビット数）は $1 + lb n$ の整数部分であり、以下の床関数で表される。

\lfloor \operatorname {lb} \,n\rfloor +1\

計算の複雑性

二進対数は、アルゴリズム解析で頻出する。1より大きな数 $n$ を2で繰り返し割っていき、その値を1以下にするために必要な繰り返し回数は、 $\lfloor \operatorname {lb} \,n\rfloor$ で与えられる。この発想は、多くのアルゴリズムやデータ構造の分析で使用される。例えば二分検索では、検索すべき空間の大きさは操作の繰り返しごとに半分になる。ゆえに、大きさ1の問題を得るには大まかにいって $lb n$ 回の繰り返しが必要となり、そのあとは定数時間で終了する。同様に、 $n$ 個の要素からなる完全平衡二分探索木は、 $1 + lb n$ の高さをもつ。

しかし、アルゴリズムの実行時間は通常、定数倍の差を無視してランダウの記号で表記される。ここで、1以外の任意の正の数 $k$ に対して $log 2 n = log k n / log k 2$ （底の変換）が成り立つので、 $O(log 2 n)$ の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、 $O(log 13 n)$ の実行時間を持つとも表現できる^[3]。したがって、 $O(log n)$ や $O(n log n)$ といった式では、対数の底がいくつであるかは本質的な問題ではない。

ただし、対数の底を指定する必要があるケースもあるので注意が必要である。例えば、所要時間 $O(2 lb n)$ の計算と、所要時間 $O(2 ln n)$ の計算とは同等ではない。前者は $O(n)$ と等価であり、後者は $O(n 0.6931...)$ と等価である。

$O(n log n)$ の実行時間をもつアルゴリズムは、しばしば線形対数と呼ばれる。 $O(log n)$ や $O(n log n)$ の実行時間をもつアルゴリズムの例としては、次のようなものがある。

クイックソート（ただしこれは平均の場合であり、最悪の場合には $O(n 2)$ となる。）
2分探索木
マージソート
モンジュ配列（英語版）の計算

電卓の使用法

$log 2$ のボタンがない電卓で $log 2 n$ を計算するための簡単な方法は、関数電卓に一般的に存在する自然対数 "ln" または常用対数 "Log" のボタンを使うことである。この場合、次のような底の変換公式を使うことになる。

log 2 n = ln n / ln 2 = Log n / Log 2

従って、

log 2 n = log e n \times 1.442695... = log 10 n \times 3.321928...

となる。

ところでこの式は、 $log e n + log 10 n$ が0.6%以内の差で $log 2 n$ と一致する、という興味深い結果を与える。実際のところ、 $log e n + log 10 n$ という式は、

e^{1/(1+\log _{10}e)}=10^{1/(1+\log _{e}10)}=2.00813\ 59293\ 46243\ 95422\ 87563\ 25191\ldots

という底を用いて、 $log 2.0081359... n$ と表現される。

二進対数の算出

整数→整数

小数点以下の切り上げ・切り捨てを行って、整数→整数の二進対数を定めることができる。これら二つ（切り上げ・切り下げ）の整数二進対数の間には、

\lfloor \log _{2}n\rfloor =\lceil \log _{2}(n+1)\rceil -1

　　ただし、

1 ≦ n

の関係がある^[4]。この左辺の関数は、 $\lfloor \log _{2}0\rfloor =-1$ とおくことによって、定義域を $n ≧ 0$ にまで拡張できる。このように拡張した関数は、非負整数 $n$ の $m$ ビット符号なし二進表示における先頭の0の個数（英語版） $nlz(n)$ との間で

\lfloor \log _{2}n\rfloor =(m-1)-\operatorname {nlz} (n)

^[4]

の関係にある。この整数二進対数は、 $n$ の最上位ビットがどこにあるかを示している。

実数→実数

一般の正の実数に対しては、二進対数は次の2段階の手順で計算できる。

整数部分 $\lfloor \operatorname {lb} \,x\rfloor$ を計算する。
小数部分を計算する。

まず、整数部分の計算は簡単である。任意の正の実数 $x$ に対して、 $2 n ≦ x < 2 n +1$ となるような整数 $n$ が唯一に定まる^[5]。この各辺を $2 n$ で割った $1 ≦ x /2 n < 2$ という式を立ててもよい。これをもって、二進対数の整数部分を $n$ と定める。そして、この $n$ を使って、小数部分を $lb (x /2 n)$ と表記することにする。すなわち、 $y = x /2 n$ と置くと、次のようになる。

lb x = n + lb y

　　ただし、

1 ≦ y < 2

小数部分 $lb y$ は、掛け算と割り算のみを使って再帰的に計算できる。この計算手順は以下のとおりとなる。

まず、 $1 ≦ y < 2$ から出発する。 $y = 1$ ならば、小数部分は0となって、その時点で終了である。
$y > 1$ ならば、 $y$ を繰り返し2乗して、 $2 ≦ z < 4$ なる実数 $z$ を得る。2乗した回数を $m$ とすると、 $z=y^{(2^{m})}$ となる。
この式の両辺の対数をとり、式変形を行うと次のようになる。
${\begin{aligned}\operatorname {lb} \,z&=2^{m}\operatorname {lb} \,y\\\operatorname {lb} \,y&={\operatorname {lb} \ z \over 2^{m}}\\&={1+\operatorname {lb} (z/2) \over 2^{m}}\\&=2^{-m}+2^{-m}\operatorname {lb} (z/2)\end{aligned}}$
この $m$ の値を記録しておく。
2乗する作業をやめる基準は $2 ≦ z < 4$ であった。したがって、 $1 ≦ z /2 < 2$ となっている。そこであらためて $y ：= z /2$ と置き、この新しい $y$ の二進対数を同じ手法で計算する。

そして最終的に、 $lb x$ を次のように計算する。以下、 $m [i]$ は、アルゴリズムの $i$ 回目の繰り返しにおいて2乗の操作を行った回数とする。

{\begin{aligned}\operatorname {lb} \,x&=n+2^{-m[1]}\left(1+2^{-m[2]}\left(1+2^{-m[3]}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m[1]}+2^{-m[1]-m[2]}+2^{-m[1]-m[2]-m[3]}+\cdots \end{aligned}}

ある時点で $y = 1$ となった場合には、この計算は当然、そこまでで終了する。逆に、永久に $y = 1$ とならない場合には、この式は無限級数となるが、すべての $i$ について $m [i] ≧ 1$ が成り立つので、どの項もその直前の項より小さくなっている。よって、比較判定法により、この級数が必ず収束するということがわかる。

実用上は、計算に無限の時間を費やすわけにはいかないので、計算を途中で打ち切った近似値を使うことになる。級数の $i$ 番目の項より後ろを切り捨てた場合の誤差の上限は、 $(1/2) m [1]+ m [2]+\dots+ m [i]$ である。

しかし実際には幸いなことに、このような高コストな計算も、無限級数の切り捨ても必要とせずに、

値を2乗する。
結果が2以上であれば、2で割る。

という計算を繰り返すのみで簡単に対数を得ることができる。具体的なコードを Microsoft Visual Basic で記述すると、下記のとおりとなる。（なお、この実装ではわかりやすさのために、関数の戻り値を2進表現の文字列としてある。当然ながら、その後の計算のためには、何らかの方法で数値型のデータにしなければならない。）

 Function lb(ByVal y As Double, ByVal numDigits As Integer) as String
     Dim result As String
     result = "0."
     If y &lt; 1 Or 2 &lt;= y Then
         lb = "1≦y＜2の値を渡してください。"
         Exit Function
     End If
     While numDigits > 0
         y = y * y
         If 2 &lt;= y Then
             result = result & "1": y = y / 2
         Else
             result = result & "0"
         End If
         numDigits = numDigits - 1
     Wend
     lb = result
 End Function

例として、1.65の二進対数を4ビットの精度で計算する（すなわち、上記の関数を lb(1.65, 4) として呼び出す）ケースを考える。このプログラムを逐次追いかけていくと次のようになる。

まず、このプログラムでは整数位の計算が既に終わっていることを前提とする（すなわち、 $1 ≦ y < 2$ となっていることを要求する）ので、無条件で "0．" の2文字を書く。
与えられた $y = 1.65$ を2乗すると2.72となる。これは2以上なので、小数1桁目として1を書く。この2.72を2で割って1.36を得る。
1.36を2乗すると1.85となる。これは2より小さいので、2で割ることはせず、2桁目として0を書く。
1.85を再度2乗すると3.43となる。これは2以上なので、3桁目として1を書く。この3.43を2で割って1.72を得る。
1.72を2乗すると2.95となる。これは2以上なので、4桁目として1を書く。ほしい精度は4ビットなので、これで計算終了とする。

こうして0.1011という数字列を得たので、

lb 1.65 ≒ 0.1011 (2) = 13/16

と確定させる。このとき、誤差は1/16未満となっている。さらにもう1ビット計算すれば27/32となり、誤差は1/32未満となる。一般に、 $m$ ビットの精度がほしい（すなわち、誤差を $(1/2) 1+ m$ 未満としたい）ときには、2乗の計算をちょうど $m$ 回、2で割る計算を最大 $m$ 回行えば必要十分である。