Pourquoi élever au carré un nombre plus rapide que la multiplication de deux nombres aléatoires?
https://stackoverflow.com/questions/1377430
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Multipliant deux nombres binaires prend n ^ 2 temps, mais un certain nombre d'élévation au carré peut se faire plus efficacement en quelque sorte. (N étant le nombre de bits) Comment pourrait-il être?
Ou est-il pas possible? C'est la folie!
La solution
-
Il existe des algorithmes plus efficaces que O (N ^ 2) pour multiplier deux nombres (voir Karatsuba, Pollard, Schönhage-Strassen, etc.)
-
Les deux problèmes "multiplier deux nombres arbitraires de N-bits" et "carré arbitraire nombre N bits" ont la même complexité.
Nous avons
4*x*y = (x+y)^2 - (x-y)^2
Donc, si la quadrature des nombres entiers N bits prend O (f (N)) fois, puis le produit de deux nombres entiers N bits arbitraire peut être obtenu en O (f (N)) aussi. (Qui est 2x sommes N bits, 2x carrés de N bits, 1x somme à 2n bits, et 1x décalage à 2n bits)
Et, évidemment, nous avons
x^2 = x * x
Donc, si la multiplication de deux nombres entiers N bits prend O (f (N)), puis d'élévation au carré d'un nombre entier N-bit peut être fait en O (f (N)).
Tout algorithme de calcul du produit (resp carré) fournit un algorithme pour calculer le carré (resp le produit) avec le même coût asymptotique.
Comme il est indiqué dans d'autres réponses, les algorithmes utilisés pour la multiplication rapide peuvent être simplifiées dans le cas d'élévation au carré. Le gain sera de la constante devant le f (N), et non pas sur f (N) lui-même.
Autres conseils
Squaring un nombre de n chiffres peut être plus rapide que la multiplication de deux nombres de chiffres n aléatoire. Googler J'ai trouvé cet article . Il est sur l'arithmétique de précision arbitraire, mais il peut être pertinent à ce que votre demande. Dans ce document, les auteurs disent ceci:
En élevant au carré un grand nombre entier, à savoir X ^ 2 = (XN-1, XN-2, ..., x1, x0) ^ 2 de nombreux termes de produits croisés de la forme xi * xj et xj * xi sont équivalentes. Ils doivent être calculés qu'une seule fois et gauche décalée afin d'être doublé. Une opération d'élévation au carré n chiffres est effectuée en utilisant seulement (n ^ 2 + n) / 2 multiplications simple précision.
Comme d'autres l'ont souligné, mise au carré ne peut être d'environ 1,5x ou 2x plus rapide que la multiplication régulière entre les nombres arbitraires. D'où vient l'avantage de calcul de? Il est symétrie. Calculons la place de 1011 et essayer de repérer un modèle que nous pouvons exploiter. u0:u3 représentent les bits dans le nombre de la plus significative à la moins significative.
1011 // u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3
1011 // u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3
0000 // u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3
1011 // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3
Si l'on considère les éléments ui * ui pour i=0, 1, ..., 4 pour former la diagonale et les ignorer, vous verrez que les éléments ui * uj pour i ≠ j sont répétées deux fois.
Par conséquent, tout ce que vous devez faire est de calculer la somme des produits pour les éléments ci-dessous la diagonale et le doubler, avec un décalage vers la gauche. Vous souhaitez enfin ajouter les éléments en diagonale. Maintenant, vous pouvez voir où la vitesse 2X up vient. Dans la pratique, la vitesse-up est d'environ 1,5 fois en raison des opérations en diagonale et supplémentaires.
Je crois que vous faites allusion exponentiation par élévation au carré . Cette technique ne sert pas à multiplier, mais pour élever à une puissance x ^ n, où n peut être grande. Plutôt que de multiplier x fois elle-même N fois, on effectue une série d'élévation au carré et en ajoutant des opérations qui peuvent être mis en correspondance avec la représentation binaire de N. Le nombre d'opérations de multiplication (qui sont plus chers que les additions pour un grand nombre) est réduite à partir de N à log (N) par rapport à l'algorithme d'exponentiation naïf.
Voulez-vous dire multiplier un nombre par une puissance de 2? Ceci est généralement plus rapide que de multiplier deux nombres aléatoires puisque le résultat peut être calculé par décalage simple bit. Cependant, gardez à l'esprit que les microprocesseurs modernes de silicium beaucoup consacrent la force brute à ces types de calculs et la plus arithmétique est réalisée avec une vitesse fulgurante par rapport aux microprocesseurs âgés
Je l'ai!
2 * 2
est plus cher que
2 << 1
(La mise en garde étant, il ne fonctionne que pour un cas.)
Supposons que vous souhaitez étendre le (a+b)×(c+d) de multiplication. Il se divise en quatre multiplications individuels. a×c + a×d + b×c + b×d
Mais si vous voulez étendre sur (a+b)², il n'a besoin que trois multiplications (et un doublement):. a² + 2ab + b²
(Notez également que deux des multiplications sont des carrés eux-mêmes.)
Espérons que cela commence juste à donner un aperçu de quelques-unes des speedups qui sont possibles lors de l'exécution d'un carré sur une multiplication régulière.
D'abord une grande question! Je souhaite qu'il y avait d'autres questions comme celle-ci.
Il se trouve que la méthode que je suis venu avec O (n log n) pour la multiplication générale de la complexité arithmétique seulement. Vous pouvez représenter un nombre X
X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0
où
x_i, y_i \in {0,1}
puis
XY = sum _ {k=0} ^ m+n r_k 2^k
où
r_k = sum _ {i=0} ^ k x_i y_{k-i}
qui est juste une application avant droite de FFT pour trouver les valeurs de r_k pour chaque k (n + m) log (n + m) temps.
Ensuite, pour chaque r_k vous devez déterminer la taille du débordement est et de l'ajouter en conséquence. Pour un certain nombre d'élévation au carré, cela signifie O (n log n) arithmétique opérations.
Vous pouvez ajouter les valeurs de r_k plus efficacement en utilisant l'opération de bits algorithme Schönhage-Strassen pour obtenir un O (n log n log log n) lié.
La réponse exacte à votre question est déjà affichée par Eric Bainville.
Cependant, vous peut obtenir une bien meilleure borne que O (n ^ 2) pour élever au carré un nombre simplement parce qu'il existe des limites beaucoup mieux pour multiplier les entiers!
Si vous assumez la longueur fixée à la taille de mot de la machine et que le numéro à carré est en mémoire, une opération d'élévation au carré nécessite une seule charge de la mémoire, donc peut être plus rapide.
Pour les entiers de longueur arbitraire, la multiplication est généralement O (N²), mais il existe des algorithmes qui réduisent ce pour les grands entiers.
Si vous assumez l'approche simple O (N²) à multiplier a par b , puis pour chaque bit dans a vous devez changer b et l'ajouter à un accumulateur si ce bit est un. Pour chaque bit dans a vous avez besoin des changements et des ajouts 3N.
Notez que
( x - y )² = x² - 2 xy + y²
Par conséquent
x² = ( x - y )² + 2 xy - y²
Si chaque y est la plus grande puissance de deux pas plus grand que x, ce qui donne une réduction à un carré inférieur, deux quarts de travail et deux ajouts. Comme N est réduit à chaque itération, vous pouvez obtenir un gain d'efficacité (la symétrie signifie qu'il se rend chaque point dans un triangle plutôt qu'un rectangle), mais il est encore O (N²).
Il peut y avoir une autre meilleure symétrie à exploiter.
a ^ 2 (A + b) * (a + b) + b ^ 2, par exemple. ^ 2 = 66 (66 + 6) (66-6) + 6 ^ 2 = 72 * 60 + 36 = 4356
pour une ^ n il suffit d'utiliser la règle de puissance
66 ^ 4 = 4356 ^ 2
Je voudrais résoudre le problème par la multiplication N bits pour un certain nombre
A bits soit A (n-1) A (n-2) ........ A (1) A (0).
B bits est B (n-1) B (n-2) ........ B (1) B (0).
pour le carré du nombre A des bits de multiplication uniques générés seront A (0) -> (0) .... A (n-1) A (1) -> (1) .... A (n-1) et ainsi de suite donc l'ensemble des opérations seront
OP = n + n-1 + 2 n-1 + ....... Par conséquent OP = n ^ 2 + n / 2; de sorte que la notation asymptotique sera O (n ^ 2)
et pour la multiplication de A et de B n ^ 2 multiplications unique sera généré de sorte que la notation asymptotique sera O (n ^ 2)
La racine carrée de 2 n est de 2 n / 2 ou 2 n >> 1 , donc si votre numéro est une puissance de deux tout est tout à fait simple, une fois que vous connaissez le pouvoir. Pour multiplier est encore plus simple: 2 4 * 2 8 est égal à 2 4 + 8 . Il n'y a pas de sens dans ce que vous avez fait des déclarations.
Si vous avez un nombre binaire A, il peut (toujours, la preuve laissée au lecteur avide) est exprimée en (2 ^ n + B), cela peut être carré comme 2 ^ 2n + 2 ^ (n + 1) B + B ^ 2. On peut alors répéter l'expansion, jusqu'à un point tel que B est égal à zéro. Je ne l'ai pas regardé trop dur, mais intuitivement, il se sent comme si vous devriez être en mesure de faire une fonction d'élévation au carré de prendre moins d'étapes algorithmiques qu'une multiplication d'usage général.
Je pense que vous êtes tout à fait tort dans vos déclarations
Multipliant deux nombres binaires prend n ^ 2 temps
Multipliant deux numéros 32bit prennent exactement un cycle d'horloge. Sur un processeur 64 bits, je suppose que la multiplication de deux nombres 64 bits prennent exactement 1 cycle d'horloge. Il ne serait pas même surprendre mon qu'un processeur 32 bits peut multiplier deux nombres de 64 bits dans le cycle 1 d'horloge.
yet squaring a number can be done more efficiently somehow.
Squaring un numéro est juste le nombre avec multiplie lui-même, de sorte que est juste une simple multiplication. Il n'y a pas d'opération « carré » dans la CPU.
Peut-être que vous confondez « élévation au carré » avec « la multiplication par une puissance de 2 ». La multiplication par deux peut être implemeted en déplaçant tous les bits d'une position vers la « gauche ». La multiplication par 4 se déplace tous les bits de deux positions à la « gauche ». En 8, 3 positions. Mais cette astuce ne s'applique qu'à une puissance de deux.
