Produit de deux nombres complexes en moins de 3 multiplications

Question

Quelqu'un peut-il me démonter? Pourquoi ne peut-il pas être fait en deux multiplications?

La multiplication des nombres complexes

Si le nombre de multiplications nécessaires à un calcul est considéré comme une mesure de la difficulté et ces calculs sont effectués en utilisant des nombres complexes, il est naturel de se demander combien de multiplications réelles sont nécessaires à évaluer les parties réelles et imaginaires d'un produit complexe. La manière naturelle de former un produit complexe nécessite quatre multiplications réelles. Il peut cependant être fait en trois mais pas en deux multiplications.

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

théorème - L'évaluation du produit de deux nombres complexes nécessite trois multiplications réelles, même si la multiplication par des constantes réelles est pas pris en compte.

Esquisse de la preuve Puisque ni le réel, ni la partie complexe d'une multiplication complexe peut être déterminée dans une multiplication réelle, si ce calcul peut être fait en deux multiplications ce sera fait, pour un certain choix de C _i, W _i, X _i, Y _i et Z _i de la manière suivante.

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) 

Cela conduit à des 20 équations non linéaires dans les 20 inconnues, C _i, W _i, X _i, Y _i et Z _i où (i = 1, 2,3,4), qui n'a pas de solution réelle et donc il n'y a aucun moyen d'effectuer une multiplication complexe en deux multiplications réelles

Source:

Munro, Ian. "40-44." http://dl.acm.org/. Proc. des Actes du Troisième Symposium Annuel ACM sur la Théorie de l'Informatique, Ohio, Shaker Heights. Ed. Michael A. Harrison, Ranan B. Banerji et Jeffrey D. Ullman. Acm, 3 mai 1971. Web. 26 nov. 2016. http://dl.acm.org/citation.cfm?doid=800157.805036.

Answer 1

La preuve est contradictoire.

On suppose que nous pouvons évaluer la multiplication de deux nombres complexes par 2 multiplications réelles, alors vous devez évaluer ac-bd et ad + bc avec 2 multiplications.

Il aurait dû la manière affichée par vous où les évaluations se composent des exactement les mêmes deux multiplications à coefficients constants réels différents C1, C2, C3, C4 où Xi, Yi, Zi, Wi devraient être des nombres réels aussi bien.

Étant donné que les coefficients de a^2, b^2, c^2, d^2, ab, ac, ad, bc, bd, cd doit correspondre dans les deux équations, nous avons 20 non linéaire équations avec 20 inconnues. Par exemple, C1 * * W1 W2 + W3 * C2 * W4 = 0 pour a^2 dans la première évaluation de ac-bd. Cette preuve affirme en outre que le système n'a pas de vraies solutions et, par conséquent, l'hypothèse ne tient pas.

Answer 2

Ainsi, le théorème étant prouvé ici est fondamentalement « Même si vous pouvez faire autant additions, soustractions, multiplications et-par-constantes de prédéterminées que vous le souhaitez, vous ne pouvez pas calculer ac-bd et ad + bc sans faire au moins trois multiplications-de-deux- non -déterminées-quantités. "

(Note:. Désormais, je vais abréger "multiplication (s) de deux quantités non prédéterminé" comme "MNPQ (s)")

La preuve commence en signalant que vous ne pouvez certainement pas calculer soit l'un des {ac-bd, ad + bc} avec juste un seul MNPQ. La seule façon vous pouvez calculer les deux d'entre eux avec seulement deux MNPQs serait si vous pouvez en quelque sorte « partager » les MNPQs, utilisant à la fois de leurs résultats dans les deux {ac-bd, ad + bc } D'ailleurs, la preuve repose sur le principe implicite que si tout ce que vous avez sont des additions, des soustractions et des multiplications par des constantes prédéterminées, alors tout ce que vous faites équivaudra finalement à une combinaison linéaire de vos entrées. (Est-ce que vous voyez pourquoi?) Donc, les deux MNPQs seront tous deux multiplications de combinaisons linéaires de {un, b, c, d}, et la façon dont vous « partager » leurs résultats seront pour {ac-bd, ad + bc} être deux combinaisons linéaires différentes des résultats de ces MNPQ. (A complet preuve nécessiterait un argument plus approfondi concernant la possibilité que le résultat d'un MNPQ pourrait être un argument à l'autre, ainsi que la possibilité que les combinaisons linéaires finales incorporent non seulement les résultats des MNPQ mais aussi { un, b, c, d}, mais cela est étiqueté juste « croquis de la preuve », donc je suppose qu'il n'a pas à se soucier de ces choses)

Si vous acceptez. cette prémisse, alors nous pouvons écrire les deux MNPQ comme (W₁a + X₁b + Y₁c + Z₁d) & middot; (W₂a + X₂b + Y₂c + Z₂d) et (W₃a + X₃b + Y₃c + Z₃d) & middot; (W₄a + X₄b + Y₄c + Z₄d), et leurs deux l combinaisons inear (ac-bd et ad + bc) en tant que C₁ (MNPQ) ₁ + C₂ (MNPQ) ₂ et C₃ (MNPQ) ₃ + C₄ (MNPQ) ₄. Si vous multipliez ensuite tout par, vous obtenez un système d'équations pour résoudre les inconnues à résoudre pour être les constantes magiques W₁, X₂, C₃, etc. — sauf que, comme il s'avère, ce système d'équations n'a réellement aucune solution .Par conséquent, aucun ensemble de constantes magiques ne permettra cette approche, donc cette approche est impossible, donc vous devez effectuer au moins trois MNPQ afin de calculer à la fois ac-bd et ad + bc.