2

我目前正在学习 FFT，但无法解决以下问题：

编写一个“分而治之”算法，将两个多项式（最大 N 次）的复杂度相乘：

n^log3 的 Theta（base 2 log ofc）

该算法应该将两个给定的多项式系数分成两组：

Group1) 具有偶数索引的系数。Group2) 具有奇数索引的系数。

嗯，我什至不知道如何开始考虑解决方案。指南似乎类似于 FFT 算法，但我仍然看不到解决方案。很想得到一些帮助！甚至只是一种思考方式..

请注意，不应提供任何代码..只有解释，也许还有关于如何完成它的伪代码。

谢谢 ！

4

1 回答 1

1

Here are a few hints, then the solution.

1 - First of all, you should make sure that you can perform the multiplication in less than n^2 coefficient multiplications, on a simple example :

(aX + b)*(cX + d)

One of your multiplications should be (a+b)*(c+d)

2 - Haven't found how to do it ? Here are the operations for each power :

X^2 : ac

X : (a+b)*(c+d) - ac - bd

1 : bd

You just have to perform 3 multiplications instead of 4. Additions do not cost that much compared to multiplications.

3 - You are asked to find a solution in Theta(n^lg(3)). Here is a quick reminder of the 'Théorème Général' :

Let T(n) the cost of your algorithme for the polynoms with degree n.

With a 'divide to conquer strategy' which leads to :

T(n) = aT(n/b)+f(n)

If f(n)~O(n^lg_b(a)) then T(n) = Theta(n^lg_b(a))

You are looking for T(n) = Theta(n^lg_2(3)). This could mean that :

T(n)=3.T(n/2) + epsilon

If you split your polynoms in even and odd polynoms, they have half of the initial coefficients amount : n/2.

The formula shows you that you will perform three multiplications between the odd and even polynoms...

4 - Consider to represent your polynom P(x) with degree n this way :

P(X) = X.A(X) + B(X)

A(X) and B(X) contain n/2 coefficients.

5 - Solution

P(X) = X.A(X) + B(X)

P'(X) = X.A'(X) + B'(X)

The coefficients of P*P'(X) is the sum of the coefficients of :

X^2.A.A'

X.(A.B'+A'.B) = X.[(A+B)(A'+B') - A.A' - B.B']

B.B'

So you have to call your multiplication algorithm on :

A and A'

A+B and A'+B'

B and B'

Then you can recombine coefficients with shifts and additions.

Cheers

于 2013-07-09T09:33:44.073 回答