Editing Multiplication algorithm (section)

===Karatsuba multiplication===
{{Main|Karatsuba algorithm}}

Karatsuba multiplication is an O(''n''<sup>log<sub>2</sub>3</sup>) ≈ O(''n''<sup>1.585</sup>) divide and conquer algorithm, that uses recursion to merge together sub calculations. 

By rewriting the formula, one makes it possible to do sub calculations / recursion. By doing recursion, one can solve this in a fast manner.

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

:<math>x = x_1 B^m + x_0,</math>
:<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>



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''.

==== General case with multiplication of N numbers ====

By exploring patterns after expansion, one see following:

<math display="block">\begin{alignat}{5} (x_1 B^{ m} + x_0) (y_1 B^{m} + y_0) (z_1 B^{ m} + z_0) (a_1 B^{ m} + a_0) &=
a_1 x_1 y_1 z_1 B^{4 m} &+ a_1 x_1 y_1 z_0 B^{3m} &+ a_1 x_1 y_0 z_1 B^{3 m} &+ a_1 x_0 y_1 z_1 B^{3 m} \\
&+ a_0 x_1 y_1 z_1 B^{3 m} &+ a_1 x_1 y_0 z_0 B^{2 m} &+ a_1 x_0 y_1 z_0 B^{2 m} &+ a_0 x_1 y_1 z_0 B^{2 m}\\ 
&+ a_1 x_0 y_0 z_1 B^{2 m} &+ a_0 x_1 y_0 z_1 B^{2 m} &+ a_0 x_0 y_1 z_1 B^{2 m} &+ a_1 x_0 y_0 z_0 B^{m\phantom{1}}\\
&+ a_0 x_1 y_0 z_0 B^{m\phantom{1}} &+ a_0 x_0 y_1 z_0 B^{m\phantom{1}} &+ a_0 x_0 y_0 z_1 B^{m\phantom{1}} &+ a_0 x_0 y_0 z_0 \phantom{B^{1 m}}
\end{alignat}</math>

Each summand is associated to a unique binary number from 0 to
<math> 2^{N+1}-1 </math>, for example <math> a_1 x_1 y_1 z_1 \longleftrightarrow 1111,\ a_1 x_0 y_1 z_0 \longleftrightarrow 1010 </math> etc. Furthermore; B is powered to number of 1, in this binary string, multiplied with m.

If we express this in fewer terms, we get:

<math display="block">\prod_{j=1}^N (x_{j,1} B^{ m} + x_{j,0})  = \sum_{i=1}^{2^{N+1}-1}\prod_{j=1}^N x_{j,c(i,j)}B^{m\sum_{j=1}^N c(i,j)} = \sum_{j=0}^{N}z_jB^{jm} 
</math>, where <math> c(i,j) </math> means digit in number i at position j. Notice that <math> c(i,j) \in \{0,1\} </math>

<math display="block">
\begin{align}
z_{0} &= \prod_{j=1}^N x_{j,0}
\\
z_{N} &= \prod_{j=1}^N x_{j,1}
\\
z_{N-1} &= \prod_{j=1}^N (x_{j,0} + x_{j,1}) -  \sum_{i \ne N-1}^{N} z_i
\end{align}
</math>

==== 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.