Creating Karatsuba's algorithm with Matlab

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!

[Siti Hariani Zahrullaili]

This is my first time asking a question here since I only just recently installed and learnt Matlab on my own. So, forgive me as the question seems highly confusing to look at...

[Walter Roberson]

Please check the definition of m. Is it m = [n/2] like you wrote or is it something written closer to |_ n/2 _| which has the inward strokes on the bottom but not on the top? If I am correct about what it should look like then m = floor(n/2) which would be necessary to avoid square roots if n is not even.

[Siti Hariani Zahrullaili]

I've checked, the inward strokes are on the top but not on the bottom. Does this also imply m = floor(n/2)? What about the rest of the algorithm?

[Walter Roberson]

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.

Answer 1

[Brian Neiswander]

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:

https://eprint.iacr.org/2006/224.pdf

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.

Answer 2

[Libor Seda]

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