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.
Your $(7)(2)$ should be $(A+B)\cdot(C+D)=(8)(3)$.