Karatsuba algorithm splitting number in 3 strings

324 Views Asked by At

Im trying to code the Karatsuba algorithm with some changes. Instead of splitting each number into 2 strings, I want to split it into 3.

For example:

Common Karatsuba -> first number would goes into A and B. Second number would goes into C and D.

       A B
     x C D
resulting...
    ac  ad+bc   bd

In order to implement it through recursive calls, majority of the codes do something like:

e = karatsuba(a,c)
f = karatsuba(b,d)
g = karatsuba(a+b,c+d)
h = g-f-e //that's to get the 'ad+bc', since (a+b)(c+d) = ac+ad+bc+bd, then removing 'f' and 'e', we get just ad+bc

and finally...

return e*10ˆn + h*10^(n/2) + f;

Karatsuba I want to implement -> first number would goes into A, B and C. Second number would goes into D, E and F.

    A B C
  x D E F
resulting...
 ad  ae+bd  af+be+cd  cf+ce  cf

However I have no idea how I can implement such thing through recursive calls, cause it seems much more complicated than the common way.

Please help.

0

There are 0 best solutions below