# 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$, Jun 7, 2017 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. Jul 3, 2019 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. Jul 3, 2019 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$).

• I ran into an issue with this answer, but the comment under OPs question solved my problem. Jul 3, 2019 at 21:31

You can add a zero to X and Y Eg : 729784 change it into 72907840.then apply the algorithm . Then at last remove the two zeros. You are now left with X*Y

• 729 × 784. And 7290 × 7840. Sorry for the inconvenience Mar 9, 2021 at 15:40
• Or change it to 0729 x 0784 and you don't need to change anything in the result. Mar 9, 2021 at 18:10
• (Sorry for the inconvenience - don't apologise, edit your post: either "escape the stars" - prepending a \ may do, or turn into a $L^AT_EX$/ MathJax formula (enclose in \$) or…) Mar 9, 2021 at 21:58