Creating Karatsuba's algorithm with Matlab

12 次查看（过去 30 天）
Siti Hariani Zahrullaili
回答： Libor Seda 2017-2-7
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!
  4 个评论
显示 2更早的评论
Siti Hariani Zahrullaili
Siti Hariani Zahrullaili 2015-8-16
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
Walter Roberson 2015-8-16
编辑：Walter Roberson 2015-8-16
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Brian Neiswander
Brian Neiswander 2015-8-18
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.
Libor Seda
Libor Seda 2017-2-7
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

类别

在 Help Center 和 File Exchange 中查找有关 Polynomials 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by