Content deleted Content added
Line 337:
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> (x_1 B^{2 m} + x_0) (y_1 B^{2 m} + y_0) (z_1 B^{2 m} + z_0) (a_1 B^{2 m} + a_0) = </math> <br>
<math> a_1 x_1 y_1 z_1 B^{8m} + a_1 x_1 y_1 z_0 B^{6m} + a_1 x_1 y_0 z_1 B^{6 m} + a_1 x_0 y_1 z_1 B^{6 m} </math> <br>
<math>+ a_0 x_1 y_1 z_1 B^{6 m} + a_1 x_1 y_0 z_0 B^{4 m} + a_1 x_0 y_1 z_0 B^{4 m} + a_0 x_1 y_1 z_0 B^{4 m}</math> <br>
<math> + a_1 x_0 y_0 z_1 B^{4 m} + a_0 x_1 y_0 z_1 B^{4 m} + a_0 x_0 y_1 z_1 B^{4 m} + a_1 x_0 y_0 z_0 B^{2 m}</math> <br>
<math>+ a_0 x_1 y_0 z_0 B^{2 m} + a_0 x_0 y_1 z_0 B^{2 m} + a_0 x_0 y_0 z_1 B^{2 m} + a_0 x_0 y_0 z_0 </math>
Every possible binary number from 1 to
<math> 2^{N+1}-1 </math> is in the polynomial.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> \prod_{j=1}^N x_j = \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_{i=0}^{N}z_iB^{2im}
</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>
z_{0} = \prod_{j=1}^N x_{j,0}
</math><br>
<math>
z_{N} = \prod_{j=1}^N x_{j,1}
</math><br>
<math>
z_{N-1} = \prod_{j=1}^N (x_{j,0} + x_{j,1}) - \sum_{i \ne N-1}^{N} z_i
</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.
| |||