Editing Binary logarithm (section)

===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"/>