Multiply two integers. Isn’t it simple?

Photo by Gayatri Malhotra on Unsplash
Schematic representation of the grad-school algorithm and its number of operations.
Schematic representation of the operations involved in the Karatsuba algorithm.
Schematic representation of the operations involved in the Toom-Cook-3 algorithm. The matrices A and B are the ones defined in the text.
Schematic representation of the operations involved in the Schönhage-Strassen algorithm.

References

[1] — A. Karatsuba and Yu. Ofman (1962). “Multiplication of Many-Digital Numbers by Automatic Computers”. Proceedings of the USSR Academy of Sciences. 145: 293–294. Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alessandro Attanasi

Alessandro Attanasi

Engineering Manager at PTV Group for Real-Time mobility. PhD in physics with passion in Computer Science, Statistics, ML/AI. Motto: “Never stop learning”