二進対数

テンプレート:Mathのグラフ

二進対数 (にしんたいすう、テンプレート:Lang-en-short)とは、2を底とする対数 テンプレート:Math のことである。これは、指数関数 テンプレート:Math の逆関数でもある。

コンピューターへの応用

情報理論

二進対数は二進法と密接に関係しているため、計算機科学や情報理論でしばしば使われる。この文脈において、二進対数は「テンプレート:Math」と表記されることがよくある。同じ関数の別の表記としてときどき（特にドイツ語で）使われるものとして「テンプレート:Math」があり、これはラテン語の テンプレート:Lang から来ている。ただし、ISO 80000-2では「テンプレート:Math」は テンプレート:Math すなわち常用対数を示すとされており、二進対数の略記法は「テンプレート:Math」である。本稿でもこれに従う。

正整数 テンプレート:Mvar の二進法における桁数（すなわちビット数）は テンプレート:Math の整数部分であり、以下の床関数で表される。

$\lfloor \mathrm{lb}n\rfloor +1$

計算の複雑性

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

しかし、アルゴリズムの実行時間は通常、定数倍の差を無視してランダウの記号で表記される。ここで、1以外の任意の正の数 テンプレート:Mvar に対して テンプレート:Math（底の変換）が成り立つので、テンプレート:Math の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、テンプレート:Math の実行時間を持つとも表現できる。したがって、テンプレート:Math や テンプレート:Math といった式では、対数の底がいくつであるかは本質的な問題ではない。

ただし、対数の底を指定する必要があるケースもあるので注意が必要である。例えば、所要時間 テンプレート:Math の計算と、所要時間 テンプレート:Math の計算とは同等ではない。前者は テンプレート:Math と等価であり、後者は テンプレート:Math と等価である。

テンプレート:Math の実行時間をもつアルゴリズムは、しばしば線形対数と呼ばれる。テンプレート:Math や テンプレート:Math の実行時間をもつアルゴリズムの例としては、次のようなものがある。

• クイックソート（ただしこれは平均の場合であり、最悪の場合には テンプレート:Math となる。）
• 2分探索木
• マージソート
• テンプレート:仮リンクの計算

電卓の使用法

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

テンプレート:Math

従って、

テンプレート:Math

となる。

ところでこの式は、テンプレート:Math が0.6%以内の差で テンプレート:Math と一致する、という興味深い結果を与える。実際のところ、テンプレート:Math という式は、

$e^{1/(1+{\log }_{10}e)}=10^{1/(1+{\log }_{e}10)}=2.008135929346243954228756325191\dots$

という底を用いて、テンプレート:Math と表現される。

二進対数の算出

整数→整数

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

$\lfloor {\log }_{2}n\rfloor =\lceil {\log }_2(n+1)\rceil -1$　　ただし、テンプレート:Math

の関係がある。この左辺の関数は、$\lfloor {\log }_{2}0\rfloor =-1$ とおくことによって、定義域を テンプレート:Math にまで拡張できる。このように拡張した関数は、非負整数 テンプレート:Mvar の テンプレート:Mvar ビット符号なし二進表示におけるテンプレート:仮リンク テンプレート:Math との間で

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

の関係にある。この整数二進対数は、テンプレート:Mvar の最上位ビットがどこにあるかを示している。

実数→実数

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

1. 整数部分 $\lfloor \mathrm{lb}x\rfloor$ を計算する。
2. 小数部分を計算する。

まず、整数部分の計算は簡単である。任意の正の実数 テンプレート:Mvar に対して、テンプレート:Math となるような整数 テンプレート:Mvar が唯一に定まる。この各辺を テンプレート:Math で割った テンプレート:Math という式を立ててもよい。これをもって、二進対数の整数部分を テンプレート:Mvar と定める。そして、この テンプレート:Mvar を使って、小数部分を テンプレート:Math と表記することにする。すなわち、テンプレート:Math と置くと、次のようになる。

テンプレート:Math　　ただし、テンプレート:Math

小数部分 テンプレート:Math は、掛け算と割り算のみを使って再帰的に計算できる。この計算手順は以下のとおりとなる。

1. まず、テンプレート:Math から出発する。テンプレート:Math ならば、小数部分は0となって、その時点で終了である。
2. テンプレート:Math ならば、テンプレート:Mvar を繰り返し2乗して、テンプレート:Math なる実数 テンプレート:Mvar を得る。2乗した回数を テンプレート:Mvar とすると、$z=y^{(2^m)}$ となる。
3. この式の両辺の対数をとり、式変形を行うと次のようになる。

   $\begin{array}{cc}\mathrm{lb}z& =2^m\mathrm{lb}y\\ \mathrm{lb}y& =\frac{\mathrm{lb}z}{2^m}\\ & =\frac{1+\mathrm{lb}(z/2)}{2^m}\\ & =2^{-m}+2^{-m}\mathrm{lb}(z/2)\end{array}$

4. この テンプレート:Mvar の値を記録しておく。
5. 2乗する作業をやめる基準は テンプレート:Math であった。したがって、テンプレート:Math となっている。そこであらためて テンプレート:Math と置き、この新しい テンプレート:Mvar の二進対数を同じ手法で計算する。

そして最終的に、テンプレート:Math を次のように計算する。以下、テンプレート:Math は、アルゴリズムの テンプレート:Mvar 回目の繰り返しにおいて2乗の操作を行った回数とする。

$\begin{array}{cc}\mathrm{lb}x& =n+2^{-m[1]}(1+2^{-m[2]}(1+2^{-m[3]}(1+\cdots )))\\ & =n+2^{-m[1]}+2^{-m[1]-m[2]}+2^{-m[1]-m[2]-m[3]}+\cdots \end{array}$

ある時点で テンプレート:Math となった場合には、この計算は当然、そこまでで終了する。逆に、永久に テンプレート:Math とならない場合には、この式は無限級数となるが、すべての テンプレート:Mvar について テンプレート:Math が成り立つので、どの項もその直前の項より小さくなっている。よって、比較判定法により、この級数が必ず収束するということがわかる。

実用上は、計算に無限の時間を費やすわけにはいかないので、計算を途中で打ち切った近似値を使うことになる。級数の テンプレート:Mvar 番目の項より後ろを切り捨てた場合の誤差の上限は、テンプレート:Math である。

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

1. 値を2乗する。
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 < 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ビットの精度で計算する（すなわち、上記の関数を lb(1.65, 4) として呼び出す）ケースを考える。このプログラムを逐次追いかけていくと次のようになる。

• まず、このプログラムでは整数位の計算が既に終わっていることを前提とする（すなわち、テンプレート:Math となっていることを要求する）ので、無条件で "0．" の2文字を書く。
• 与えられた テンプレート:Math を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という数字列を得たので、

テンプレート:Math

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

関連項目

• 常用対数
• 自然対数
• 二進法
• 2の冪
• 2の自然対数