A divide-and-conquer algorithm for multiplying two large numbers faster than the grade-school method, by splitting each number into halves and reducing four sub-multiplications to three, one of the earliest algorithms shown to beat the naive quadratic bound.
Facts
Core PrincipleMultiplies two n-digit numbers using three multiplications of n/2-digit numbers instead of four, a divide-and-conquer approach that is asymptotically faster than long multiplication. 1 Connections
Sources
1. Wikipedia: Karatsuba Algorithm
Wikimedia FoundationLead section, second sentence
It was discovered by Anatoly Karatsuba in 1960 and published in 1962.
Lead section, third sentence
It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.