Мы выполняем комплексное умножение чисел следующим образом:
(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)
Это включает в себя четыре реальных умножения. Как мы можем это сделать только с тремя действительными умножениями?
Вас интересуют два номера: A=ac−bd и B=ad+bc.
Вычислите три действительных умножения S1=ac,S2=bd, and S3=(a+b)(c+d).
Теперь вы можете вычислить результаты как
A=S1−S2 и B=S3−S1−S2.
Этот процесс называется умножением Карацубы и сильно используется в анализе алгоритмов.
Используется для нахождения ближайшей пары точек.
Для полноты, я хотел бы указать комплексный алгоритм умножения Гаусса, что является еще одним способом комплексного умножения с тремя размножается. Подводя итог, вы вычисляете
k1 = c * (a + b)
k2 = a * (d - c)
k3 = b * (c + d)
Real part = k1 - k3
Imaginary part = k1 + k2
Некоторые алгоритмы, например. 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 полностью исходят из коэффициентов twiddle, поэтому их можно предварительно вычислить и сохранить в справочной таблице. Таким образом, требование выполнено. FFT Tricks
Валлаб Патаде уже ответил, как выполнить произведение между двумя комплексными числами только с тремя действительными умножениями. Применение алгоритма Karatsuba действительно является следующим
x = a + i * b;
y = c + i * d;
real(x * y) = a * c - b * d;
imag(x * y) = (a + b) * (c + d) - a * c - b * d;
Теперь возникает вопрос: можем ли мы выполнить произведение между двумя комплексными числами с less, чем три реальных умножения?
Ответ NO и предоставляется теоремой Винограда в
S. Winograd, "On the number of multiplications required to compute certain functions", Commun. Pure Appl. Math. 23 (1970), 165-179.
Минимальное количество умножений, требуемое при вычислении произведения между двумя комплексными числами, равно трем.