-1

So I've only been introduced to Karatsuba's method for integer multiplication. I started working through some examples, and everything was fine until I hit the following multiplication problem:

Key/Expressions:

$n = $ max digits from the two integer inputs (+1 in the case of odd numbers - adds leading zero)

$m = n/2$

$x.y = 10^n(a.c) + 10^m(a.d+b.c) + b.d$

$a.d+b.c = (a+b)(c+d) - a.c - b.d$

Input arguments:

$x = 107$

$y = 102$

$n = 4$

$m = 2$

$a = 01$

$b = 07$

$c = 01$

$d = 02$

Solving $a.c$ and $b.d$ for above $x.y$ expression:

$a.c = 1$

$b.d = 14$

Solving $ad+bc$ for $x.y$ expression:

$a.d+b.c = (a+b)(c+d) - a.c - b.d$

$a.d+b.c = (7)(2) – 1 – 14$

$a.d+b.c = -1$ (solution should be 9 here!)

This is where my problem occurs. As stated in the wiki article TonyK linked:

$z_{1}=x_{1}y_{0}+x_{0}y_{1}$

$z_{1}=(x_{1}+x_{0})(y_{1}+y_{0})-x_{1}y_{1}-x_{0}y_{0}$

But this is producing the wrong output for me. Would be great to know where I'm going wrong. Like I said, I've successfully solved other multiplication problems using this method, but this one is giving problems.

sookie
  • 103
  • 2
  • It's difficult to know where you went wrong, because this doesn't look like Karatsuba at all. I suggest you look at the example in the relevant Wikipedia article, which has $A=12, B=345, C=6, D=789$. – TonyK Oct 07 '16 at 11:06
  • It's just a step-by-step for a 3-digit karatsuba multiplication, given 107 and 102 as the two integer inputs. I left out the x.y expression and m (which is just n/2) and just solved for A.C, B.D and AD+BC. It was at AD+BC where I ran into the issue, so I stopped there and didn't finish the multiplication. – sookie Oct 07 '16 at 11:19
  • @TonyK I'm not sure why the question is receiving downvotes, but I'll update it with more info. I've successfully used Karatsuba to solve a number of integer multiplication problems, but this is the only one that seems to not work. Maybe if someone could give their own solution it would be helpful – sookie Oct 07 '16 at 12:54

1 Answers1

0

Your $(7)(2)$ should be $(A+B)\cdot(C+D)=(8)(3)$.

TonyK
  • 64,559