# 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
• @miracle173 your comment solved the problem for me but @roukah answer did not. The difference is, in your comment, we derive that m=2, which is used in the final calculated (10^4 and 10^2) because each string becomes of length 4, and we can use len/2. However, using @roukah answer, a,b,c,d is preserved but m=1, which leads to my final calculation being wrong. So this comment is the answer I would accept. – Tommy Jul 3 at 21:18
• to elaborate, without padding, a,b,c,d was the same but m was 1, which affected the final calculation, but with your padding suggestion, a,b,c,d were the same but m was 2. If this was an answer I would upvote. – Tommy Jul 3 at 21:32

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$).