私は現在FFTを勉強していますが、次の質問を解決するのに苦労しています:
2 つの多項式 (最大 N 次) を複雑に乗算する "分割統治" アルゴリズムを記述します。
n^log3 のシータ (c の底 2 の対数)
アルゴリズムは、与えられた 2 つの多項式係数を 2 つのグループに分割する必要があります。
Group1) インデックスが偶数の係数。Group2) インデックスが奇数の係数。
ええと、解決策について考え始める方法さえわかりません..ガイドラインはFFTアルゴリズムに似ているようですが、まだ解決策がわかりません。何らかの支援を受けたいです！それについて考える方法だけでも..
コードは提供されないことに注意してください。説明と、それを実行する方法に関する疑似コードのみです。
ありがとう ！
ここにいくつかのヒントがあり、それから解決策があります。
1 - まず、単純な例で、n^2 未満の係数乗算で乗算を実行できることを確認する必要があります。
(aX + b)*(cX + d)
乗算の 1 つは (a+b)*(c+d) である必要があります。
2 - 方法がわかりませんか? 各勢力の操作は次のとおりです。
X^2 : 交流
X : (a+b)*(c+d) - ac - bd
1 : BD
4 回ではなく 3 回の乗算を実行するだけで済みます。加算は、乗算に比べてそれほどコストがかかりません。
3 - Theta(n^lg(3)) で解を求めるよう求められます。ここで、'Théorème Général' を簡単に思い出してください。
次数 n の多項式のアルゴリズムのコストを T(n) とします。
「分割して征服する戦略」により、次のことが実現します。
T(n) = aT(n/b)+f(n)
f(n)~O(n^lg_b(a)) の場合、T(n) = Theta(n^lg_b(a))
T(n) = Theta(n^lg_2(3)) を探しています。これは次のことを意味します。
T(n)=3.T(n/2) + イプシロン
多項式を偶数多項式と奇数多項式に分割すると、初期係数量の半分 (n/2) になります。
この式は、奇数多項式と偶数多項式の間で 3 つの乗算を実行することを示しています...
4 - 次数 n の多項式 P(x) を次のように表すことを検討してください。
P(X) = XA(X) + B(X)
A(X) と B(X) には n/2 の係数が含まれます。
5 - ソリューション
P(X) = XA(X) + B(X)
P'(X) = XA'(X) + B'(X)
P*P'(X) の係数は、次の係数の合計です。
X^2.AA'
X.(AB'+A'.B) = X.[(A+B)(A'+B') - AA' - BB']
BB'
したがって、乗算アルゴリズムを次のように呼び出す必要があります。
AとA'
A+B および A'+B'
BとB'
次に、係数をシフトと加算で再結合できます。
乾杯