algorithm - 3 つの乗算のみを使用した複素数の積

Question

複素数の乗算は次のように行います。

(a + i * b) * (c + i * d) = (a * c - b * d) + i * (a * d + b * c)

結果の実数部と虚数部は次のとおりです。

real part = (a * c - b * d)
imag part = (a * d + b * c)

これには、4 つの実数乗算が含まれます。たった 3 つの実数の乗算でどのようにそれを行うことができるでしょうか?

Answer 1

Split-radix FFTなどの一部のアルゴリズムは、正確に 3 つの実数乗算と 3 つの実数加算の複雑さを必要とする複雑な乗算に対して、より高い期待を設定します。

(a+ib)(c+id)=ac−bd+i(ad+bc)    

x=a(c−d)
y=a+b
z=a−b
ac-bd=zd+x
ad+bc=yc−x

FFT では、y と z は完全に回転因子から得られるため、事前に計算してルックアップ テーブルに格納できます。したがって、要件は満たされています。FFT トリック