Multiplication algorithm: Difference between revisions

Revision as of 11:27, 22 July 2023

Revision as of 11:30, 22 July 2023

Line 341:

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^{8m4m} + a_1 x_1 y_1 z_0 B^{6m3m} + a_1 x_1 y_0 z_1 B^{63 m} + a_1 x_0 y_1 z_1 B^{63 m} </math> <br>

<math>+ a_0 x_1 y_1 z_1 B^{63 m} + a_1 x_1 y_0 z_0 B^{42 m} + a_1 x_0 y_1 z_0 B^{42 m} + a_0 x_1 y_1 z_0 B^{42 m}</math> <br>

<math> + a_1 x_0 y_0 z_1 B^{42 m} + a_0 x_1 y_0 z_1 B^{42 m} + a_0 x_0 y_1 z_1 B^{42 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

Line 354:

<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^{2imim}

</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>

Line 368:

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