4

、 where 、およびx**rの展開での係数を計算する (おそらく numpy または scipy からの) Python 関数はありますか?(1+x+x**2+x**3+...+x**(k-1))**nk>=1n>=00<=r<=n(k-1)

これは、多項式係数 (PC)と呼ばれることもあります (たとえば、こちらを参照)。

そうでない場合、それを計算する効率的な方法を考えてもらえますか? （素朴で貪欲な方法には興味がありません）。

4

1 に答える 1

1

n[1, 1, 1, ..., 1, 1, 1] の畳み込みを効果的に実行しています。
そのため、十分にゼロのパディングされた配列でFFTを使用し、その要素を累乗nし、逆FFTを使用してすべての係数を回復することを検討しましたか?

(1+x+x**2+x**3+...+x**(k-1))**n

そして、興味のあるものを読み飛ばすだけですか？

更新：

FFT は循環的であるため、次の項の数以上の配列が必要です。

(1+x+x**2+x**3+...+x**(k-1))**n

または、言い換える(k-1)*n+1と、結果が端で折り返されないようにします (または、少なくとも折り返された場合、影響を受ける要素にゼロを追加するだけです)。多くの場合、その長さは 2 のべき乗である必要があります。これは FFT アルゴリズムで必要とされるためです (必要のない実装では、必要になるまで入力がゼロでパディングされます)。

C ライクな擬似コードでは:

unsigned int m = 1;
while(m<(k-1)*n+1) m *= 2;

complex c[m];
for(unsigned int i=0;i!=k;++i) c[i] = complex(1.0, 0.0);
for(unsigned int i=k;i!=m;++i) c[i] = complex(0.0, 0.0);

c = fft(c);
for(unsigned int i=0;i!=m;++i) c[i] = pow(c[i], double(n));
c = inv_fft(c);

最後にr、複素数配列の ' 番目の要素は、cの係数に等しい実部とx**r0 の虚部を持ちます。
これはすべて浮動小数点で行われるため、これらの要素には丸め誤差が蓄積されることに注意してください。これを最も近い整数に丸めることで部分的に修正できますが、十分に大きい場合k、nこれらの誤差は 0.5 を超えるため、わずかな相対誤差によって結果がずれることがあることに注意してください。

Web で簡単に検索すると、numpy には FFT とその逆の実装があり、numpy.fft.rfftそれぞれnumpy.fft.irfft、入力データが実数の場合に使用できることがわかります。

于 2014-05-28T19:02:56.677 に答える