Editing Binary logarithm (section)

==Calculation==
[[File:HP-35 Red Dot.jpg|thumb|upright=0.75|[[HP-35]] [[scientific calculator]] (1972). The log and ln keys are in the top row; there is no log<sub>2</sub> key.]]

===Conversion from other bases===
An easy way to calculate {{math|log<sub>2</sub>{{hsp}}''n''}} on [[calculator]]s that do not have a {{math|log<sub>2</sub>}} function is to use the [[natural logarithm]] ({{math|ln}}) or the [[common logarithm]] ({{math|log}} or {{math|log<sub>10</sub>}}) functions, which are found on most [[scientific calculator]]s. To [[Logarithm#Change of base|change the logarithm base]] to 2 from {{mvar|e}}, {{math|10}}, or any other base {{mvar|b}}, one can use the [[formulae]]:<ref name="btzs"/><ref>{{citation|title=Secret History: The Story of Cryptology|first=Craig P.|last=Bauer|publisher=CRC Press|year=2013|isbn=978-1-4665-6186-1|page=332|url=https://books.google.com/books?id=EBkEGAOlCDsC&pg=PA332}}.</ref>

:<math>\log_2 n = \frac{\ln n}{\ln 2} = \frac{\log_{10} n}{\log_{10} 2} = \frac{\log_{b} n}{\log_{b} 2}\,.</math>
Approximately,<ref>{{Cite OEIS|A007525|Decimal expansion of log_2 e}}</ref><ref>{{Cite OEIS|A020862|Decimal expansion of log_2(10)}}</ref>
:<math>\log_2 n \approx 1.442695\ln n \approx 3.321928\log_{10} n\,.</math>

===Integer rounding===
The binary logarithm can be made into a function from integers and to integers by [[rounding]] it up or down.  These two forms of integer binary logarithm are related by this formula:

:<math> \lfloor \log_2(n) \rfloor = \lceil \log_2(n + 1) \rceil - 1, \text{ if }n \ge 1.</math><ref name="Warren_2002">{{citation |title=Hacker's Delight |title-link=Hacker's Delight |first=Henry S. |last=Warren Jr. |date=2002 |edition=1st |publisher=[[Addison Wesley]] |isbn=978-0-201-91465-8 |page=215}}</ref>
The definition can be extended by defining <math> \lfloor \log_2(0) \rfloor = -1</math>. Extended in this way, this function is related to the [[number of leading zeros]] of the 32-bit unsigned binary representation of {{mvar|x}}, {{math|nlz(''x'')}}.
:<math>\lfloor \log_2(n) \rfloor = 31 - \operatorname{nlz}(n).</math><ref name="Warren_2002" />

The integer binary logarithm can be interpreted as the zero-based index of the most significant {{math|1}} bit in the input. In this sense it is the complement of the [[find first set]] operation, which finds the index of the least significant {{math|1}} bit. Many hardware platforms include support for finding the number of leading zeros, or equivalent operations, which can be used to quickly find the binary logarithm. The <code>fls</code> and <code>flsl</code> functions in the [[Linux kernel]]<ref>[https://www.kernel.org/doc/htmldocs/kernel-api/API-fls.html fls], Linux kernel API, [[kernel.org]], retrieved 2010-10-17.</ref> and in some versions of the [[libc]] software library also compute the binary logarithm (rounded up to an integer, plus one).

===Piecewise-linear approximation===
For a number <math>x</math> represented in [[floating point]] as <math>x=2^E(1+m)</math>, with integer exponent <math>E</math> and [[significand|mantissa]] <math>m</math> in the range <math>0\le m<1</math>, the binary logarithm can be roughly approximated as <math>\log_2 x\approx E+m</math>.<ref name=mitchell/> This approximation is exact at both ends of the range of mantissas but underestimates the logarithm in the middle of the range, reaching a maximum error of approximately 0.086 at a mantissa of approximately 0.44. It can be made more accurate by using a [[piecewise linear function]] of <math>m</math>,<ref>{{citation
 | last1 = Combet | first1 = M.
 | last2 = Van Zonneveld | first2 = H.
 | last3 = Verbeek | first3 = L.
 | date = December 1965
 | doi = 10.1109/pgec.1965.264080
 | issue = 6
 | journal = IEEE Transactions on Electronic Computers
 | pages = 863–867
 | title = Computation of the base two logarithm of binary numbers
 | volume = EC-14}}</ref> or more crudely by adding a constant correction term <math>\log_2 x\approx E+m+\sigma</math>. For instance choosing <math>\sigma\approx 0.043</math> would halve the maximum error. The [[fast inverse square root]] algorithm uses this idea, with a different correction term that can be inferred to be <math>\sigma\approx 0.0450466</math>, by directly manipulating the binary representation of <math>x</math> to multiply this approximate logarithm by <math>-\tfrac12</math>, obtaining a floating point value that approximates <math>1/\sqrt x</math>.<ref>{{citation
|url=http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf
|title=The Mathematics Behind the Fast Inverse Square Root Function Code
|last=McEniry
|first=Charles
|date=August 2007
|archive-url=https://web.archive.org/web/20150511044204/http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf
|archive-date=2015-05-11}}</ref>

===Iterative approximation===

For a general [[positive number|positive real number]], the binary logarithm may be computed in two parts.<ref name="ml73">{{citation
 | last1 = Majithia | first1 = J. C.
 | last2 = Levan | first2 = D.
 | doi = 10.1109/PROC.1973.9318
 | issue = 10
 | journal = Proceedings of the IEEE
 | pages = 1519–1520
 | title = A note on base-2 logarithm computations
 | volume = 61
 | year = 1973}}.</ref>
First, one computes the [[Floor and ceiling functions|integer part]], <math>\lfloor\log_2 x\rfloor</math> (called the characteristic of the logarithm).
This reduces the problem to one where the argument of the logarithm is in a restricted range, the interval {{closed-open|1, 2}}, simplifying the second step of computing the fractional part (the mantissa of the logarithm).
For any {{math|''x'' > 0}}, there exists a unique integer {{mvar|n}} such that {{math|2<sup>''n''</sup> ≤ ''x'' < 2<sup>''n''+1</sup>}}, or equivalently {{math|1 ≤ 2<sup>−''n''</sup>''x'' < 2}}.  Now the integer part of the logarithm is simply {{mvar|n}}, and the fractional part is {{math|log<sub>2</sub>(2<sup>−''n''</sup>''x'')}}.<ref name="ml73"/>  In other words:
:<math>\log_2 x = n + \log_2 y \quad\text{where } y = 2^{-n}x \text{ and } y \in [1,2)</math>
For normalized [[floating-point]] numbers, the integer part is given by the floating-point exponent,<ref>{{citation |title=Production Rendering: Design and Implementation |first=Ian |last=Stephenson |publisher=Springer-Verlag |year=2005 |isbn=978-1-84628-085-6 |url=https://books.google.com/books?id=BCC5aTR34C4C&pg=PA270 |pages=270–273 |contribution=9.6 Fast Power, Log2, and Exp2 Functions}}.</ref> and for integers it can be determined by performing a [[count leading zeros]] operation.<ref name="Warren_2013">{{Citation |title=Hacker's Delight |title-link=Hacker's Delight |first=Henry S. |last=Warren Jr. |date=2013 |orig-year=2002 |edition=2nd |publisher=[[Addison Wesley]] – [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8 |id=0-321-84268-5 |page=291 |contribution=11-4: Integer Logarithm|contribution-url=https://books.google.com/books?id=XD9iAwAAQBAJ&pg=PA291}}.</ref>

The fractional part of the result is {{math|log{{sub|2}} ''y''}} and can be computed iteratively, using only elementary multiplication and division.<ref name="ml73"/>
The algorithm for computing the fractional part can be described in [[pseudocode]] as follows:
# Start with a real number {{mvar|y}} in the half-open interval {{closed-open|1, 2}}.  If {{math|1=''y'' = 1}}, then the algorithm is done, and the fractional part is zero.
# Otherwise, square {{mvar|y}} repeatedly until the result {{mvar|z}} lies in the interval {{closed-open|2, 4}}.  Let {{mvar|m}} be the number of squarings needed.  That is, {{math|1=''z'' = ''y''<sup>2<sup>''m''</sup></sup>}} with {{mvar|m}} chosen such that {{mvar|z}} is in {{closed-open|2, 4}}.
# Taking the logarithm of both sides and doing some algebra: <math display="block">\begin{align}
 \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{align}</math>
# Once again {{math|''z''/2}} is a real number in the interval {{closed-open|1, 2}}. Return to step 1 and compute the binary logarithm of {{math|''z''/2}} using the same method.

The result of this is expressed by the following recursive formulas, in which <math>m_i</math> is the number of squarings required in the ''i''-th iteration of the algorithm:
<math display="block">\begin{align}
 \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{align}</math>

In the special case where the fractional part in step 1 is found to be zero, this is a ''finite'' sequence terminating at some point.  Otherwise, it is an [[infinite series]] that [[convergent series|converge]]s according to the [[ratio test]], since each term is strictly less than the previous one (since every {{math|''m''<sub>''i''</sub> > 0}}). See [[Horner's method]]. For practical use, this infinite series must be truncated to reach an approximate result.  If the series is truncated after the {{mvar|i}}-th term, then the error in the result is less than {{math|2<sup>−(''m''<sub>1</sub> + ''m''<sub>2</sub> + ⋯ + ''m''<sub>''i''</sub>)</sup>}}.<ref name="ml73"/>

===Software library support===
The <code>log2</code> function is included in the standard [[C mathematical functions]]. The default version of this function takes [[double precision]] arguments but variants of it allow the argument to be single-precision or to be a [[long double]].<ref>{{citation | url=http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf | title=ISO/IEC 9899:1999 specification | page=226| contribution = 7.12.6.10 The log2 functions }}.</ref> In computing environments supporting [[complex number|complex numbers]] and implicit type conversion such as [[MATLAB]] the argument to the <code>log2</code> function is allowed to be a [[negative number]], returning a complex one.<ref>{{citation|title=The Matlab® 5 Handbook|first1=Darren|last1=Redfern|first2=Colin|last2=Campbell|publisher=Springer-Verlag|year=1998|isbn=978-1-4612-2170-8|url=https://books.google.com/books?id=KQDaBwAAQBAJ&pg=PA141|page=141}}.</ref>