Multiplication algorithm: Difference between revisions

Revision as of 21:35, 8 January 2022

Revision as of 21:36, 8 January 2022

Line 323:

Karatsuba's algorithm was the first known algorithm for multiplication that is asymptotically faster than long multiplication,<ref>D. Knuth, ''The Art of Computer Programming'', vol. 2, sec. 4.3.3 (1998)</ref> and can thus be viewed as the starting point for the theory of fast multiplications.

In 1963, [[Peter UngarUnger]] suggested setting ''m'' to ''i'' to obtain a similar reduction in the complex multiplication algorithm.<ref name="taocp-vol2-sec464-ex41"/> To multiply (''a''&nbsp;+&nbsp;''b i'') · (''c''&nbsp;+&nbsp;''d i''), follow these steps:

# compute ''b'' · ''d'', call the result ''F''

# compute ''a'' · ''c'', call the result ''G''