二進対数

出典: フリー百科事典『ウィキペディア(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 となる。

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

情報理論[編集]

二進対数は、二進法と密接に関係しているため、計算機科学情報理論でしばしば使われる。ラテン語の logarithmus duālis から ld nlg n とよく表記される。ただし 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 [1]

定義は、 \lfloor \log_2(0) \rfloor = -1と明確にする事で満たす事が出来る。この関数はx, nlz(x)で表される32ビットの無署名の二進数である初期設定の発見法英語版と関連している。

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

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

実数[編集]

一般的な正の数において、二進対数は2つの手順で計算されるはずである。

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

整数部分の計算は簡単である。x > 0において、2n ≤ x < 2n+1となるような特別な整数nを仮定すると、1 ≤ 2nx < 2と等しくなる。この時、対数の整数部分は即ち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でなければ、yを再び2乗し、得られた結果をz \in [2,4)と置く。ここで、2乗する数に必要な、ある数mを仮定しよう。すると、z \in [2,4)の範囲内で、mを用いた数式はz = y^{2\uparrow m}となる。
  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_iiは、アルゴリズムにおけるi番目の繰り返しであることを意味する。)で表される以下の公式で説明される。

\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であるが故に、どの項も1つ前の項より絶対に小さくなるためである。実用的な方法では、この無限級数は近似値になるように切り捨てられるに違いない。もしある級数がi番目の項より後ろを切り捨てられたならば、最終結果との誤差2^{-(m_1+m_2+\cdots+m_i)}より小さいとなる。

幸運な事に、実際はいくつかの演算や無限級数の繰り返しをする事なく、計算をして誤差を知る事ができる。試しに、1.65の二進対数を小数点以下4桁まで計算してみよう。前述の手順を、4回繰り返せば良い。

  1. 実数を2乗する。
  2. もし2乗した値が2より大きければ、2で割って1より大きければ1と記入し、1より小さければ0と記入する。

1.65を二進法によって計算し、対数として書くと以下のようになる。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より小さくなる。一般に、1+Nと表されるように0.5より小さい誤差を得るためには、Nを2乗したり、Nより小さい数には半分にする事が必要である。

関連項目[編集]

脚注[編集]

  1. ^ a b Warren Jr., Henry S. (2002). Hacker's Delight. Addison Wesley. pp. 215. ISBN 978-0-201-91465-8.