WritingMedium
Karatsuba Multiplication Algorithm
By Sachin Gupta6 min read
How the Karatsuba algorithm multiplies large numbers faster than long multiplication, trading one multiplication for a few additions to bring the cost from quadratic down to about n^1.585.
Notes
A self-hosted write-up of this entry is on the way. In the meantime, the source link below has the canonical version, and the About page has context on the work I do day-to-day.
