二進対数

正の整数nの二進数表現の桁数 (ビット数)は1 + log ₂ nの整数部分です。つまり^{[ 12 ]}

${\displaystyle \lfloor \log _{2}n\rfloor +1.}$

情報理論では、自己情報量と情報エントロピーの定義は、ビットを情報の基本単位とすることに対応するバイナリ対数で表現されることが多い。これらの単位を用いると、シャノン・ハートレーの定理は、チャネルの情報容量を信号対雑音比のバイナリ対数に1を加えたものとして表現する。ただし、これらの定義の別の表記法として自然対数とnatも使用される。^{[ 26 ]}

自然対数は数論や数学解析などの純粋数学の多くの分野で二進対数よりも重要であるが、^{[ 27 ]}二進対数は組み合わせ論においていくつかの応用例がある。

• n個の葉を持つすべての二分木は、少なくともlog ₂ n の高さを持ち、nが2 のべき乗で、木が完全二分木である場合は等号が成り立つ。^{[ 28 ]}同様に、n本の支流を持つ河川系のシュトララー数は、最大でlog ₂ n + 1である。^{[ 29 ]}
• n 個の異なる集合からなる任意の集合族は、その和集合に少なくともlog ₂ n個の要素を持ち、集合族が冪集合である場合は等号が成り立つ。^{[ 30 ]}
• n個の頂点を持つすべての部分立方体は、少なくともlog ₂ n の等長次元を持ち、最大で 1 / 2 n log 2 n の辺を持ち 、部分立方体がハイパー_キューブグラフである場合は等号が成り立つ。^{[ 31 ]}
• ラムゼーの定理によれば、すべてのn頂点無向グラフは、 nの対数サイズのクリークまたは独立集合のいずれかを持つ。保証できる正確なサイズは不明だが、そのサイズに関する既知の最良の境界は二進対数を含む。特に、すべてのグラフは少なくとも 1 / 2 log 2 n (1 − o (1)) サイズのクリークまたは独立集合を持ち、ほとんどすべてのグラフは2 log 2 n ₍ 1 ₊ o ( 1 ) )より大きいサイズのクリークまたは独立集合を持たない。^{[ 32 ]}
• ギルバート・シャノン・リードのランダムシャッフルモデルの数学的解析から、 n枚のカードのデッキをリフルシャッフルでシャッフルして、ほぼ一様ランダムな順列分布を得るには、およそ 3 / 2 log 2 n の回数が必要であることが示せる。この計算は_、52枚のカードのデッキを 7 回シャッフルするという推奨事項の根拠となっている。^{[ 33 ]}

バイナリ対数はアルゴリズムの解析にも頻繁に登場します。^{[ 19 ]}これは、アルゴリズムでバイナリ数の演算が頻繁に使用されるためだけでなく、バ​​イナリ対数が双方向分岐に基づくアルゴリズムの解析にも登場するためでもあります。^{[ 14 ]} 問題が最初にn個の解の選択肢を持ち、アルゴリズムの各反復で選択肢の数が 2 分の 1 に減少する場合、1 つの選択肢を選択するために必要な反復回数は、再びlog ₂ nの整数部分になります。この考え方は、いくつかのアルゴリズムとデータ構造の解析で使用されます。たとえば、バイナリサーチでは、解決する問題のサイズは各反復で半分になるため、サイズnの問題の解を得るには、おおよそlog ₂ n回の反復が必要です。^{[ 34 ]}同様に、n個の要素を含む完全にバランスの取れたバイナリサーチツリーの高さはlog ₂ ( n + 1) − 1です。^{[ 35 ]}

アルゴリズムの実行時間は通常、定数係数と低次の項を省略して式を簡略化するために使用されるビッグ O 記法で表されます。異なる底の対数は定数係数のみが異なるため、 O (log ₂ n )の時間で実行されるアルゴリズムは、たとえばO (log ₁₃ n )の時間で実行されるとも言えます。したがって、O (log n )やO ( n log n )のような式の対数の底は重要ではなく、省略できます。^{[ 11 ] [ 36 ]}ただし、時間制限の指数に現れる対数については、対数の底を省略することはできません。たとえば、O (2 ^{log ₂ n} )はO (2 ^{ln n} )とは異なります。前者はO ( n )に等しく、後者はO ( n ^0.6931... )に等しいからです。

実行時間がO ( n  log n )のアルゴリズムは、 線形アルゴリズムと呼ばれることがあります。^{[ 37 ]}実行時間がO (log n )またはO ( n log n )のアルゴリズムの例をいくつか挙げます。

• 平均時間クイックソートおよびその他の比較ソートアルゴリズム^{[ 38 ]}
• バランスのとれた二分探索木での検索^{[ 39 ]}
• 二乗による指数計算^{[ 40 ]}
• 最長増加部分列^{[ 41 ]}

分割統治アルゴリズムの中には、時間制限の指数にバイナリ対数が含まれるものもある。例えば、nビット数を乗算する時間O ( n ^{log ₂ 3} )のカラツバアルゴリズム^{[ 42 ]} や、n × n行列を乗算する時間 O ( n ^{log ₂ 7} )のストラッセンアルゴリズム^{[ 43 ]}などである。これらの実行時間にバイナリ対数が含まれることは、分割統治再帰のマスター定理を参照することで説明できる。

バイオインフォマティクスでは、マイクロアレイは、生物学的材料のサンプルでさまざまな遺伝子がどの程度強く発現しているかを測定するために使用されます。遺伝子のさまざまな発現速度は、発現速度の比の二進対数を使用して比較されることがよくあります。2 つの発現速度の対数比は、2 つの速度の比の二進対数として定義されます。二進対数を使用すると、発現速度を簡単に比較できます。たとえば、2 倍の発現速度は log 比1で表すことができ、半分の発現速度は log 比-1で表すことができ、変化のない発現速度は log 比 0 で表すことができます。^{[ 44 ]}

このようにして得られたデータポイントは、座標軸の一方または両方が強度比の二進対数である散布図として、あるいはこれらの対数比散布図を回転および拡大縮小するMAプロットやRAプロットなどの視覚化として視覚化されることが多い。^{[ 45 ]}

音楽理論では、 2 つの音の間の音程または知覚的な差は、それらの周波数の比によって決定されます。分子と分母が小さい有理数の比から生じる音程は、特に心地よい音として知覚されます。これらの音程の中で最も単純で重要なものはオクターブであり、周波数比は2:1です。2 つの音が異なるオクターブの数は、それらの周波数比の二進対数です。^{[ 46 ]}

音程システムや、音のより細かい区別を必要とする音楽理論の他の側面を研究するには、オクターブよりも細かい、乗法（周波数比のように）ではなく加法（対数のように）である音程の大きさの尺度があると便利です。つまり、音x、y、zが上昇音列を形成する場合、 xからyまでの音程の尺度とyからzまでの音程の尺度を足したものが、xからzまでの音程の尺度と等しくなります。このような尺度はセントで与えられ、セントはオクターブを1200 個の等しい音程（それぞれ100セントの12 個の半音）に分割します。数学的には、周波数f ₁とf ₂の音が与えられた場合、 f _1からf ₂までの音程のセント数は^{[ 46 ]}です。

${\displaystyle \left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\right|.}$

ミリオクターブも同様に定義されるが、乗数は1200ではなく1000である。^{[ 47 ]}

各試合またはマッチに2人のプレイヤーまたはチームが参加する競技ゲームやスポーツでは、バイナリ対数は、勝者を決定するために必要なシングルエリミネーション トーナメントのラウンド数を示します。たとえば、4人のプレイヤーのトーナメントでは、勝者を決定するためにlog ₂ 4 = 2ラウンドが必要であり、 32チームのトーナメントでは、 log ₂ 32 = 5ラウンドが必要です。この場合、nが 2 のべき乗でないn 人のプレイヤー/チームの場合、残りのすべての競技者がプレイしないラウンドが少なくとも 1 回必要であるため、 log ₂ nは切り上げられます。たとえば、log ₂ 6は約2.585であり、切り上げると3になります。これは、 6チームのトーナメントでは3ラウンドが必要であることを示しています (最初のラウンドで 2 チームが棄権するか、2 番目のラウンドで 1 チームが棄権するかのいずれかです)。スイス システムのトーナメントで明確な勝者を決定するためにも、同じラウンド数が必要です。^{[ 48 ]}

写真において、露出値は、人間の視覚系の光に対する対数的な反応を記述するウェーバー・フェヒナーの法則に従って、フィルムまたはセンサーに到達する光量の二進対数で測定されます。1段の露出は、底が2の対数スケールで1単位です。^{[ 49 ] [ 50 ]}より正確には、写真の露出値は次のように定義されます。

$\displaystyle \log _{2}{\frac {N^{2}}{t}}}$

ここで、Nは露光中のレンズの絞りを測定するf値であり、 tは露光時間（秒）である。^{[ 51 ]}

濃度測定では、感光性材料やデジタルセンサーのダイナミックレンジを表すために、バイナリ対数（ストップ数で表される）も使用されます。 ^{[ 52 ]}

log ₂関数がない電卓でlog ₂ nを計算する簡単な方法は、ほとんどの科学電卓にある自然対数( ln ) または常用対数( logまたはlog ₁₀ ) 関数を使用することです。対数の底をe、10、またはその他の任意の底bから 2 に変更するには、次の式を使用できます。^{[ 50 ] [ 53 ]}

${\displaystyle \log _{2}n={\frac {\ln n}{\ln 2}}={\frac {\log _{10}n}{\log _{10}2}}={\frac {\log _{b}n}{\log _{b}2}}\,.}$

おおよそ、^{[ 54 ] [ 55 ]}

${\displaystyle \log _{2}n\approx 1.442695\ln n\approx 3.321928\log _{10}n\,.}$

二進対数は、整数から整数への関数、または整数から整数への関数として、切り上げまたは切り下げによって定義できます。これら2つの形式の整数二進対数は、次の式で関連付けられます。

${\displaystyle \lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{n \geq 1 の場合}}$^{[ 56 ]}

定義は、定義することによって拡張できます${\displaystyle \lfloor \log _{2}(0)\rfloor =-1}$このように拡張されたこの関数は、xの 32 ビット符号なしバイナリ表現の先頭ゼロの数nlz( x )に関連しています。

$\displaystyle \lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (n).}$^{[ 56 ]}

整数バイナリ対数は、入力の最上位1ビットのゼロベースのインデックスとして解釈できます。この意味では、最下位1ビットのインデックスを見つける最初のセットを見つける操作の補数です。多くのハードウェア プラットフォームには、先頭のゼロの数を見つける機能、またはバイナリ対数をすばやく見つけるために使用できる同等の操作のサポートが含まれています。Linuxカーネル^{[ 57 ]}およびlibcソフトウェア ライブラリの一部のバージョンの関数もバイナリ対数を計算します (整数に切り上げて 1 を加算)。flsflsl

数の場合${\displaystyle x}$浮動小数点では次のように表されます${\displaystyle x=2^{E}(1+m)}$整数指数${\displaystyle E}$そして仮数${\displaystyle m}$範囲内${\displaystyle 0\leq m<1}$バイナリ対数は、おおよそ次のように近似できます。${\displaystyle \log _{2}x\approx E+m}$[ ^{16 ]}この近似は仮数の範囲の両端では正確ですが、範囲の中央では対数を過小評価し、仮数が約0.44のときに最大誤差が約0.086に達します。これを、区分的線形関数を使用することでより正確にすることが^できます。${\displaystyle m}$[ ^{58 ]あるいはもっと大まかに言え}ば定数補正項を加えることによって${\displaystyle \log _{2}x\approx E+m+\sigma }$例えば、${\displaystyle \sigma \approx 0.043}$最大誤差を半分にする。高速逆平方根アルゴリズムはこのアイデアを使用しており、異なる補正項は次のように推測できる。${\displaystyle \sigma \approx 0.0450466}$バイナリ表現を直接操作することによって${\displaystyle x}$この近似対数を掛ける${\displaystyle -{\tfrac {1}{2}}}$浮動小数点値を近似して取得します${\displaystyle 1/{\sqrt {x}}}$[ ^{59 ]​}

一般的な正の実数に対して、二進対数は2つの部分で計算できます。^{[ 60 ]} まず、整数部分を計算し、${\displaystyle \lfloor \log _{2}x\rfloor }$（対数の特性と呼ばれる）。これにより、対数の引数が区間[ 1, 2)に限定された範囲にある問題に帰着し、小数部（対数の仮数）を計算する第 2 段階が簡略化される。任意のx > 0に対して、 2 ⁿ ≤ x < 2 ^{n +1}または同等に1 ≤ 2 ^{− n} x < 2となる一意の整数nが存在する。これで、対数の整数部は単にnとなり、小数部はlog ₂ (2 ^{− n} x )となる。^{[ 60 ]} 言い換えれば、

${\displaystyle \log _{2}x=n+\log _{2}y\quad {\text{ただし}}y=2^{-n}x{\text{かつ}}y\in [1,2)}$

正規化された浮動小数点数の場合、整数部分は浮動小数点指数によって与えられ、^{[ 61 ]}整数の場合は、先頭のゼロを数える操作を実行することによって決定できます。^{[ 62 ]}

結果の小数部分はlog ₂ yであり、基本的な乗算と除算のみを使用して反復的に計算できます。^{[ 60 ]} 小数部分を計算するアルゴリズムは、擬似コードで次のように記述できます。

1. 半開区間[ 1, 2)内の実数yから始めます。y = 1の場合、アルゴリズムは終了し、小数部はゼロになります。
2. そうでない場合は、結果z が区間[ 2, 4)に入るまでy を繰り返し二乗します。必要な二乗の回数をmとします。つまり、z = y ^{2 m}で、mはzが[ 2, 4)に入るように選択されます。
3. 両辺の対数を取って代数計算を行うと次のようになります。$${\displaystyle {\begin{aligned}\log _{2}z&=2^{m}\log _{2}y\\\log _{2}y&={\frac {\log _{2}z}{2^{m}}}\\&={\frac {1+\log _{2}(z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\log _{2}(z/2).\end{aligned}}}$$
4. ここでも、z /2は区間[ 1, 2)内の実数です。ステップ 1 に戻り、同じ方法を使用してz /2の二進対数を計算します。

その結果は、次の再帰式で表され、${\displaystyle m_{i}}$は、アルゴリズムの i番目の反復で必要となる二乗の回数です。$${\displaystyle {\begin{aligned}\log _{2}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{aligned}}}$$

ステップ 1 の小数部分がゼロである特殊なケースでは、これはある時点で終了する有限数列です。それ以外の場合は、各項が前の項より厳密に小さい (すべてのm _i > 0であるため)ため、比率テストに従って収束する無限級数です。ホーナーの方法を参照してください。実用上、この無限級数は近似結果を得るために打ち切る必要があります。級数がi番目の項で打ち切られると、結果の誤差は2 ^{−( m ₁ + m ₂ + ⋯ + m _i )}より小さくなります。^{[ 60 ]}

このlog2関数は標準Cの数学関数に含まれています。この関数のデフォルトバージョンは倍精度引数を受け取りますが、バリアントでは引数を単精度またはlong doubleにすることができます。^{[ 63 ]} MATLABなどの複素数と暗黙的な型変換をサポートする計算環境では、関数の引数に負の数を指定でき、複素数を返します。^{[ 64 ]}log2