Продукт двух комплексных чисел менее чем за 3 умножения

Question

Может кто-то сломает это для меня? Почему это невозможно сделать двумя способами?

Умножение комплексных чисел

Если количество умножений, необходимых для вычисления рассматривается как мера сложности, так и эти расчеты выполняются с использованием комплексных чисел, то естественно спросить, сколько реальных умножений необходимы для оценки реальной и мнимой частей сложного продукта. Естественный способ формирования сложного продукта требует четырех реальных умножений. Можно, однако, выполнить три, но не в двух комбинациях.

(a+bi)(c+di) = (ac-bd) + (ad+bc)i 

a(c+d) - d(a+b) = ac - bd 
(1)  (2) 

a(c+d) + c(b-a) = ad + bc 
      (3) 

Теорема - Оценка произведения двух комплексных чисел требует три вещественных умножений, даже если умножение вещественных констант не учитывается.

Эскиз доказательства Поскольку ни реальное, ни сложная часть комплексного умножения может быть определены в одном вещественном умножении, если этот расчет может быть сделан в двух умножениях это не будет сделано, при некотором выборе C _я, Вт _я, X _я, У _я и Z _я следующим образом.

ac - bd = C₁(W₁a+X₁b+Y₁c+Z₁d) 
      (W₂a+X₂b+Y₂c+Z₂d) 
     + C₂(W₃a+X₃b+Y₃c+Z₃d) 
      (W₄a+X₄b+Y₄c+Z₄d) 
ad + bc = C₃(W₁a+X₁b+Y₁c+Z₁d) 
      (W₂a+X₂b+Y₂c+Z₂d) 
     + C₄(W₃a+X₃b+Y₃c+Z₃d) 
      (W₄a+X₄b+Y₄c+Z₄d) 

Это приводит к 20 нелинейных уравнений в 20 неизвестных, С _я, Вт _я, Х _I, У _я и Z _I где (я = 1, 2,3,4), которые не имеют никакого реального решения, и, следовательно, нет никакого способа для выполнения комплексного умножения в двух вещественных умножений

Источник:

Munro, Ian. "40-44". http://dl.acm.org/. Proc. Трудов третьего ежегодного симпозиума ACM по теории вычислений, Огайо, высоты шейкера. Издание Майкл А. Харрисон, Ранан Б. Банерджи и Джеффри Д. Ульман. Acm, 03 мая 1971. Веб. 26 ноября 2016. http://dl.acm.org/citation.cfm?doid=800157.805036.

Answer 1

Доказательство от противного.

Предположим, что мы можем оценить умножение двух комплексных чисел на 2 реальных умножений, то вам необходимо оценить AC-Bd и объявление + Ьс используя 2 умножений.

Это должно манера отправленного вами, где обе оценки состоит из точно тех же двух умножений с различными постоянными вещественными коэффициентами С1, С2, С3, С4 где Си, Yi, Zi, Беспроводная также должны быть действительными числами.

Поскольку коэффициенты a^2, b^2, c^2, d^2, ab, ac, ad, bc, bd, cd должны совпадать в двух уравнениях, имеем 20 нелинейных уравнения с 20 неизвестными. Например, С1 * W1 * W2 + W3, С2 * * W4 = 0 для а^2 в первой оценке AC-бд. Это доказательство далее утверждает, что система не имеет реальных решений, и поэтому предположение не выполняется.

Answer 2

Таким образом, теорема доказанности здесь, в основном, «Даже если вы можете сделать так много дополнений, вычитаний и умножения-по-заданной константой, как вам нравится, вы не можете вычислить ас-ДБ и ad + bc без выполнения как минимум трех умножений-двух-не -определенных величин. "

(Примечание. В дальнейшем я буду сокращайте «умножение (ы) два не предопределены количеств» как «MNPQ (ы)»)

Доказательства начинается, указывая на то, что вы, конечно, не можете вычислить либо один из {ac-bd, ad + bc} только с одним MNPQ. Таким образом, единственный способ, которым Вы могли бы вычислить как из них только с двух MNPQs если бы можно как-то «делиться» эти MNPQs, используя оба из их результатов в обоих {ас-бд, объявление + Ьс }.

Доказательство основывается на неустановленной предпосылке, между прочим, если все, что у вас есть, это дополнения, вычитания и умножения на предопределенные константы, то в конечном итоге все, что вы делаете, будет просто равняться линейной комбинации ваши входы. (Вы видите, почему?) Так что эти два MNPQs оба будут умножений линейных комбинаций {, б, с, d}, и способ, которым вы «доля» их результаты будут для {ac-bd, ad + bc} быть двумя различными линейными комбинациями результатов этих MNPQ. (A complete доказательство потребует более тщательного аргумента относительно возможности того, что результат одного MNPQ может быть аргументом другой, а также возможность того, что в конечные линейные комбинации включены не только результаты MNPQ, но также { , б, с, d}, но это помечена только «эскиз доказательства», так что я предполагаю, что это не нужно беспокоиться о таких вещах)

Если вы принимаете. это предположение, тогда мы можем записать два MNPQ как (W₁a + X₁b + Y₁c + Z₁d) & middot; (W₂a + X₂b + Y₂c + Z₂d) и (W₃a + X₃b + Y₃c + Z₃d) & middot; (W₄a + X₄b + Y₄c + Z₄d), и их два l (ac-bd и ad + bc) как C₁ (MNPQ) ₁ + C₂ (MNPQ) ₂ и C₃ (MNPQ) ₃ + C₄ (MNPQ) ₄. Если вы затем умножаете все, вы получаете систему уравнений для решения неизвестных решений для того, чтобы они были магическими константами W₁, X₂, C₃ и т. Д. —, за исключением того, что, как оказалось, эта система уравнений фактически не имеет решения ,Таким образом, ни один набор магических констант не включит этот подход, поэтому этот подход невозможен, поэтому вам необходимо выполнить как минимум три MNPQ, чтобы вычислить как ac-bd, так и ad + bc.