二進対数
二進対数 (にしんたいすう、英: binary logarithm)とは、2を底とする対数 log2 x のことである。これは、指数関数 x → 2 の逆関数でもある。
lb z = 2 m lb y lb y = lb  z 2 m = 1 + lb  ( z / 2 ) 2 m = 2 − m + 2 − m lb  ( z / 2 ) {\displaystyle {\begin{aligned}\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{aligned}}}
この m の値を記録しておく。
2乗する作業をやめる基準は 2 ≦ z < 4 であった。したがって、1 ≦ z/2 < 2 となっている。そこであらためて y := z/2 と置き、この新しい y の二進対数を同じ手法で計算する。
そして最終的に、lb x を次のように計算する。以下、m[i] は、アルゴリズムの i 回目の繰り返しにおいて2乗の操作を行った回数とする。
lb x = n + 2 − m [ 1 ] ( 1 + 2 − m [ 2 ] ( 1 + 2 − m [ 3 ] ( 1 + ⋯ ) ) ) = n + 2 − m [ 1 ] + 2 − m [ 1 ] − m [ 2 ] + 2 − m [ 1 ] − m [ 2 ] − m [ 3 ] + ⋯ {\displaystyle {\begin{aligned}\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{aligned}}}