Karatsuba Algorithm

The Karatsuba algorithm

Is a fast multiplication algorithm. It is a divide-and-conquer algorithm that reduces the multiplication of two $n$-digit numbers to three multiplications of $n/2$-digit numbers.

It is a fast multiplication algorithm. A Divide and Conquer algorithm that reduces the multiplication of two $n-$digit numbers to three multiplications of $n/2-$digit numbers and by repeating this reduction, to at most $n^{\log 23}\approx n^{1.58}$ single-digit multiplications.

It is asymptotically faster than the traditional algorithm, which performs $n^2$ single-digit products.

Related

• Strassen Algorithm