Произведение двух комплексных чисел менее чем в 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_i, W_i, X_i, Y_i и Z_i следующим образом.

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 неизвестных, C_i, W_i, X_i, Y_i и Z_i, где (i = 1,2,3,4), которые не имеют реального решения и, следовательно, не имеют способ выполнить сложное умножение в двух реальных умножениях

Источник:

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

Answer 1

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

(Примечание: впредь я буду сокращать "умножение (я) двух неопределенных величин" как "MNPQ(s)".)

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

Между прочим, доказательство опирается на неустановленную предпосылку: если все, что у вас есть, это сложения, вычитания и умножения на заранее определенные константы, то в конечном итоге все, что вы делаете, будет равносильно линейной комбинации ваших входных данных. (Вы понимаете, почему?) Таким образом, оба MNPQ будут умножением линейных комбинаций { a, b, c, d }, и способ, которым вы "поделитесь" их результатами, будет для { ac − bd, ad + bc } быть двумя различными линейными комбинациями результатов этих MNPQ. (Для полного доказательства потребуется более тщательный аргумент относительно возможности того, что результат одного MNPQ может быть аргументом для другого, а также возможность того, что окончательные линейные комбинации включают в себя не только результаты MNPQ, но также { a, b, c, d }, но это помечено просто как "эскиз доказательства", поэтому я думаю, что о таких вещах не стоит беспокоиться.)

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

Answer 2

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

Предположим, что мы можем оценить умножение двух комплексных чисел на 2 действительных умножения, тогда вам необходимо оценить ac-bd и ad+bc, используя 2 умножения.

Он должен быть представлен таким образом, чтобы обе оценки состояли из одинаковых двух умножений с разными действительными постоянными коэффициентами C1, C2, C3, C4, где Xi, Yi, Zi, Wi также должны быть действительными числами.

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