Karatsuba Multiplication
Anatoly Karatsuba, 1960
O(n^1.585)Karatsuba (1960) broke the O(n²) schoolbook barrier by observing that z₁ = (a₁+a₀)(b₁+b₀)−z₂−z₀ reuses z₂ and z₀, saving one multiplication per recursion level.
Anatoly Karatsuba, 1960
O(n^1.585)Karatsuba (1960) broke the O(n²) schoolbook barrier by observing that z₁ = (a₁+a₀)(b₁+b₀)−z₂−z₀ reuses z₂ and z₀, saving one multiplication per recursion level.