algorithm - 少于 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/ .过程。第三届年度 ACM 计算理论研讨会论文集，俄亥俄州，Shaker Heights。埃德。 Michael A. Harrison、Ranan B. Banerji 和 Jeffrey D. Ullman。 ACM，1971 年 5 月 3 日。网络。 2016 年 11 月 26 日。http://dl.acm.org/citation.cfm?doid=800157.805036 .

Answer 1

所以，这里要证明的定理基本上是，“即使你可以根据预定常数进行任意多的加法、减法和乘法，你也无法计算 ac−bd 和 ad+bc 而不是至少进行三次二乘法-非-预定量。”

(注:今后，我将“两个非预定量的乘法”简称为“MNPQ(s)”。)

证明首先指出您当然不能仅用一个 MNPQ 计算 { ac−bd, ad+bc } 中的任何一个。因此，您可以仅使用两个 MNPQ 来计算两者 的唯一方法是，如果您可以某种方式“共享”这些MNPQ，在{ < em>ac−bd, ad+bc }.

证明依赖于未说明的前提，顺便说一下，如果你得到的只是加法、减法和乘以预定常数，那么最终你所做的任何事情都将只是你的线性组合输入。 (明白为什么了吗？)所以这两个 MNPQ 都是 { a, b, c, 的线性组合的乘法d }，而您“分享”他们的结果的方式是 { ac−bd, ad+bc } 是两个不同的线性组合这些 MNPQ 的结果。 (完整 证明需要更彻底的论证，即一个 MNPQ 的结果可能是另一个 MNPQ 的结果的可能性，以及最终线性组合不仅包含以下结果的可能性MNPQs 还有 { 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.