Karatsuba Multiplication with n/3 division of large number I was studying Karatsuba multiplication where the complexity is reduced as compared to classical algorithm by splitting each number into two parts.

Now I'm trying to understand how the multiplication will take place when a number is divided into three parts instead of two.

I tried to solve the math but only came up with more number of multiplications than in Karatsuba.

Can someone help me out with this problem?
The algorithm you are looking for seems to be the Toom-3 algorithm.