Creating Karatsuba's algorithm with Matlab
6 views (last 30 days)
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))
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
m = n/2;
f = f0 + (f1*x^m);
g = g0 + (g1*x^m);
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!
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=