Multiplication algorithm: Difference between revisions

Revision as of 07:31, 23 December 2018

Revision as of 17:44, 13 March 2019

Line 256:

If, for example, you wanted to multiply 9 by 3, you observe that the sum and difference are 12 and 6 respectively. Looking both those values up on the table yields 36 and 9, the difference of which is 27, which is the product of 9 and 3.

Antoine Voisin published a table of quarter squares from 1 to 1000 in 1817 as an aid in multiplication. A larger table of quarter squares from 1 to 100000 was published by Samuel Laundy in 1856,<ref>{{Citation |title=Reviews |journal=The Civil Engineer and Architect's journalJournal |year=1857 |pages=54–55 |url=https://books.google.com/books?id=gcNAAAAAcAAJ&pg=PA54#v=onepage&f=false |postscript=.}}</ref> and a table from 1 to 200000 by Joseph Blater in 1888.<ref>{{Citation|title=Multiplying with quarter squares |first=Neville |last=Holmes| journal=The Mathematical Gazette |volume=87 |issue=509 |year=2003 |pages=296–299 |jstor=3621048|postscript=.|doi=10.1017/S0025557200172778 }}</ref>

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___location = 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⁹-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⁹-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>

Line 284:

</math>

But there is a way of reducing the number of multiplications to three.<ref name="taocp-vol2-sec464-ex41">{{Citation | last1=Knuth | first1=Donald E. | author1-link=Donald Knuth | title=[[The Art of Computer Programming]] volume 2: Seminumerical algorithms | publisher=[[Addison-Wesley]] | year=1988 | pages=519, 706| title-link=The Art of Computer Programming }}

</ref>

Line 412:

==Further reading==

* {{Cite book |title=[[Hacker's Delight]] |first=Henry S. |last=Warren Jr. |date=2013 |edition=2 |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8|title-link=Hacker's Delight }}

* {{cite web |title=Advanced Arithmetic Techniques |author-first=John J. G. |author-last=Savard |date=2018 |orig-year=2006 |work=quadibloc |url=http://www.quadibloc.com/comp/cp0202.htm |access-date=2018-07-16 |dead-url=no |archive-url=https://web.archive.org/web/20180703001722/http://www.quadibloc.com/comp/cp0202.htm |archive-date=2018-07-03}}