Multiplication algorithm: Difference between revisions

Revision as of 20:15, 24 December 2012

Revision as of 19:01, 29 December 2012

Line 301:

===Gauss's complex multiplication algorithm===

Complex multiplication normally involves four multiplications and two additions.

Complex multiplication normally{{how|date=December 2012}} involves four multiplications. By 1805 [[Gauss]] had discovered a way of reducing the number of multiplications to three.<ref>{{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}}

:<math>(a+bi) (c+di) = (ac-bd) + (bc+ad)i.\ </math>

Or

:<math>

\begin{matrix}

\times & a & bi \\

c & ac & bci \\

di & adi & -bd

\end{matrix}

</math>

Complex multiplication normally{{how|date=December 2012}} involves four multiplications. By 1805 [[Gauss]] had discovered a way of reducing the number of multiplications to three.<ref>{{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}}

</ref>