Karatsuba algorithm: Difference between revisions

Revision as of 23:57, 30 January 2023

Revision as of 00:15, 31 January 2023

Line 61:

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>

:<math>z_1 = (x_1 + x_0)(y_1 + y_0) - z_2 - z_0.</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 \\

:<math>z_1 &= (x_1 + x_0) (y_1 + y_0) - z_2 - z_0.</math> \\

\end{align}

</math>

===Example===