3
$\begingroup$

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}$?

$\endgroup$
  • 3
    $\begingroup$ 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$, $\endgroup$ – miracle173 Jun 7 '17 at 16:01
  • $\begingroup$ @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. $\endgroup$ – Tommy Jul 3 at 21:18
  • $\begingroup$ 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. $\endgroup$ – Tommy Jul 3 at 21:32
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I ran into an issue with this answer, but the comment under OPs question solved my problem. $\endgroup$ – Tommy Jul 3 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.