# Karatsuba multiplication on numbers with odd length

I am learning about Karatsuba-Ofman multiplication. I don't quite understand how to multiply two numbers with odd length.

Let's take two 3-digit numbers $a = 234; b = 857$ with base $B = 10$ and length $n=3$.

The first step is to split split $a$ and $b$ at position $n/2$. However, since $n=3$ where do I split it? Does it even matter?

Later in the algorithm I have to multiply $((a_1 + a_0) \cdot (b_1 + b_0) - (a_1 \cdot b_1) - (a_0 \cdot b_0)) \cdot B^{n/2}$. Would that mean, with $n=3$, I have to multiply by $B^{1.5}$?

• add a leading digit then you have an even number of digits, so $a=0234, b=0857$ Now you can split it in $a_1=02, a_0=34, b_1=08, b_0=57$, which is the same as $a_1=2, a_0=34, b_1=8, b_0=57$, – miracle173 Jun 7 '17 at 16:01

Here, $B = 10$ and $n = 3$. The Karatsuba method works for any $m < n$. With $m = 2$ :

$a = 2 * 10^2 + 34$ and $b = 8 * 10^2 + 57$ ; thus, $a_1 = 2$, $a_0 = 34$, $b_1 = 8$ and $b_0 = 57$.

It follows that $ab = z_2 B^{2m} + z_1 B^m + z_0$ where $z_2 = a_1 b_1 = 16$, $z_1 = a_1 b_0 + a_0 b_1 = 386$ and $z_0 = a_0 b_0 = 1938$.

Thus, $ab = 16 \cdot 10^{2*2} + 386 \cdot 10^2 + 1938 = 200538$.

I'm not sure about the step you mentioned, as it doesn't seem to give the correct result with the current decomposition ($m = 2$).