二進対数

二進対数 (にしんたいすう、)とは、2を底とする対数 のことである。これは、指数関数 の逆関数でもある。
コンピューターへの応用.
情報理論.
二進対数は二進法と密接に関係しているため、計算機科学や情報理論でしばしば使われる。この文脈において、二進対数は「」と表記されることがよくある。同じ関数の別の表記としてときどき（特にドイツ語で）使われるものとして「」があり、これはラテン語の から来ている。ただし、ISO 80000-2では「」は すなわち常用対数を示すとされており、二進対数の略記法は「」である。本稿でもこれに従う。
正整数 の二進法における桁数（すなわちビット数）は の整数部分であり、以下の床関数で表される。
計算の複雑性.
二進対数は、アルゴリズム解析で頻出する。1より大きな数 を2で繰り返し割っていき、その値を1以下にするために必要な繰り返し回数は、formula_2 で与えられる。この発想は、多くのアルゴリズムやデータ構造の分析で使用される。例えば二分検索では、検索すべき空間の大きさは操作の繰り返しごとに半分になる。ゆえに、大きさ1の問題を得るには大まかにいって 回の繰り返しが必要となり、そのあとは定数時間で終了する。同様に、 個の要素からなる完全平衡二分探索木は、 の高さをもつ。
しかし、アルゴリズムの実行時間は通常、定数倍の差を無視してランダウの記号で表記される。ここで、1以外の任意の正の数 に対して （底の変換）が成り立つので、 の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、 の実行時間を持つとも表現できる。したがって、 や といった式では、対数の底がいくつであるかは本質的な問題ではない。
ただし、対数の底を指定する必要があるケースもあるので注意が必要である。例えば、所要時間 の計算と、所要時間 の計算とは同等ではない。前者は と等価であり、後者は と等価である。
 の実行時間をもつアルゴリズムは、しばしば線形対数と呼ばれる。 や の実行時間をもつアルゴリズムの例としては、次のようなものがある。
電卓の使用法.
 のボタンがない電卓で を計算するための簡単な方法は、関数電卓に一般的に存在する自然対数 "ln" または常用対数 "Log" のボタンを使うことである。この場合、次のような底の変換公式を使うことになる。
従って、
となる。
ところでこの式は、 が0.6%以内の差で と一致する、という興味深い結果を与える。実際のところ、 という式は、
という底を用いて、 と表現される。
二進対数の算出.
整数→整数.
小数点以下の切り上げ・切り捨てを行って、整数→整数の二進対数を定めることができる。これら二つ（切り上げ・切り下げ）の整数二進対数の間には、
の関係がある。この左辺の関数は、formula_5 とおくことによって、定義域を にまで拡張できる。このように拡張した関数は、非負整数 の ビット符号なし二進表示における との間で
の関係にある。この整数二進対数は、 の最上位ビットがどこにあるかを示している。
実数→実数.
一般の正の実数に対しては、二進対数は次の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 < 1 Or 2 <= y Then
 lb = "1≦y＜2の値を渡してください。"
 Exit Function
 End If
 While numDigits > 0
 y = y * y
 If 2 <= 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ビットの精度で計算する（すなわち、上記の関数を codice_1 として呼び出す）ケースを考える。このプログラムを逐次追いかけていくと次のようになる。
こうして0.1011という数字列を得たので、
と確定させる。このとき、誤差は1/16未満となっている。さらにもう1ビット計算すれば27/32となり、誤差は1/32未満となる。一般に、 ビットの精度がほしい（すなわち、誤差を 未満としたい）ときには、2乗の計算をちょうど 回、2で割る計算を最大 回行えば必要十分である。