二進対数のソースを表示

[[File:Binary logarithm plot.png|thumb|right|200px|{{math|1=log<sub>2</sub> ''n''}}の[[グラフ (関数)|グラフ]]]]

'''二進対数''' (にしんたいすう、{{lang-en-short|binary logarithm}})とは、2を底とする[[対数]] {{math|1=log<sub>2</sub> ''x''}} のことである。これは、[[指数関数]] {{math|1=''x'' → 2<sup>''x''</sup>}} の[[逆関数]]でもある。

== コンピューターへの応用 ==
=== 情報理論 ===
二進対数は[[二進法]]と密接に関係しているため、[[計算機科学]]や[[情報理論]]でしばしば使われる。この文脈において、二進対数は「{{math|1=lg ''x''}}」と表記されることがよくある<ref>{{cite book 
| last = Cormen 
| first = Thomas H. 
| authorlink=Thomas H. Cormen 
| author2 = [[:en:Charles E. Leiserson|Leiserson, Charles E.]], [[:en:Ron Rivest|Rivest, Ronald L.]], [[:en:Clifford Stein|Stein, Clifford]]
| title = [[Introduction to Algorithms]]
| origyear = 1990
| year = 2001
| edition = 2nd 
| publisher = MIT Press and McGraw-Hill 
| isbn = 0-262-03293-7
| page = 34
}}</ref>。同じ関数の別の表記としてときどき（特にドイツ語で）使われるものとして「{{math|1=ld ''x''}}」があり、これはラテン語の {{lang|la|'''L'''ogarithmus '''D'''uālis}} から来ている<ref>例えば、次を参照。{{citation|title=Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum|first=Friedrich L.|last=Bauer|publisher=Springer Science & Business Media|year=2009|isbn=9783642029929|page=54|url=https://books.google.co.jp/books?id=y4uTaLiN-wQC&pg=PA54&redir_esc=y&hl=ja}}.</ref>。ただし、[[ISO 80000-2]]では「{{math|1=lg ''x''}}」は {{math|1=log<sub>10</sub> ''x''}} すなわち[[常用対数]]を示すとされており、二進対数の略記法は「{{math|1=lb ''x''}}」である。本稿でもこれに従う。

正整数 {{mvar|n}} の[[二進法]]における桁数（すなわち[[ビット]]数）は {{math|1=1 + lb ''n''}} の整数部分であり、以下の[[床関数と天井関数|床関数]]で表される。

:<math> \lfloor \operatorname{lb}\, n\rfloor + 1 \ </math>
<!-- 意味不明、コメントアウト。
情報理論では、{{仮リンク|自己情報量|en|self-information}}と[[情報量]]の定義は二進対数を含んでいる。これは情報量の単位であるビットあるいは[[シャノン (単位)|シャノン]]が、同一確率の2つの事象の一方の発生から得られる情報量を表すためである。
-->

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

しかし、アルゴリズムの実行時間は通常、定数倍の差を無視して[[ランダウの記号]]で表記される。ここで、1以外の任意の正の数 {{mvar|k}} に対して {{math|1=log<sub>2</sub> ''n'' = log<sub>''k</sub> n'' / log<sub>''k'' </sub>2}}（底の変換）が成り立つので、{{math|1=O(log<sub>2</sub> ''n'')}} の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、{{math|1=O(log<sub>13</sub> ''n'')}} の実行時間を持つとも表現できる<ref>1より小さな底でも対数の算出自体は当然ながら可能である。しかし、そのような底を用いると {{math|1=''n'' &gt; 1}} のときに {{math|1=log ''n'' &lt; 0}}、特に、{{math|1=''n'' → +∞}} のときに {{math|1=log ''n'' → &minus;∞}} となるため、所要時間の評価用としては実用的でない。</ref>。したがって、{{math|1=O(log ''n'')}} や {{math|1=O(''n'' log ''n'')}} といった式では、対数の底がいくつであるかは本質的な問題ではない。

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

{{math|1=O(''n'' log ''n'')}} の実行時間をもつアルゴリズムは、しばしば[[ランダウの記号#一般的なオーダー|線形対数]]と呼ばれる。{{math|1=O(log ''n'')}} や {{math|1=O(''n'' log ''n'')}} の実行時間をもつアルゴリズムの例としては、次のようなものがある。

* [[クイックソート]]（ただしこれは'''平均'''の場合であり、'''最悪'''の場合には {{math|1=O(''n''<sup>2</sup>)}} となる。）
* [[2分探索木]]
* [[マージソート]]
* {{仮リンク|モンジュ配列|en|Monge array}}の計算

== 電卓の使用法 ==
{{math|1=log<sub>2</sub>}} のボタンがない電卓で {{math|1=log<sub>2</sub> ''n''}} を計算するための簡単な方法は、[[関数電卓]]に一般的に存在する[[自然対数]] "ln" または[[常用対数]] "Log" のボタンを使うことである。この場合、次のような[[対数#対数の性質|底の変換]]公式を使うことになる。

:{{math|1=log<sub>2</sub> ''n'' = ln ''n'' / ln 2 = Log ''n'' / Log 2}}

従って、
:{{math|1=log<sub>2</sub> ''n'' = log<sub>e</sub>''n'' × 1.442695... = log<sub>10</sub> ''n'' × 3.321928...}}
となる。

ところでこの式は、{{math|1=log<sub>e</sub> ''n'' + log<sub>10</sub> ''n''}} が0.6%以内の差で {{math|1=log<sub>2</sub> ''n''}} と一致する、という興味深い結果を与える。実際のところ、{{math|1=log<sub>e</sub> ''n'' + log<sub>10</sub> ''n''}} という式は、
:<math>e^{1/(1+\log_{10} e)} = 10^{1/(1+\log_e 10)} = 2.00813\ 59293\ 46243\ 95422\ 87563\ 25191\ldots</math>
という底を用いて、{{math|1=log<sub>2.0081359...</sub> ''n''}} と表現される。

== 二進対数の算出 ==
=== 整数→整数 ===
小数点以下の切り上げ・切り捨てを行って、整数→整数の二進対数を定めることができる。これら二つ（切り上げ・切り下げ）の整数二進対数の間には、
:<math>\lfloor \log_2 n \rfloor = \lceil \log_2 (n + 1) \rceil - 1</math>　　ただし、{{math|1=1 ≦ ''n''}}
の関係がある<ref name="Hackers">{{Cite book | title=[[Hacker's Delight]] | first1=Henry S. | last1=Warren Jr. | year=2002 | publisher=Addison Wesley | isbn=978-0-201-91465-8 | pages=215}}</ref>。この左辺の関数は、<math>\lfloor \log_2 0 \rfloor = -1</math> とおくことによって、定義域を {{math|1=''n'' ≧ 0}} にまで拡張できる。このように拡張した関数は、非負整数 {{mvar|n}} の {{mvar|m}} ビット符号なし二進表示における{{仮リンク|先頭の0の個数|en|number of leading zeros}} {{math|1=nlz(''n'')}} との間で
:<math>\lfloor \log_2 n \rfloor = (m-1) - \operatorname{nlz}(n)</math><ref name="Hackers" />
の関係にある。この整数二進対数は、{{mvar|n}} の最上位ビットがどこにあるかを示している。
<!--意味不明。コメントアウト。
したがってこれは、最下位1ビットの位置を求める{{仮リンク|最初の1検出|en|find first set}} (find first one) の補数表現 (complement) になっている。整数二進対数についてのアルゴリズムやアーキテクチャサポート、およびその応用について詳細は、{{仮リンク|Find first set|en|Find first set}}の項を参照。-->

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

# 整数部分 <math>\lfloor\operatorname{lb}\,x\rfloor</math> を計算する。
# 小数部分を計算する。

まず、整数部分の計算は簡単である。任意の正の実数 {{mvar|x}} に対して、{{math|1=2<sup>''n''</sup> ≦ ''x'' &lt; 2<sup>''n''+1</sup>}} となるような整数 {{mvar|n}} が唯一に定まる<ref>{{math|1=''x'' &lt; 1}} であっても {{mvar|n}} が定まることに注意。このときの {{mvar|n}} は負の数である。</ref>。この各辺を {{math|1=2<sup>''n''</sup>}} で割った {{math|1=1 ≦ ''x''/2<sup>''n''</sup> &lt; 2}} という式を立ててもよい。これをもって、二進対数の整数部分を {{mvar|n}} と定める。そして、この {{mvar|n}} を使って、小数部分を {{math|1=lb (''x''/2<sup>''n''</sup>)}} と表記することにする。すなわち、{{math|1=''y'' = ''x''/2<sup>''n''</sup>}} と置くと、次のようになる。
:{{math|1=lb ''x'' = ''n'' + lb ''y''}}　　ただし、{{math|1=1 ≦ ''y'' &lt; 2}}

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

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

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

:<math>\begin{align}
\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{align}</math>

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

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

しかし実際には幸いなことに、このような高コストな計算も、無限級数の切り捨ても必要とせずに、
# 値を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ビットの精度で計算する（すなわち、上記の関数を <code>lb(1.65, 4)</code> として呼び出す）ケースを考える。このプログラムを逐次追いかけていくと次のようになる。
* まず、このプログラムでは整数位の計算が既に終わっていることを前提とする（すなわち、{{math|1=1 ≦ ''y'' &lt; 2}} となっていることを要求する）ので、無条件で "0．" の2文字を書く。
* 与えられた {{math|1=''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という数字列を得たので、
:{{math|1=lb 1.65 ≒ 0.1011<sub>(2)</sub> = 13/16}}
と確定させる。このとき、誤差は1/16未満となっている。さらにもう1ビット計算すれば27/32となり、誤差は1/32未満となる。一般に、{{mvar|m}} ビットの精度がほしい（すなわち、誤差を {{math|1=(1/2)<sup>1+''m''</sup>}} 未満としたい）ときには、2乗の計算をちょうど {{mvar|m}} 回、2で割る計算を最大 {{mvar|m}} 回行えば必要十分である。

== 関連項目 ==
* [[常用対数]]
* [[自然対数]]
* [[二進法]]
* [[2の冪]]
* [[2の自然対数]]

== 脚注 ==
{{reflist}}

{{デフォルトソート:にしんたいすう}}
[[Category:解析学]]
[[Category:初等数学]]
[[Category:初等関数]]
[[Category:対数]]
[[Category:数学に関する記事]]