4

有人可以帮我分解一下吗？为什么不能在两次乘法中完成？

复数的乘法

如果将计算所需的乘法次数视为其难度的衡量标准，并且这些计算是使用复数执行的，那么很自然地会问需要多少实数乘法来评估复数乘积的实部和虚部。形成复数乘积的自然方式需要四次实数乘法。然而，它可以用三个而不是两个乘法来完成。

(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。

4

2 回答 2

1

所以，这里要证明的定理基本上是，“即使你可以随心所欲地做任意多的加法、减法和乘法运算，你也无法计算ac−bd和ad+bc至少不做三个非预定量的二乘法。”

（注：此后，我将“两个非预定量的乘法”缩写为“MNPQ(s)”。）

证明首先指出你肯定不能只用一个 MNPQ计算 { ac−bd , ad+bc } 中的任何一个。所以你可以用两个MNPQ 计算它们的唯一方法是，如果你能以某种方式“共享”这些 MNPQ，在 { ac−bd , ad+bc } 中使用它们的两个结果。

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

于 2016-11-29T05:41:56.763 回答
0

证明是矛盾的。

假设我们可以计算两个复数乘以 2 次实数乘法，那么您需要使用 2 次乘法计算ac-bd和ad+bc。

它应该具有您发布的方式，其中两个评估都包含完全相同的两个乘法，具有不同的实常数系数C1、C2、C3、C4，其中Xi、Yi、Zi、Wi也应该是实数。

由于a^2, b^2, c^2, d^2, ab, ac, ad, bc, bd, cd的系数在两个方程中应该匹配，所以我们有 20 个非线性方程和 20 个未知数。例如，对于ac-bd的第一次评估中的a ^2 ， C1*W1*W2 + C2*W3*W4 = 0。该证明进一步声称该系统没有真正的解决方案，因此该假设不成立。

于 2016-11-29T04:02:12.937 回答