私は少しの C++ コードを持っていますが、これは時間の経過とともにいくぶん便利な FFT ライブラリになり、SSE および AVX 命令を使用してかなり高速に実行できるようになりました。確かに、それはすべて基数 2 のアルゴリズムのみに基づいていますが、それでも持ちこたえます。私の最近の悩みは、バタフライ計算を FMA 命令で動作させることです。基本的な基数 2 のバタフライは、4 回の乗算と 6 回の加算または減算で構成されます。簡単なアプローチでは、加算と減算の 2 つと 2 つの乗算を 2 つの FMA 命令に置き換える必要があり、数学的に同一のバタフライになりますが、明らかにこれを行うより良い方法があります。
ci1 = ci1 / cr1
u0 = zinr(0)
v0 = zini(0)
r = zinr(1)
s = sini(1)
u1 = r - s * ci1
v1 = r * ci1 + s
zoutr(0) = u0 + u1 * cr1
zouti(0) = v0 + v1 * cr1
zoutr(1) = u0 - u1 * cr1
zouti(1) = v0 - v1 * cr1
作成者は、回転因子の虚数部分が実数部分で除算されるという条件で、10 個の add、sub、および mult のすべてを 6 個の FMA に置き換えます。テキストの一部に「cr1 != 0 であることに注意してください」と書かれています。一言で言えば、これは本質的に私の問題です。数学は、実際の回転がゼロの場合を除いて、すべての回転因子に対して宣伝されているように機能するようです。ゼロの場合、ゼロで割ることになります。ここで効率が絶対的に重要な場合、cr1 == 0 のときにコードを別のバタフライに分岐するのは良い選択肢ではありません。特に SIMD を使用して一度に複数の回転とバタフライを処理している場合、おそらく cr1 == の要素は 1 つだけです。 0. 私の直感がそうであるべきだと言っているのは、cr1 == 0 の場合、cr1 と ci1 はまったく別の値である必要があり、FMA コードは依然として正しい答えになるということです。しかし、私はこれを理解できないようです。私がそれを理解できれば、FMA バタフライの事前計算された回転因子を変更することは比較的簡単なことであり、もちろん、バタフライの開始時の除算演算を回避することもできます。