Multiplication algorithm: Difference between revisions

Revision as of 21:36, 21 July 2023

Revision as of 09:01, 22 July 2023

Line 293:

===Karatsuba multiplication===

{{Main|Karatsuba algorithm}}

For systems that need to multiply numbers in the range of several thousand digits, such as [[computer algebra system]]s and [[bignum]] libraries, long multiplication is too slow. These systems may employ '''Karatsuba multiplication''', which was discovered in 1960 (published in 1962). The heart of [[Anatoly Karatsuba|Karatsuba]]'s method lies in the observation that two-digit multiplication can be done with only three rather than the four multiplications classically required. This is an example of what is now called a ''[[divide-and-conquer algorithm]]''. Suppose we want to multiply two 2-digit base-''m'' numbers: ''x''₁'' m + x''₂ and ''y''₁'' m + y''₂:

#Karatsuba computemultiplication is an O(''xn''^log₁₂3) ·≈ O(''yn''<subsup>1.585</subsup>,) callmultiplication thealgorithm. result ''F''

# compute ''x''₂ · ''y''₂, call the result ''G''

# compute (''x''₁ + ''x''₂) · (''y''₁ + ''y''₂), call the result ''H''

# compute ''H'' − ''F'' − ''G'', call the result ''K''; this number is equal to ''x''₁ · ''y''₂ + ''x''₂ · ''y''₁

# compute ''F'' · ''m''² + ''K'' · ''m'' + ''G''.

Let <math>x</math> and <math>y</math> be represented as <math>n</math>-digit strings in some base <math>B</math>. For any positive integer <math>m</math> less than <math>n</math>, one can write the two given numbers as

To compute these three products of base ''m'' numbers, we can employ the same trick again, effectively using [[recursion]]. Once the numbers are computed, we need to add them together (steps 4 and 5), which takes about ''n'' operations.

:<math>x = x_1 B^m + x_0,</math>

Karatsuba multiplication has a time complexity of [[Big O notation|O]](''n''^log₂3) ≈ O(''n''^1.585), making this method significantly faster than long multiplication. Because of the overhead of recursion, Karatsuba's multiplication is slower than long multiplication for small values of ''n''; typical implementations therefore switch to long multiplication for small values of ''n''.

:<math>y = y_1 B^m + y_0,</math>

where <math>x_0</math> and <math>y_0</math> are less than <math>B^m</math>. The product is then

<math>

\begin{align}

xy &= (x_1 B^m + x_0)(y_1 B^m + y_0) \\

&= x_1 y_1 B^{2m} + (x_1 y_0 + x_0 y_1) B^m + x_0 y_0 \\

&= z_2 B^{2m} + z_1 B^m + z_0, \\

\end{align}

</math>

where

:<math>z_2 = x_1 y_1,</math>

:<math>z_1 = x_1 y_0 + x_0 y_1,</math>

:<math>z_0 = x_0 y_0.</math>

These formulae require four multiplications and were known to [[Charles Babbage]].<ref>Charles Babbage, Chapter VIII – Of the Analytical Engine, Larger Numbers Treated, [https://archive.org/details/bub_gb_Fa1JAAAAMAAJ/page/n142 <!-- pg=125 --> Passages from the Life of a Philosopher], Longman Green, London, 1864; page 125.</ref> Karatsuba observed that <math>xy</math> can be computed in only three multiplications, at the cost of a few extra additions. With <math>z_0</math> and <math>z_2</math> as before one can observe that

:<math>

\begin{align}

z_1 &= x_1 y_0 + x_0 y_1 \\

&= x_1 y_0 + x_0 y_1 + x_1 y_1 - x_1 y_1 + x_0 y_0 - x_0 y_0 \\

&= x_1 y_0 + x_0 y_0 + x_0 y_1 + x_1 y_1 - x_1 y_1 - x_0 y_0 \\

&= (x_1 + x_0) y_0 + (x_0 + x_1) y_1 - x_1 y_1 - x_0 y_0 \\

&= (x_1 + x_0) (y_0 + y_1) - x_1 y_1 - x_0 y_0 \\

&= (x_1 + x_0) (y_1 + y_0) - z_2 - z_0. \\

\end{align}

</math>

Karatsuba multiplication has a time complexity of [[Big O notation|O]](''n''^log₂3) ≈ O(''n''^1.585), making this method significantly faster than long multiplication. Because of the overhead of recursion, Karatsuba's multiplication is slower than long multiplication for small values of ''n''; typical implementations therefore switch to long multiplication for small values of ''n''.

==== History ====

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.