Binary Karatsuba Multiplication

I recently looked at a amazing peice of simple mathmatics called Karatsuba’s Multiplication. The orignal article went in depth proving that it does infact decrease the ammount of expencive opetation when multiplying numbers together.

This was an intristing descovery and when I though about it further I beleve that I can make it even faster than that in terms of a computer.

I will take his basic condition and improve on it

$$x = x_1 * B^m + x_2$$ $$y = y_1 * B^m + y_2$$

Assuming that the Base (B) is 2. We convert it in to

$$x = x_1 * 2^m + x_2 \\ y = y_1 * 2^m + y_2 \\ $$

In doing so we convert simplify the power. If a number is raised to a power of 2 than it is just doing a binary shift.

Now you get:

$$x = x_1 << m + x_2 \\ y = y_1 << m + y_2 \\ $$ $$61 * 35 = 100011_2 * 111101_2 \\ $$

Now lets break down X in to its parts.

$$\begin{align} x &= 100011_2 \\ &= 100_2 * 2^3 + 011_2 \end{align}$$ $$x_1 = 100_2 \\ x_2 = 011_2 \\ \\ $$

And the same for Y.

$$\begin{align} y &= 111101_2 \\ &= 111_2 * 2^3 + 101_2 \end{align}$$ $$y_1 = 111_2 \\ y_2 = 101_2 \\ $$

Lets compute A

$$\begin{align} a &= x_1 * y_1 \\ &= 100_2 * 111_2 \\ &= 11100_2 \end{align}$$

And C.

$$\begin{align} c &= x_2 * y_2 \\ &= 011_2 * 101_2 \\ &= 1111_2 \end{align}$$

And finaly B

$$\begin{align} b &= (x_1 + x_2)*(y_1 + y_2) - a - c \\ &= 111_2 * 1100_2 - 11100_2 - 1111_2 \\ &= 101001_2 \end{align}$$

And plugging it back in

$$\begin{align} x*y &= a * B^2m + b * B^m + c \\ &= 11100_2 << 2m + 101001_2 << m + 1111_2 \\ &= 100001010111_2 = 2135 \end{align}$$