Multiplication ? - Page 1

g une question conne : est-ce que ça va plus vite (en C) de faire une multiplication ou de faire une boucle d'additions ?

Les boucles ne seront jamais plus rapides, par contre les suites le peuvent. Tout dépend :
1- des facteurs,
2- du fait que l'un soit constant ou non

par exemple on a ça : x*10
ds ce cas c plus rapide de faire une boucle ?

Dans ton cas, cette suite d'additions est en effet beaucoup plus rapide qu'une multiplication :

resultat= x + x;
resultat+= resultat << 2;

dc en fait là c comme si on faisait res=2*x + 8*x ?
le but est dc d'utiliser des puissances de 2 ?

bah oué .... c plus rapide

Tout à fait, on exploite les particularités de la base binaire :

On t'a appris en primaire que pour multiplier par 10 un nombre décimal (c'est à dire exprimé en base 10), on ajoute un zéro.
Eh bien en binaire, pour multiplier par 2, on fait pareil, on ajoute un zéro, ce qui revient à décaler le nombre vers la gauche dans le registre

yeah !
et pour les divisions ça donnerait quoi ? (si c possible)

J'avais fais un topic une fois dans cette section du forum où je donnais ma modeste opinion : pour moi l'opération "naturelle" est l'addition (et peut-être la soustraction), les autres sont des algorithmes basés sur cette opération.

La multiplication est une succession d'additions, ça c'est un algorithme simple.

La division c'est autre chose, l'algo est beaucoup plus complexe, et il y a seulement de très rares cas où l'on peut la résumer à quelques opérations, la plupart du temps muls et mulu sont plus rapides.

Pour diviser par 10 :
resultat= (x*6554) >> 16;

oué
on va laisser tomber pour la division alors

bah c'est simple, ça tient en une ligne là
Tu veux diviser par un nombre particulier ?

le multiplication par 6554 ralentit pas mal qd même, non ?
(faut qd même pas la passer en linéaire elle aussi ?)

oué Vark, sert toi des décallage de bits le plus souvent possible ! donc essais de diviser (>> ) ou multiplier (<< ) par des décallages de bits, qui seront bcp + rapides que "*" ou "/" !

juste pour que tu vois (peut-être tu connais déjà ces règles) :

int x;

x << n équivaut à x * 2^n

x >> n équivaut à x / 2^n

je connais, c ce que g utilisé pour mon moteur 3D (mé ça m'est pas venu à l'idée de les utiliser pour accélérer n'importe qu'elle multiplication )

Vark : la multiplication ralenti, mais il faut savoir que sur le MC68000 la multiplication est 2-3 fois plus rapide que la division ! donc la formule (x*6554) >> 16 est quand même 2-3 fois plus rapide que x/10

Il n'y a pas moyen de calculer rapidement x*6554 avec une suite d'additions/décalages

là g pas trop envie de réfléchir : comment on fait pour trouver les 2 nbres k et z tq x/n <=> (x*k)>>z

D'où vient la formule ? Et bien c'est tout con, tu le sais depuis la 5ème :

 x           1
---  =  x · ---
 n           n

Donc pour diviser x par 10 :

  x            1           6553.6            6554           6554
----  =  x · ----  =  x · --------  ~  x · -------  =  x · ------
 10           10           65536            65536           2^16

J'ai bien dit que les cas optimisables sont très rares, car pour que (x * k) / z soit plus rapide que x/n, z doit être une puissance de 2. Quand on a trouvé un z, il ne reste plus qu'a trouver k

ok

Thibaut> Vark : la multiplication ralenti, mais il faut savoir que sur le MC68000 la multiplication est 2-3 fois plus rapide que la division ! donc la formule (x*6554) >> 16 est quand même 2-3 fois plus rapide que x/10

pas tout a fait d'accord... la muls prend MAXIMUM 70 cycles, la divs MAXIMUM 140 cycles (pa sur, je dis ca de tete, je pe me tromper..)
si tu divise ou multiplie par 10 ca prendra beaucoup moins que 140 ou 70 cycles... et ca ne sera PAS 2 a 3 fois plus rapide en rajoutant un decalage de 16 (a moins de faire un swap, ms la c plus un decalage )

je n'ai plus en tete la formule pour calculer le nombre de cycles pris par une muls ou une divs, dc dur a comparer pour une mul/div par 10, mais ca vaut pa franchement le coup d'optimiser ca a mon avis.. a moins ke ca soit dans une routine critique
la formule pour trouver le nombre de cycles est assez tordue, et elle est en fct du nombres de bits a 1 du multiplicateur, un truc comme ca...

Non sBibi,

1- dans le meilleur des cas divs nécessite 128 cycles.
2- c'est bien environ 2 fois (le 3 fois était exagéré : je ne savais plus si c'était 40 ch ou 70 ch pour muls) car le compilateur est assez intelligent pour remplacer le décalage de 16 par un swap quand le résultat est demandé sur un short.


Alors entre 74 cycles et 128-140 cycles, y'a pas photo la technique que j'ai donnée à Vark est bien plus rapide.

=======================================================

Sinon, j'ai dit une bêtise à propos de la formule. On peut diviser par n'importe quel nombre avec ! mais la précision du résultat est très variable suivant le nombre par lequel on divise. Pour 10 c'est assez imprécis par exemple, mais pour 17 c'est excellent

Thibaut> erf, c vrai ke vous parlez en C... bah ok, mettons que le compilo remplace le >>16 par un swap...
alors deja, d'une: kan on voit la gueule des .s gerbes par tigcc, ca me donne envi de faire pareil..
(petite pique, fermons la parenthese )

et ensuite ca metonne BCP que dans le MEILLEUR DES CAS, muls prenne 74 cycles, et divs 155 !!
mais alors la, BEAUCOUP...

tu en est sur? sur a 100%?

Bon déjà, c'est pas 74 cycles pour muls mais 70 ! 74 c'est le muls + swap

Ensuite, tant mieux si dans le meilleur des cas muls prend moins de 70 cycles (70 étant le pire) : la méthode "multiplication+swap" est encore plus rapide

Pour divs tu as raison, je me suis trompé, il demande 128 cycles minimum.

Et surtout arrête de prétendre vouloir mieux savoir que les grands de la communauté : la méthode "multiplication+swap" n'est pas de moi mais de PpHd.

Cf topics/14493-vitesse-de-mulu-info-sur-divu

Thibaut> LOL j'ai jamais pretendu ca

et j'ai dit 74 cycles, tt simplement pke ct la valeur ke t'av mise, et que n'ayant pas de table de cycles sous les yeux, je ne peux pas verifier, dc je pensais m'etre trompe kan g mis 70 cycles au post d'au dessus

Thibaut a écrit :
J'avais fais un topic une fois dans cette section du forum où je donnais ma modeste opinion : pour moi l'opération "naturelle" est l'addition (et peut-être la soustraction), les autres sont des algorithmes basés sur cette opération.

Les fonctions transcendentales tu expliquais ça comment déjà

J'en sais rien, je ne pige pas de quoi tu parles. Et tu le sais en plus que je ne connais pas ce mot. Explique

Hum ok... les fonctions transcendantales c'est les fonctions trigo, ln, etc.. Non je demandais parce que si tu avais trouvé ça, tu aurais révolutionné toute l'analyse numérique quand même

lol c'est juste une supposition faite sur mes connaissances actuelles

Le calcul d'un cosinus, c'est un simple algorithme utilisant des divisions, des additions, etc... donc mon hypothèse reste valable !

Oui, mais pour calculer la valuer exacte du cosinus, tu dois faire une infinité d'opérations élémentaires (+, -, ×, ÷)!

Bah oué ben si on n'a pas trouvé d'autre méthode plus précise n'utilisant pas de calculs "de base" j'y peux rien !