Content deleted Content added
Yuval Filmus (talk | contribs) →Linear time multiplication: This section is very confusing. Knuth is describing the Schönhage–Strassen algorithm (or one of their algorithms); a discussion on machine models can be useful, and can be based on the recent preprint of Fürer. |
Pat power11 (talk | contribs) |
||
Line 206:
== Shift and add ==
Historically, computers used a "shift and add" algorithm
In base 2, multiplying by the single digit of the multiplier reduces to a simple series of [[logical AND]] operations. Each partial product is added to a running sum as soon as each partial product is computed. Most currently available microprocessors implement this or other similar algorithms (such as [[Booth encoding]]) for various integer and floating-point sizes in [[hardware multiplier]]s or in [[microcode]].
| |||