二進対数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
log2 nグラフ

二進対数 (にしんたいすう)は数学において、2とする対数 log2 n である。n ↦ 2n逆写像でもある。n の二進対数は、2冪乗ある値nにならなければいけない数である。よって、二進対数は、2の冪すなわち2倍にすることを含むどんなものに対しても有用である。例えば、十進法1, 2, 4, 8, 16, 32 は二進対数では、0, 1, 2, 3, 4, 5 となる。

コンピューターへの応用[編集]

情報理論[編集]

二進対数は、二進法と密接に関係しているため、計算機科学情報理論でしばしば使われる。この文脈において、lg n とよく書かれる[1]。同じ関数の別の表記としてときどき(特にドイツ語で)使われるものとして ld n があり、これはラテン語の logarithmus duālis から来ている[2]。ただし ISO 31-11英語版では、lg (n) は log10 n と見なされるので、lb (n) と表記すべきだと規定されている。正の整数 n2進数におけるの数(ビットのこと)は 1 + lb n の整数部分であり、以下の床関数で表される。

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

情報理論では、自己情報量英語版情報量の定義は二進対数を含んでいる。これは情報量の単位であるビットあるいはシャノンが、同一確率の2つの事象の一方の発生から得られる情報量を表すためである。

計算複雑性[編集]

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

しかし、アルゴリズムの実行時間は通常、定数部分を無視して、ランダウの記号で表記される。k が1より大きい数を取る時、log2 n = (1/logk 2)logk n であるので、O(log2 n) の実行時間をもつアルゴリズムは、例えば、O(log13 n) の時間で実行できるともいえる。ゆえに、O(log n) や O(n log n) といった式の対数の底は重要ではない。ただし、他の文脈では対数の底を指定することが必要な場合もある。例えば O(2lb n) は O(2ln n) とは同じ時間では終わらない、前者は O(n) と同じで、後者は O(n0.6931...) と同じだからである。

n lb n の実行時間をもつアルゴリズムは、しばしば線形対数と呼ばれる。O(lb n) や O(n lb n) の実行時間をもつアルゴリズムの例として以下があげられる。

電卓の使用法[編集]

log2のボタンを持たない電卓でlog2(n)を計算する簡単な方法は、関数電卓で最も見受けられる自然対数"ln"と常用対数"log"のボタンを使う方法である。この方法に対する特別な底の変換公式は以下のようになる。

log2(n) = ln(n)/ln(2) = log(n)/log(2)

なので、

log2(n) = loge(n)×1.442695... = log10(n)×3.321928...

となる。これは、loge(n) + log10(n)が0.6%以内の差でlog2(n)と一致するという興味深い結果を与える。実際のところ、loge(n) + log10(n)は、e1/(1+log10e) = 101/(1 + loge10)≈ 2.00813 59293 46243 95422 87563 25191  (有効数字32桁まで)を底とするlog2.0081359...(n)である。

アルゴリズム[編集]

整数[編集]

整数定義域値域において、二進対数は端数処理で切り上げたり切り下げたり計算する事ができる。これらの整数の二進対数における2つの数式は次の公式と関連がある。

 \lfloor \log_2(n) \rfloor = \lceil \log_2(n + 1) \rceil - 1, \text{ if }n \ge 1 [3]

定義は、 \lfloor \log_2(0) \rfloor = -1とすることで拡張できる。この関数はx, nlz(x)で表される32ビットの無署名の二進数である先頭の0の個数英語版と関連している。

\lfloor \log_2(n) \rfloor = 31 - \operatorname{nlz}(n).[3]

整数の二進対数は、入力操作において最も有名な1ビットを意味する0を基調とした表記として、解釈することができる。初期設定の発見法英語版の記事は、整数の二進対数についてのアルゴリズムや技術的なサポート、応用面についてより詳細な情報を含んでいる。

実数[編集]

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

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

整数部分の計算は簡単である。任意の x > 0 に対して、2n ≤ x < 2n+1となるような、あるいは同じことだが、1 ≤ 2nx < 2 となるような、ただ1つの整数 n が存在する、。このとき、対数の整数部分は単純に n であり、小数部分はlb(2nx)である。言い換えると

\operatorname{lb}(x) = n + \operatorname{lb}(y) \quad\text{where } y = 2^{-n}x \text{ and } y \in [1,2)

結果の小数部分は\operatorname{lb} yであり、初等的な掛け算割り算のみを使って再帰的に計算できる。小数部分の計算方法は以下の手順になる。

  1. まず、実数y \in [1,2)から始める。y=1ならば、小数部分は0となって、その時点で終了である。
  2. y=1でなければ、y2乗することを結果が z \in [2,4) になるまで繰り返す。2乗した回数を m とする。すなわち、z = y^{2\uparrow m} であって、mz \in [2,4) となるように選ばれている。
  3. 両辺の対数をとり、いくつかの演算を施す。
    \begin{align}
\operatorname{lb}\,z &= 2^m \operatorname{lb}\,y \\
\operatorname{lb}\,y &= \frac{ \operatorname{lb} z }{ 2^m } \\
&= \frac{ 1 + \operatorname{lb}(z/2) }{ 2^m } \\
&= 2^{-m} + 2^{-m}\operatorname{lb}(z/2)
\end{align}
  4. z/2 は再び区間 [1,2) にある実数であることに注意する。
  5. 手順1に戻り、z/2の二進対数を、同じ手法で繰り返し計算する。

この結果は、以下の式で説明される。ただし、m_i はアルゴリズムの i 番目の繰り返しにおいて2乗を行った回数である。

\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}

手順1において小数部分が0であることが分かった場合、これはあるところで終了する「有限」列である。そうでなければ、m_i>0 だから各項がその前の項よりも真に小さいため、比較判定法によって収束する無限級数である。実用的な使用においては、この無限級数は近似値になるように切り捨てられなければならない。級数のi番目の項より後ろを切り捨てられたならば、最終結果における誤差2^{-(m_1+m_2+\cdots+m_i)}より小さいとなる。

幸運な事に、実際は演算や無限級数の切り捨てを全くせずに、計算をして誤差の幅を知る事ができる。1.65の二進対数を小数点以下4桁まで計算したいとしよう。以下の手順を、4回繰り返せば良い。

  1. 実数を2乗する。
  2. もし2乗した値が2以上であれば、2で割って1と書く。そうでなければ0と書く。

書いた数は2進法で書かれた対数である。これは1と2の間にあるどんな数で始めてもうまくいく。したがって

    • 1.65を2乗すると2.72となる。これは2より大きいので、半分にして1.36を得、小数点1桁目は1と書く。
    • 1.36を2乗すると1.85となる。これは2より小さいので、半分にせず、小数点2桁目は0と書く。
    • 1.85を2乗すると3.43となる。これは2より大きいので、半分にして1.72を得、小数点3桁目は1と書く。
    • 1.72を2乗すると2.95となる。これは2より大きいので、小数点4桁目は1と書く(4桁目で計算終了なので、2.95を半分にする必要はない)

1011まで書くと、1.65の二進対数を二進法で表した数字は0.1011(分数として表記すると13/16)になり、誤差は1/16より小さくなる。1/32のくらいまで計算した時は、27/32であり誤差は1/32より小さくなる。一般に、0.5 の 1+N 乗より小さい誤差を得るためには、N回2乗することと高々N回半分にする事が必要である。

関連項目[編集]

脚注[編集]

  1. ^ Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. p. 34. ISBN 0-262-03293-7. 
  2. ^ 例えば次を見よ。Bauer, Friedrich L. (2009), Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum, Springer Science & Business Media, p. 54, ISBN 9783642029929, http://books.google.com/books?id=y4uTaLiN-wQC&pg=PA54 .
  3. ^ a b Warren Jr., Henry S. (2002). Hacker's Delight. Addison Wesley. pp. 215. ISBN 978-0-201-91465-8.