Editing Horner's method (section)

===Application to floating-point multiplication and division===
{{main|binary logarithm#Calculation|multiplication algorithm#Shift and add}}

Horner's method is a fast, code-efficient method for multiplication and division of binary numbers on a [[microcontroller]] with no [[binary multiplier|hardware multiplier]].  One of the binary numbers to be multiplied is represented as a trivial polynomial, where (using the above notation) <math>a_i = 1</math>, and <math>x = 2</math>.  Then, ''x'' (or ''x'' to some power) is repeatedly factored out.  In this [[binary numeral system]] (base 2), <math>x = 2</math>, so powers of 2 are repeatedly factored out.

====Example====
For example, to find the product of two numbers (0.15625) and ''m'':
<math display="block">\begin{align}
  (0.15625) m & = (0.00101_b) m = \left( 2^{-3} + 2^{-5} \right) m = \left( 2^{-3})m + (2^{-5} \right)m \\
              & = 2^{-3} \left(m + \left(2^{-2}\right)m\right) = 2^{-3} \left(m + 2^{-2} (m)\right).
\end{align}</math>

====Method====
To find the product of two binary numbers ''d'' and ''m'':
# A register holding the intermediate result is initialized to ''d''.
# Begin with the least significant (rightmost) non-zero bit in ''m''. {{ordered list | list-style-type = lower-alpha | start = 2
| Count (to the left) the number of bit positions to the next most significant non-zero bit.  If there are no more-significant bits, then take the value of the current bit position.
| Using that value, perform a left-shift operation by that number of bits on the register holding the intermediate result}}
# If all the non-zero bits were counted, then the intermediate result register now holds the final result.  Otherwise, add d to the intermediate result, and continue in step 2 with the next most significant bit in ''m''.

====Derivation====
In general, for a binary number with bit values (<math> d_3 d_2 d_1 d_0 </math>) the product is
<math display="block"> (d_3 2^3 + d_2 2^2 + d_1 2^1 + d_0 2^0)m = d_3 2^3 m + d_2 2^2 m + d_1 2^1 m + d_0 2^0 m. </math>
At this stage in the algorithm, it is required that terms with zero-valued coefficients are dropped, so that only binary coefficients equal to one are counted, thus the problem of multiplication or [[division by zero]] is not an issue, despite this implication in the factored equation:
<math display="block"> = d_0\left(m + 2 \frac{d_1}{d_0} \left(m + 2 \frac{d_2}{d_1} \left(m + 2 \frac{d_3}{d_2} (m)\right)\right)\right). </math>

The denominators all equal one (or the term is absent), so this reduces to
<math display="block"> = d_0(m + 2 {d_1} (m + 2 {d_2} (m + 2 {d_3} (m)))),</math>
or equivalently (as consistent with the "method" described above)
<math display="block"> = d_3(m + 2^{-1} {d_2} (m + 2^{-1}{d_1} (m + {d_0} (m)))). </math>

In binary (base-2) math, multiplication by a power of 2 is merely a [[arithmetic shift|register shift]] operation.  Thus, multiplying by 2 is calculated in base-2 by an [[arithmetic shift]].  The factor (2<sup>−1</sup>) is a right [[arithmetic shift]], a (0) results in no operation (since 2<sup>0</sup> = 1 is the multiplicative [[identity element]]), and a (2<sup>1</sup>) results in a left arithmetic shift.
The multiplication product can now be quickly calculated using only arithmetic shift operations, addition and subtraction.

The method is particularly fast on processors supporting a single-instruction shift-and-addition-accumulate.  Compared to a C floating-point library, Horner's method sacrifices some accuracy, however it is nominally 13 times faster (16 times faster when the "[[canonical signed digit]]" (CSD) form is used) and uses only 20% of the code space.<ref>{{harvnb|Kripasagar|2008|p=62}}.</ref>