Devrais-je utiliser la multiplication ou la division?

Voici une question amusante stupide:

Disons que nous devons effectuer une opération simple où nous avons besoin de la moitié de la valeur d’une variable. Il y a généralement deux manières de le faire:

y = x / 2.0; // or... y = x * 0.5; 

En supposant que nous utilisons les opérateurs standard fournis avec le langage, lequel a les meilleures performances?

J’imagine que la multiplication est généralement meilleure, alors j’essaye de m’en tenir à cela quand je code, mais je voudrais le confirmer.

Bien que personnellement je sois intéressé par la réponse de Python 2.4-2.5, n’hésitez pas à poster une réponse pour d’autres langues! Et si vous le souhaitez, n’hésitez pas à utiliser d’autres moyens plus sophistiqués (comme utiliser des opérateurs de décalage au niveau du bit).

Python:

 time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0' real 0m26.676s user 0m25.154s sys 0m0.076s time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5' real 0m17.932s user 0m16.481s sys 0m0.048s 

la multiplication est 33% plus rapide

Lua:

 time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end' real 0m7.956s user 0m7.332s sys 0m0.032s time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end' real 0m7.997s user 0m7.516s sys 0m0.036s 

=> pas de vraie différence

LuaJIT:

 time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end' real 0m1.921s user 0m1.668s sys 0m0.004s time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end' real 0m1.843s user 0m1.676s sys 0m0.000s 

=> c’est seulement 5% plus rapide

conclusions: en Python, il est plus rapide de se multiplier que de diviser, mais à mesure que vous vous rapprochez du processeur en utilisant des machines virtuelles ou des JIT plus avancés, l’avantage disparaît. Il est tout à fait possible qu’un futur Python VM le rende inutile

Toujours utiliser ce qui est le plus clair. Tout ce que vous faites, c’est essayer de déjouer le compilateur. Si le compilateur est du tout intelligent, il fera de son mieux pour optimiser le résultat, mais rien ne peut faire que le gars suivant ne vous déteste pas pour votre solution de bitshifting (j’adore la manipulation des bits, c’est amusant. Mais amusant! = Lisible )

L’optimisation prématurée est la racine de tout Mal. Rappelez-vous toujours les trois règles d’optimisation!

  1. Ne pas optimiser
  2. Si vous êtes un expert, voir la règle n ° 1
  3. Si vous êtes un expert et pouvez justifier le besoin, utilisez la procédure suivante:

    • Code non optimisé
    • Déterminez la rapidité de “Fast vitesse” – Notez quelle exigence / article utilisateur requirejs cette mesure.
    • Ecrire un test de vitesse
    • Testez le code existant – Si c’est assez rapide, vous avez terminé.
    • Recoder il optimisé
    • Testez le code optimisé. Si elle ne correspond pas à la mésortingque, jetez-la et conservez l’original.
    • S’il répond au test, conservez le code d’origine sous forme de commentaires

De même, faire des choses comme supprimer des boucles internes lorsqu’elles ne sont pas requirejses ou choisir une liste liée sur un tableau pour un sorting par insertion ne sont pas des optimisations, mais de la programmation.

Je pense que cela devient tellement épineux que vous feriez mieux de faire tout ce qui rend le code plus lisible. À moins que vous exécutiez les opérations des milliers, voire des millions, de fois, je doute que personne ne remarquera jamais la différence.

Si vous devez vraiment faire le choix, l’parsing comparative est la seule solution. Trouvez quelle (s) fonction (s) vous pose des problèmes, puis trouvez où se trouvent les problèmes et corrigez ces sections. Cependant, je doute encore qu’une opération mathématique unique (même une répétition de nombreuses, plusieurs fois) soit la cause d’un goulot d’étranglement.

La multiplication est plus rapide, la division est plus précise. Vous perdrez une certaine précision si votre nombre n’est pas un pouvoir de 2:

 y = x / 3.0; y = x * 0.333333; // how many 3's should there be, and how will the comstackr round? 

Même si vous laissez le compilateur déterminer la constante inversée pour obtenir une précision parfaite, la réponse peut toujours être différente.

 x = 100.0; x / 3.0 == x * (1.0/3.0) // is false in the test I just performed 

Le problème de la vitesse ne risque d’être important que dans les langages C / C ++ ou JIT, et ce même si l’opération est en boucle sur un goulot d’étranglement.

Si vous souhaitez optimiser votre code tout en restant clair, essayez ceci:

 y = x * (1.0 / 2.0); 

Le compilateur doit être capable de faire la division au moment de la compilation, vous obtenez donc une multiplication au moment de l’exécution. Je m’attendrais à ce que la précision soit la même que dans le cas y = x / 2.0 .

Là où cela peut avoir de l’importance, LOT est dans les processeurs intégrés où l’émulation en virgule flottante est nécessaire pour calculer l’arithmétique en virgule flottante.

Juste pour append quelque chose pour l’option “autres langues”.
C: Comme il ne s’agit que d’un exercice académique qui ne fait aucune différence, j’ai pensé que je consortingbuerais à quelque chose de différent.

J’ai compilé pour assembler sans optimisations et j’ai regardé le résultat.
Le code:

 int main() { volatile int a; volatile int b; asm("## 5/2\n"); a = 5; a = a / 2; asm("## 5*0.5"); b = 5; b = b * 0.5; asm("## done"); return a + b; } 

compilé avec gcc tdiv.c -O1 -o tdiv.s -S

la division par 2:

 movl $5, -4(%ebp) movl -4(%ebp), %eax movl %eax, %edx shrl $31, %edx addl %edx, %eax sarl %eax movl %eax, -4(%ebp) 

et la multiplication par 0.5:

 movl $5, -8(%ebp) movl -8(%ebp), %eax pushl %eax fildl (%esp) leal 4(%esp), %esp fmuls LC0 fnstcw -10(%ebp) movzwl -10(%ebp), %eax orw $3072, %ax movw %ax, -12(%ebp) fldcw -12(%ebp) fistpl -16(%ebp) fldcw -10(%ebp) movl -16(%ebp), %eax movl %eax, -8(%ebp) 

Cependant, quand j’ai changé ceux-ci en double (ce que python ferait probablement), j’ai ceci:

division:

 flds LC0 fstl -8(%ebp) fldl -8(%ebp) flds LC1 fmul %st, %st(1) fxch %st(1) fstpl -8(%ebp) fxch %st(1) 

multiplication:

 fstpl -16(%ebp) fldl -16(%ebp) fmulp %st, %st(1) fstpl -16(%ebp) 

Je n’ai pas évalué ce code, mais en examinant simplement le code, vous pouvez voir que l’utilisation d’entiers est plus courte que la multiplication par 2. En utilisant des doubles, la multiplication est plus courte car le compilateur utilise les opcodes en virgule flottante du processeur. probablement courir plus vite (mais en fait je ne sais pas) que de ne pas les utiliser pour la même opération. Donc, en fin de compte, cette réponse a montré que les performances de la multiplication par 0,5 vs division par 2 dépendent de la mise en œuvre du langage et de la plate-forme sur laquelle il s’exécute. En fin de compte, la différence est négligeable et c’est quelque chose dont vous ne devriez pratiquement jamais vous soucier, sauf en termes de lisibilité.

En guise de note, vous pouvez voir que dans mon programme, main() renvoie a + b . Lorsque je retire le mot-clé volatile, vous ne devinerez jamais à quoi ressemble l’assemblage (à l’exception de la configuration du programme):

 ## 5/2 ## 5*0.5 ## done movl $5, %eax leave ret 

il a fait à la fois la division, la multiplication et l’addition dans une seule instruction! Clairement, vous n’avez pas à vous soucier de cela si l’optimiseur est respectable.

Désolé pour la réponse trop longue.

Écrivez ce qui indique plus clairement votre intention.

Une fois que votre programme fonctionne, déterminez ce qui est lent et accélérez les choses.

Ne le faites pas dans l’autre sens.

Faites ce dont vous avez besoin. Pensez d’abord à votre lecteur, ne vous inquiétez pas des performances tant que vous n’êtes pas certain d’avoir un problème de performance.

Laissez le compilateur faire les performances pour vous.

Premièrement, à moins que vous ne travailliez en C ou en ASSEMBLY, vous vous trouvez probablement dans un langage de plus haut niveau où les blocages de mémoire et les frais généraux d’appel surpasseront absolument la différence entre multiplier et diviser. Alors, choisissez simplement ce qui se lit mieux dans ce cas.

Si vous parlez à un niveau très élevé, il ne sera pas beaucoup plus lent pour tout ce que vous êtes susceptible de l’utiliser. Vous verrez dans d’autres réponses que les gens doivent faire un million de fois / diviser simplement pour mesurer une différence inférieure à la milliseconde entre les deux.

Si vous êtes toujours curieux, du sharepoint vue de l’optimisation de bas niveau:

Diviser tend à avoir un pipeline beaucoup plus long que la multiplication. Cela signifie que cela prend plus de temps pour obtenir le résultat, mais si vous pouvez garder le processeur occupé avec des tâches non dépendantes, cela ne vous coûtera pas plus qu’une multiplication.

La durée de la différence de pipeline dépend entièrement du matériel. Le dernier matériel que j’ai utilisé était quelque chose comme 9 cycles pour une multiplication de FPU et 50 cycles pour une division de FPU. Cela semble beaucoup, mais vous perdriez alors 1000 cycles pour un manque de mémoire, ce qui peut mettre les choses en perspective.

Une analogie est de mettre une tarte dans un four à micro-ondes pendant que vous regardez une émission de télévision. Le temps total que vous avez pris de la série télévisée est de combien de temps il a fallu le mettre au micro-ondes et le sortir du four à micro-ondes. Le rest de votre temps, vous avez encore regardé l’émission de télévision. Donc, si la tarte a mis 10 minutes à cuire au lieu d’1 minute, elle n’a plus utilisé votre temps de télévision.

En pratique, si vous voulez vous concentrer sur la différence entre Multiplier et Diviser, vous devez comprendre les pipelines, le cache, les stalls de twig, les prédictions hors-ordre et les dépendances de pipeline. Si cela ne sonne pas comme si vous aviez l’intention de répondre à cette question, la bonne réponse est d’ignorer la différence entre les deux.

Il y a de nombreuses années, il était absolument essentiel d’éviter les divisions et d’utiliser toujours des multiplications, mais à l’époque, les problèmes de mémoire étaient moins importants et les divisions étaient bien pires. De nos jours, la lisibilité est plus élevée, mais s’il n’y a pas de différence de lisibilité, je pense que c’est une bonne habitude d’opter pour les multiplications.

Si vous travaillez avec des nombres entiers ou non, n’oubliez pas vos opérateurs de transfert de bits: << >>

  int y = 10; y = y >> 1; Console.WriteLine("value halved: " + y); y = y << 1; Console.WriteLine("now value doubled: " + y); 

La multiplication est généralement plus rapide – certainement jamais plus lente. Cependant, si la vitesse n’est pas critique, écrivez le plus clair.

En fait, il y a une bonne raison pour que la multiplication générale soit plus rapide que la division. La division en virgule flottante dans le matériel se fait soit avec des algorithmes de décalage et de soustraction sous conditions («longue division» avec des nombres binarys) ou – plus probablement ces jours-ci – avec des itérations comme l’ algorithme de Goldschmidt . Shift et Subtract nécessitent au moins un cycle par bit de précision (les itérations sont presque impossibles à paralléliser, tout comme le décalage et l’ajout de la multiplication), et les algorithmes itératifs effectuent au moins une multiplication par itération . Dans les deux cas, il est fort probable que la division prenne plus de cycles. Bien sûr, cela ne tient pas compte des bizarreries dans les compilateurs, du mouvement des données ou de la précision. En gros, cependant, si vous codez une boucle interne dans une partie sensible du temps d’un programme, écrire 0.5 * x ou 1.0/2.0 * x plutôt que x / 2.0 est une chose raisonnable à faire. La pédanterie de “code quoi de plus clair” est absolument vraie, mais toutes les trois sont si faciles à lire que le pédantisme est ici simplement pédant.

La division en virgule flottante est (généralement) particulièrement lente, alors que la multiplication en virgule flottante est également relativement lente, elle est probablement plus rapide que la division en virgule flottante.

Mais je suis plus enclin à répondre “ça n’a pas vraiment d’importance”, à moins que le profilage ait montré que la division est un goulot d’étranglement par rapport à la multiplication. Je suppose cependant que le choix de la multiplication par rapport à la division ne va pas avoir un impact important sur la performance de votre application.

Cela devient plus une question quand vous programmez en assembleur ou peut-être en C. Je pense qu’avec la plupart des langages modernes, cette optimisation est faite pour moi.

Méfiez-vous de “deviner que la multiplication est généralement meilleure, alors j’essaye de m’en tenir à cela quand je code”

Dans le contexte de cette question spécifique, mieux vaut ici “plus rapide”. Ce qui n’est pas très utile.

Penser à la vitesse peut être une grave erreur. La forme algébrique spécifique du calcul comporte de profondes implications d’erreur.

Voir l’ arithmétique en virgule flottante avec parsing d’erreur . Voir les problèmes de base en arithmétique en virgule flottante et en parsing d’erreur .

Alors que certaines valeurs à virgule flottante sont exactes, la plupart des valeurs à virgule flottante sont une approximation. ils sont une valeur idéale plus une erreur. Chaque opération s’applique à la valeur idéale et à la valeur d’erreur.

Les plus gros problèmes proviennent de la manipulation de deux nombres presque égaux. Les bits les plus à droite (les bits d’erreur) dominent les résultats.

 >>> for i in range(7): ... a=1/(10.0**i) ... b=(1/10.0)**i ... print i, a, b, ab ... 0 1.0 1.0 0.0 1 0.1 0.1 0.0 2 0.01 0.01 -1.73472347598e-18 3 0.001 0.001 -2.16840434497e-19 4 0.0001 0.0001 -1.35525271561e-20 5 1e-05 1e-05 -1.69406589451e-21 6 1e-06 1e-06 -4.23516473627e-22 

Dans cet exemple, vous pouvez voir que lorsque les valeurs diminuent, la différence entre des nombres presque égaux crée des résultats non nuls où la réponse correcte est zéro.

J’ai toujours appris que la multiplication est plus efficace.

J’ai lu quelque part que la multiplication est plus efficace en C / C ++; Aucune idée concernant les langages interprétés – la différence est probablement négligeable en raison de tous les autres frais généraux.

À moins que cela ne devienne un problème, tenez compte de ce qui est plus facile à entretenir / à lire – Je déteste quand les gens me le disent, mais c’est tellement vrai.

Je suggère la multiplication en général, car vous n’avez pas à passer les cycles pour vous assurer que votre diviseur n’est pas 0. Cela ne s’applique évidemment pas si votre diviseur est une constante.

Java Android, profilé sur Samsung GT-S5830

 public void Mutiplication() { float a = 1.0f; for(int i=0; i<1000000; i++) { a *= 0.5f; } } public void Division() { float a = 1.0f; for(int i=0; i<1000000; i++) { a /= 2.0f; } } 

Résultats?

 Multiplications(): time/call: 1524.375 ms Division(): time/call: 1220.003 ms 

La division est environ 20% plus rapide que la multiplication (!)

Comme pour les publications # 24 (la multiplication est plus rapide) et # 30 – mais parfois elles sont toutes deux faciles à comprendre:

 1*1e-6F; 1/1e6F; 

~ Je les trouve tous les deux faciles à lire et je dois les répéter des milliards de fois. Il est donc utile de savoir que la multiplication est généralement plus rapide.

Il y a une différence, mais cela dépend du compilateur. Au début, sur vs2003 (c ++), je n’ai obtenu aucune différence significative pour les types doubles (virgule flottante 64 bits). Cependant, en lançant à nouveau les tests sur vs2010, j’ai détecté une énorme différence, allant jusqu’à un facteur 4 plus rapide pour les multiplications. En suivant cela, il semble que vs2003 et vs2010 génèrent un code fpu différent.

Sur un Pentium 4, 2,8 GHz, vs2003:

  • Multiplication: 8.09
  • Division: 7,97

Sur un Xeon W3530, vs2003:

  • Multiplication: 4.68
  • Division: 4.64

Sur un Xeon W3530, vs2010:

  • Multiplication: 5.33
  • Division: 21.05

Il semble que sur vs2003 une division dans une boucle (donc le diviseur a été utilisé plusieurs fois) a été traduite en une multiplication avec l’inverse. Sur vs2010, cette optimisation n’est plus appliquée (je suppose que le résultat est légèrement différent entre les deux méthodes). Notez également que le processeur effectue des divisions plus rapidement dès que votre numérateur est 0.0. Je ne connais pas l’algorithme précis câblé dans la puce, mais peut-être dépend-il du nombre.

Edit 18-03-2013: l’observation pour vs2010

Eh bien, si nous supposons qu’une opération d’ajout / soustraction coûte 1, alors multipliez les coûts 5 et divisez les coûts par 20 environ.

Après une discussion aussi longue et intéressante, voici ma réponse: il n’ya pas de réponse définitive à cette question. Comme certaines personnes l’ont souligné, cela dépend à la fois du matériel (cf piotrk et gast128 ) et du compilateur (cf tests de @Javier ). Si la vitesse n’est pas critique, si votre application n’a pas besoin de traiter une énorme quantité de données en temps réel, vous pouvez opter pour la clarté en utilisant une division alors que la vitesse de traitement ou la charge du processeur pose problème. Enfin, à moins que vous ne sachiez exactement sur quelle plate-forme votre application sera déployée, le benchmark est dénué de sens. Et pour la clarté du code, un seul commentaire ferait l’affaire!

Voici une réponse amusante stupide:

x / 2.0 n’est pas équivalent à x * 0.5

Disons que vous avez écrit cette méthode le 22 octobre 2008.

 double half(double x) => x / 2.0; 

Maintenant, 10 ans plus tard, vous apprenez que vous pouvez optimiser ce morceau de code. La méthode est référencée dans des centaines de formules tout au long de votre application. Donc, vous le changez et bénéficiez d’une amélioration remarquable de 5% des performances.

 double half(double x) => x * 0.5; 

Était-ce la bonne décision pour changer le code? En maths, les deux expressions sont en effet équivalentes. En informatique, cela n’est pas toujours vrai. Veuillez lire Réduire l’effet des problèmes de précision pour plus de détails. Si vos valeurs calculées sont, à un moment donné, comparées à d’autres valeurs, vous modifierez le résultat des observations de bord. Par exemple:

 double quantize(double x) { if (half(x) > threshold)) return 1; else return -1; } 

La ligne du bas est; une fois que vous vous contentez de l’un des deux, alors respectez-le!

Techniquement, il n’y a pas de division, il y a juste multiplication par éléments inverses. Par exemple, vous ne divisez jamais par 2, vous multipliez en fait par 0,5.

‘Division’ – laissez-nous savoir qu’il existe depuis une seconde – est toujours plus difficile que de multiplier parce que ‘diviser’ x par y il faut d’abord calculer la valeur y^{-1} telle que y*y^{-1} = 1 et ensuite la multiplication x*y^{-1} . Si vous connaissez déjà y^{-1} alors ne pas le calculer à partir de y doit être une optimisation.