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

Improve this question
$\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
    Commented Jun 7, 2017 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
    Commented Jul 3, 2019 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
    Commented Jul 3, 2019 at 21:32

2 Answers 2

Reset to default
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$).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I ran into an issue with this answer, but the comment under OPs question solved my problem. $\endgroup$
    – Tommy
    Commented Jul 3, 2019 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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 729 × 784. And 7290 × 7840. Sorry for the inconvenience $\endgroup$
    – Swayam Swastik Behera
    Commented Mar 9, 2021 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
    Commented Mar 9, 2021 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
    Commented Mar 9, 2021 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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