# Creating Karatsuba's algorithm with Matlab

9 views (last 30 days)
Siti Hariani Zahrullaili on 16 Aug 2015
Answered: Libor Seda on 7 Feb 2017
I was given a set of instructions on how to create Karatsuba's algorithm, but I can't seem to get it right! Please help; the set of instructions is as below:
Input: Polynomials f(x), g(x) both of degrees less than n. Output: f(x)g(x)
1. If n = 1, f(x) and g(x) are constants. Return f(x)g(x).
2. Otherwise write m = [n/2] and
f(x) = f0(x) + f1(x)x^m
g(x) = g0(x) + g1(x)x^m
where f0, f1, g0, g1 are polynomials of degree less than m.
3. By application of this algorithm, calculate
A(x) = f0(x)g0(x)
B(x) = f1(x)g1(x)
C(x) = (f0(x) + f1(x))(g0(x) + g1(x))
4. Return
f(x)g(x) = A(x) + (C(x) - A(x) - B(x))x^m + B(x)x^2m
Below is what I've done so far:
f = 1:n; g = 1:n;
if n == 1
f*g;
else
m = n/2;
f = f0 + (f1*x^m);
g = g0 + (g1*x^m);
end
A = f0 * g0;
B = f1 * g1;
C = (f0 + f1)*(g0 + g1);
fg = A + (C - A - B)x^m + Bx^2m
I know it is completely wrong. But that is the only way I could think of to interpret the instructions as Matlab code. Please, please, please help me understand what I did wrong! Thank you so much in advance!
Walter Roberson on 16 Aug 2015
Inward strokes on the top but not the bottom means m = ceil(n/2)
As for the rest of the algorithm: you need to input the polynomials (somehow), and they would not be f = 1 : n and g = 1 : n (if only for the reason that those would at best represent a polynomial of degree (n-1) rather than degree (n))
What you have written of the algorithm does not give you any guidance as to how to choose f0 and f1 or g0 and g1.

Brian Neiswander on 18 Aug 2015
From your description of the problem, it sounds to me like you need to create a recursive algorithm to solve this problem. See "Algorithm 1" in the paper linked below for information on how to do this:
Note that this algorithm only applies to polynomials with "n" coefficients where "n" is a power of two. As described in Section 2.3 of the paper, the algorithm splits the polynomials at "n/2" into lower and upper halves. The algorithm is then called on each half. This process of the algorithm calling itself makes it "recursive".
As described in Section 4.1 of the paper, if "n" is not a power of two then the algorithm is slightly modified by splitting the coefficients into a lower "ceil(n/2)" part and an upper "floor(n/2)" part.

Libor Seda on 7 Feb 2017
Hello, I believe what you are looking for is a recursive Karatsuba multiplication algorithm. In my implementation I am using function lx=ceil(log10(max(1,abs(x)+1))), where x is one of the numbers to multiply, to find out about number of digits in current recursion.
Then you need to find your n, which is the max of lengths the 2 numbers you are multiplying.
Knowing that, you can construct your f0,f1,g0 and g1 with floor function and recursively compute the coefficients.
To better understand the algorithm I was using Stanford's OpenClassroom http://openclassroom.stanford.edu/MainFolder/VideoPage.php?course=IntroToAlgorithms&video=CS161L1P9&speed=
HTH
Libor