4
$\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
  • 4
    $\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 '19 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 '19 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$
1
  • $\begingroup$ I ran into an issue with this answer, but the comment under OPs question solved my problem. $\endgroup$ – Tommy Jul 3 '19 at 21:31
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 729 × 784. And 7290 × 7840. Sorry for the inconvenience $\endgroup$ – Swayam Swastik Behera Mar 9 at 15:40
  • 1
    $\begingroup$ Or change it to 0729 x 0784 and you don't need to change anything in the result. $\endgroup$ – gnasher729 Mar 9 at 18:10
  • $\begingroup$ (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…) $\endgroup$ – greybeard Mar 9 at 21:58

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.