Dois-je utiliser la multiplication ou la division?

Voici une question amusante idiote:

Disons que nous devons effectuer une opération simple où nous avons besoin de la moitié de la valeur d'une variable. Il existe généralement deux façons de procéder:

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

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

Je suppose que la multiplication est généralement meilleure, alors j'essaie de m'en tenir à cela lorsque je code, mais j'aimerais le confirmer.

Bien que personnellement je sois intéressé par la réponse pour Python 2.4-2.5, n'hésitez pas à publier également une réponse pour d'autres langues! Et si vous le souhaitez, n'hésitez pas à publier d'autres méthodes plus sophistiquées (comme l'utilisation d'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 réelle 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 VM ou des JIT plus avancés, l'avantage disparaît. Il est fort possible qu'une future machine virtuelle Python la rende inutile

Utilisez toujours ce qui est le plus clair. Tout ce que vous faites est d'essayer de déjouer le compilateur. Si le compilateur est un peu intelligent, il fera de son mieux pour optimiser le résultat, mais rien ne peut faire en sorte que le prochain type ne vous déteste pas pour votre solution de changement de bits merdique (j'aime peu la manipulation au fait, c'est amusant. Mais amusant! = Lisible )

L'optimisation prématurée est la racine de tout Mal. Souvenez-vous toujours des trois règles d'optimisation!

1. N'optimisez pas.
2. Si vous êtes un expert, consultez la règle n ° 1

3. Si vous êtes un expert et pouvez justifier le besoin, utilisez la procédure suivante:

   • Codez-le non optimisé
   • Déterminez à quelle vitesse est «Assez rapide» - Notez quelle exigence / histoire de l'utilisateur nécessite cette métrique.
   • Rédiger un test de vitesse
   • Testez le code existant - Si c'est assez rapide, vous avez terminé.
   • Recoder optimisé
   • Testez le code optimisé. S'il ne correspond pas à la métrique, jetez-le et conservez l'original.
   • S'il répond au test, conservez le code d'origine sous forme de commentaires

De plus, faire des choses comme supprimer les boucles internes quand elles ne sont pas nécessaires ou choisir une liste chaînée sur un tableau pour un tri par insertion ne sont pas des optimisations, juste de la programmation.

Je pense que cela devient tellement délicat que vous feriez mieux de faire tout ce qui rend le code plus lisible. À moins que vous n'effectuiez les opérations des milliers, voire des millions de fois, je doute que quiconque remarquera jamais la différence.

Si vous devez vraiment faire un choix, l'analyse comparative est la seule façon de procéder. Trouvez quelle (s) fonction (s) vous posent des problèmes, puis recherchez où dans la fonction les problèmes se produisent et corrigez ces sections. Cependant, je doute encore qu'une seule opération mathématique (même une opération répétée plusieurs, plusieurs fois) soit une cause de goulot d'étranglement.

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

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

Même si vous laissez le compilateur déterminer la constante inversée avec 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 vitesse n'a probablement d'importance que dans les langages C / C ++ ou JIT, et même dans ce cas uniquement si l'opération est dans une boucle à un goulot d'étranglement.

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

y = x * (1.0 / 2.0);

Le compilateur devrait ê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 y = x / 2.0cas.

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

Je vais juste ajouter quelque chose pour l'option "autres langues".
C: Comme il ne s'agit que d'un exercice académique qui ne fait vraiment aucune différence, j'ai pensé que j'apporterais quelque chose de différent.

J'ai compilé en assemblage 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, lorsque j'ai changé ces ints en doubles (ce que ferait probablement python), j'ai obtenu 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 évalué aucun de ce code, mais juste en examinant le code, vous pouvez voir qu'en utilisant des entiers, la division par 2 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, qui 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 la performance de la multiplication par 0,5 vs la division par 2 dépend de l'implémentation du langage et de la plateforme sur laquelle il fonctionne. Au final, la différence est négligeable et vous ne devriez pratiquement jamais vous inquiéter, sauf en termes de lisibilité.

En remarque, vous pouvez voir que dans mon programme main()renvoiea + b . Lorsque j'enlève le mot-clé volatile, vous ne devinerez jamais à quoi ressemble l'assemblage (à l'exclusion 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 en une seule instruction! De toute évidence, vous n'avez pas à vous en soucier si l'optimiseur est respectable.

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

Premièrement, à moins que vous ne travailliez en C ou en ASSEMBLAGE, vous êtes probablement dans un langage de niveau supérieur où les blocages de mémoire et les frais généraux d'appels éclipseront absolument la différence entre multiplier et diviser au point de ne plus être pertinent. Alors, choisissez simplement ce qui se lit mieux dans ce cas.

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

Si vous êtes toujours curieux, d'un point de vue d'optimisation de bas niveau:

Divide a tendance à avoir un pipeline beaucoup plus long que de se multiplier. Cela signifie qu'il faut plus de temps pour obtenir le résultat, mais si vous pouvez occuper le processeur 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 FPU et 50 cycles pour une division 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 consiste à mettre une tarte dans un micro-ondes pendant que vous regardez une émission de télévision. Le temps total qu'il vous a éloigné de l'émission télévisée correspond au temps qu'il a fallu pour le mettre au micro-ondes et le sortir du micro-ondes. Le reste de votre temps, vous avez toujours regardé l'émission télévisée. Donc, si la tarte a mis 10 minutes à cuire au lieu d'une minute, elle n'a en fait plus utilisé votre temps à regarder la télévision.

En pratique, si vous voulez arriver au niveau de vous soucier de la différence entre Multiply et Divide, vous devez comprendre les pipelines, le cache, les blocages de branche, la prédiction dans le désordre et les dépendances de pipeline. Si cela ne correspond pas à votre intention d'aller avec cette question, la bonne réponse est d'ignorer la différence entre les deux.

Il y a de nombreuses (nombreuses) années, il était absolument essentiel d'éviter les divisions et d'utiliser toujours les multiplications, mais à l'époque, les coups de mémoire étaient moins pertinents et les fractures étaient bien pires. Ces jours-ci, j'évalue la lisibilité plus haut, mais s'il n'y a pas de différence de lisibilité, je pense que c'est une bonne habitude d'opter pour des multiplications.

Écrivez celui qui indique le plus clairement votre intention.

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

Ne faites pas l'inverse.

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

Laissez le compilateur faire les performances pour vous.

Si vous travaillez avec des entiers ou des types non flottants, n'oubliez pas vos opérateurs de décalage de bits: << >>

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

En fait, il y a une bonne raison qu'en règle générale, la multiplication sera 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 conditionnelle ("division longue" avec des nombres binaires) ou - plus probablement de nos jours - avec des itérations comme l' algorithme de Goldschmidt . Le décalage et la soustraction 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'addition de 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 prendra plus de cycles. Bien sûr, cela ne tient pas compte des bizarreries des compilateurs, du mouvement des données ou de la précision. En gros, cependant, si vous codez une boucle interne dans une partie sensible au temps d'un programme, écrire 0.5 * xou 1.0/2.0 * xplutôt que x / 2.0c'est une chose raisonnable à faire. Le pédantisme du "code ce qui est le plus clair" est absolument vrai, mais tous les trois sont si proches en lisibilité que le pédantisme est dans ce cas juste pédant.

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

La multiplication est généralement plus rapide - certainement jamais plus lente. Cependant, s'il n'est pas critique pour la vitesse, écrivez ce qui est le plus clair.

La division en virgule flottante est (généralement) particulièrement lente, donc si 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 n'ait montré que la division est un peu un goulot d'étranglement par rapport à la multiplication. J'imagine, cependant, que le choix de la multiplication par rapport à la division n'aura pas un impact important sur les performances de votre application.

Cela devient plus une question lorsque vous programmez en assemblage ou peut-être en C. Je suppose 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 préférable, alors j'essaie de m'en tenir à cela lorsque je code",

Dans le contexte de cette question spécifique, mieux signifie ici «plus vite». Ce qui n'est pas très utile.

Penser à la vitesse peut être une grave erreur. Il y a de profondes implications d'erreur dans la forme algébrique spécifique du calcul.

Voir Arithmétique à virgule flottante avec analyse d'erreur . Voir Problèmes de base dans l'arithmétique à virgule flottante et l'analyse des erreurs .

Alors que certaines valeurs à virgule flottante sont exactes, la plupart des valeurs à virgule flottante sont une approximation; ce 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 viennent d'essayer de manipuler deux nombres presque égaux. Les bits les plus à droite (les bits d'erreur) en viennent à dominer les résultats.

>>> for i in range(7):
...     a=1/(10.0**i)
...     b=(1/10.0)**i
...     print i, a, b, a-b
... 
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 différents de zéro où la réponse correcte est zéro.

J'ai lu quelque part que la multiplication est plus efficace en C / C ++; Aucune idée concernant les langues interprétées - 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, restez fidèle à ce qui est plus maintenable / lisible - je déteste quand les gens me disent cela, mais c'est tellement vrai.

Je suggérerais la multiplication en général, car vous n'avez pas à passer les cycles à vous assurer que votre diviseur n'est pas 0. Cela ne s'applique pas, bien sûr, 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 articles # 24 (la multiplication est plus rapide) et # 30 - mais parfois ils sont tous les deux tout aussi faciles à comprendre:

1*1e-6F;

1/1e6F;

~ Je les trouve tous les deux tout aussi 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 elle dépend du compilateur. Au début, sur vs2003 (c ++), je n'ai eu aucune différence significative pour les types doubles (virgule flottante 64 bits). Cependant, en exécutant à nouveau les tests sur vs2010, j'ai détecté une énorme différence, 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, par rapport à 2003:

• Multiplication: 8,09
• Division: 7,97

Sur un Xeon W3530, par rapport à 2003:

• 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 car il y a un résultat 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 que cela dépend du nombre.

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

Voici une réponse idiote et amusante:

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 à travers votre application. Vous le changez donc et bénéficiez d'une amélioration remarquable des performances de 5%.

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

Était-ce la bonne décision de changer le code? En maths, les deux expressions sont en effet équivalentes. En informatique, cela n'est pas toujours vrai. Veuillez lire Minimiser 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 cas extrêmes. Par exemple:

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

L'essentiel est; une fois que vous vous êtes contenté de l'un des deux, respectez-le!

Eh bien, si nous supposons qu'une opération d'ajout / sous-piste coûte 1, multipliez les coûts par 5 et divisez les coûts par 20.

Après une discussion aussi longue et intéressante, voici mon point de vue sur ceci: Il n'y a pas de réponse définitive à cette question. Comme certains l'ont souligné, cela dépend à la fois du matériel (cf. piotrk et gast128 ) et du compilateur (cf. les tests de @Javier ). Si la vitesse n'est pas critique, si votre application n'a pas besoin de traiter en temps réel une énorme quantité de données, vous pouvez opter pour la clarté en utilisant une division, alors que si la vitesse de traitement ou la charge du processeur sont un problème, la multiplication peut être la plus sûre. Enfin, à moins que vous ne sachiez exactement sur quelle plateforme votre application sera déployée, le benchmark n'a pas de sens. Et pour la clarté du code, un seul commentaire ferait l'affaire!

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

La «division» - disons-nous qu'elle existe pendant une seconde - est toujours plus difficile que la multiplication parce que pour «diviser» xpar yun il faut d'abord calculer la valeur y^{-1}telle que y*y^{-1} = 1puis faire la multiplication x*y^{-1}. Si vous le savez déjà, ne y^{-1}pas le calculer à partir de ydoit être une optimisation.