Content deleted Content added
No edit summary |
compress references |
||
Line 166:
In base 2, long multiplication reduces to a nearly trivial operation. For each '1' bit in the [[wikt:multiplier|multiplier]], shift the [[wikt:multiplicand|multiplicand]] an appropriate amount and then sum the shifted values. Depending on computer processor architecture and choice of multiplier, it may be faster to code this algorithm using hardware bit shifts and adds rather than depend on multiplication instructions, when the multiplier is fixed and the number of adds required is small.
This [[algorithm]] is also known as peasant multiplication, because it has been widely used among those who are unschooled and thus have not memorized the [[multiplication table]]s required by long multiplication.{{citation needed|date=April 2017}} The algorithm was also in use in ancient Egypt.<ref>{{Cite book |author=D. Wells |year=1987 |page=44 |title=The Penguin Dictionary of Curious and Interesting Numbers |publisher=Penguin Books}}</ref>.
On paper, write down in one column the numbers you get when you repeatedly halve the multiplier, ignoring the remainder; in a column beside it repeatedly double the multiplicand. Cross out each row in which the last digit of the first number is even, and add the remaining numbers in the second column to obtain the product.
Line 267 ⟶ 260:
Quarter square multipliers were used in [[analog computer]]s to form an [[analog signal]] that was the product of two analog input signals. In this application, the sum and difference of two input [[voltage]]s are formed using [[operational amplifier]]s. The square of each of these is approximated using [[piecewise linear function|piecewise linear]] circuits. Finally the difference of the two squares is formed and scaled by a factor of one fourth using yet another operational amplifier.
In 1980, Everett L. Johnson proposed using the quarter square method in a [[Digital data|digital]] multiplier.<ref name=eljohnson>{{Citation |last = Everett L. |first = Johnson |date = March 1980 |title = A Digital Quarter Square Multiplier |periodical = IEEE Transactions on Computers |publication-place = Washington, DC, USA |publisher = IEEE Computer Society |volume = C-29 |issue = 3 |pages = 258–261 |url = http://www2.computer.org/portal/web/csdl/doi/10.1109/TC.1980.1675558 |issn = 0018-9340 |doi =10.1109/TC.1980.1675558 |accessdate = 2009-03-26}}</ref> To form the product of two 8-bit integers, for example, the digital device forms the sum and difference, looks both quantities up in a table of squares, takes the difference of the results, and divides by four by shifting two bits to the right. For 8-bit integers the table of quarter squares will have 2<sup>9</sup>-1=511 entries (one entry for the full range 0..510 of possible sums, the differences using only the first 256 entries in range 0..255) or 2<sup>9</sup>-1=511 entries (using for negative differences the technique of 2-complements and 9-bit masking, which avoids testing the sign of differences), each entry being 16-bit wide (the entry values are from (0²/4)=0 to (510²/4)=65025).▼
▲}}</ref> To form the product of two 8-bit integers, for example, the digital device forms the sum and difference, looks both quantities up in a table of squares, takes the difference of the results, and divides by four by shifting two bits to the right. For 8-bit integers the table of quarter squares will have 2<sup>9</sup>-1=511 entries (one entry for the full range 0..510 of possible sums, the differences using only the first 256 entries in range 0..255) or 2<sup>9</sup>-1=511 entries (using for negative differences the technique of 2-complements and 9-bit masking, which avoids testing the sign of differences), each entry being 16-bit wide (the entry values are from (0²/4)=0 to (510²/4)=65025).
The Quarter square multiplier technique has also benefitted 8-bit systems that do not have any support for a hardware multiplier. Steven Judd implemented this for the [[MOS Technology 6502|6502]].<ref name=sjudd>{{Citation |last = Judd |first = Steven |date = Jan 1995 |periodical = C=Hacking |issue = 9 |url = http://www.ffd2.com/fridge/chacking/c=hacking9.txt}}</ref>
==Algorithm for multiplying numbers close to a round number==
Line 430 ⟶ 375:
==Polynomial multiplication==
All the above multiplication algorithms can also be expanded to multiply [[polynomial]]s. For instance the Strassen algorithm may be used for polynomial multiplication<ref>{{cite web|url=http://everything2.com/title/Strassen+algorithm+for+polynomial+multiplication|title=Strassen algorithm for polynomial multiplication |publisher=Everything2}}</ref>
Alternatively the [[Kronecker substitution]] technique may be used to convert the problem of multiplying polynomials into a single binary multiplication.<ref>{{citation |first1 = Joachim |last1 = von zur Gathen | author1-link = Joachim von zur Gathen |first2 = Jürgen | last2 = Gerhard |title = Modern Computer Algebra |publisher = Cambridge University Press |year = 1999 |isbn = 978-0-521-64176-0 |pages = 243–244 |url = https://books.google.com/books?id=AE5PN5QGgvUC&pg=PA245 }}.</ref>
Long multiplication methods can be generalised to allow the multiplication of algebraic formulae:
| |||