Fonction exp

Signaler
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011
-
jul39dole
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011
-
Bonjour,
Afin d'optimiser mon code, je me demandais comment était implémentée la fonction exp(x) en c++ (compilation sous visual par exemple). Selon la manière dont c'est implémenté, j'utiliserai soit la fonction exp, soit un tableau que je remplirai à l'avance avec les diférentes valeurs (exp de 0, 0.1, 0.2...). La précision et la mémoire utilisée n'est pas un problème dans mon cas, il me faut surtout de la rapidité...

Merci d'avance.

Ju

3 réponses

Messages postés
966
Date d'inscription
samedi 3 avril 2004
Statut
Membre
Dernière intervention
4 mars 2010
4
Rien ne sera plus rapide que des valeurs pré-enregistrées...
Messages postés
3874
Date d'inscription
mardi 8 mars 2005
Statut
Modérateur
Dernière intervention
7 novembre 2014
10
Salut,


Quand on veut connaître l'implémentation en détail d'une fonction et
que l'on a du temps devant soit, il suffit de tracer dedans pour savoir
ce qu'elle a dans le ventre.


Pour ça, sous VC2005, on va utiliser le "pas à pas détailler".


Manque de chance, ça ne marche pas pour exp (Du moins dans les conditions où j'ai fait mon test).


Il reste donc plus qu'à afficher l'assembleur (Déboguer->Fenêtres->Code Machine).


On peut là aussi utiliser le pas à pas détailler pour suivre l'execution instruction par instruction.


Dans le cas de exp, l'assembleur fait appel à des fonctionnalités avancés du processeur : il ne se contente pas de la CPU.


Mais même en ne connaissant pas grand chose à l'assembleur, on peut constater au moins deux choses :


1 Le code qui est executé dépend du processeur. On remarque en effet un
test sur la variable ___use_sse2_mathfcns. sse est une extension de
processeur qui ajoute des registres (xmm) et des instructions
supplémentaires au processeurs. Il y a plusieurs versions : sse, sse2,
sse3... On peut remarquer que cette variable est manifestement affectée
avant l'appel de la fonction exp et est donc certainement initialisée
lors de l'initialisation de la runtime C (Mouarf ! Je dis rien mais
j'en pense pas moins !) Donc si sse2 est présente sur le processeur, un
code est executé, sinon, s'en est un autre.


2 Dans mon cas, environs 70 instructions processeurs amènent au
résultat. Et pas des instructions légères puisque certaines font appel
aux registres xmm cité plus haut. Dans le cas d'un accès dans un
tableau, on tombe plutôt sur deux ou trois instructions.


Faut pas généraliser le cas de l'exponentiel à d'autres fonctions
mathématiques : le processeur est probablement plus à l'aise avec les
sinus et autre arctangente, car il a les instructions pour.


Je vais pas détailler la méthode de calcul de VC2005 qui est un peu compliquée à mon gout.


Je vais plutôt étudier celle de Delphi 7 qui utilise systématiquement
la FPU (Une autre extension processeur, mais plus ancienne que les sse).


Avant l'appel de la fonction, l'appelant pousse l'argument sur la pile de la FPU avec fld. Voici la fonction Exp de ma Delphi :


fldl2e

fmulp st(1)

fld st(0)

frndint

fsub st(1)

fxch st(1)

f2xm1

fld1

faddp st(1)

fscale

fstp st(1)

ret


La FPU utilise une pile... de registres (Sommet st(0), puis st(1)...). Je sais pas si on peut la visualiser sous VC2005.


Calcul de Exp(2) :


fldl2e pousse log2(e) sur la pile.

log2(e) ln(e) / ln(2) ln(Exp(1)) / ln(2) = 1 / ln(2) = 1.4426...


fmulp st(1) multiplie log2(e) avec notre argument et pop un coup.

On a donc 2 / ln(2) dans st(0) = 2.8853...


fld st(0) empile une copie du résultat.

frndint arrondit st(0) = 3


fsub st(1) on soustrait les deux registres, et on met le total dans st(1).

2.8853... - 3 = -0.1146...

fxch st(1) échange st(0) et st(1)

st (0) = -0.1146...

st (1) = 3


f2xm1 calcul 2 ^ x - 1 de st (0)

fld1 et faddp st(1) ajoute 1 à st(0)

On a donc mis 2 ^ st(0) dans st(0) 2 ^ -0.1146... 0.9236...


fscale ajoute st(1) à l'exposant de st(0).

st(0) st(0) * 2 ^ st(1) 0.9236... * 2 ^ 3 = 7.3890...


fstp st(1) pop st(0) dans st(1).

On se débarrasse de st(1).


Et bizarrement, il se trouve que 7.3890..., c'est l'exponentielle de 2.


On résume :


résultat = 2 ^ (arg / ln(2) - round(arg / ln(2))) * 2 ^ (round(arg / ln(2)))

         = 2 ^ (arg / ln(2))

         = 2 ^ (ln(e ^ arg) / ln(2))

         = 2 ^ ((log2(e ^ arg) * ln(2)) / (log2(2) * ln(2)))

         = 2 ^ (log2(e ^ arg) / log2(2))

         = 2 ^ log2(e ^ arg)

         = e ^ arg


Aïeuh les souvenirs de cours de Maths !

Le calcul se fait en 2 parties dans la FPU (Partie entière/décimale)
car f2xm1 prend un nombre compris entre -1 et 1 en paramètre, et FSCALE
arrondit st(1) s'il ne l'est pas déjà.


Si on en croit la bible/le coran et les idées reçues, le C++ devrait
être plus rapide que ça. Donc c'est quand même du code très précis et
efficace par rapport à ce à quoi on pourrait s'attendre. Evidement,
c'est probablement pas aussi rapide qu'un accès dans un tableau...
<hr size="2" width="100%" />3ème année en ecole d'ingé d'info cherche stage de 4 mois à partir du 01/04/08
Messages postés
117
Date d'inscription
mardi 22 juillet 2003
Statut
Membre
Dernière intervention
21 janvier 2011

hum.. merci pour ta réponse très détaillée rt15! j'essayerai de tracer la fonction exp en assembleur, je n'y avais pas pensé du tout... (ou l'idée m'était peut être venue inconsciemment? mais je crois que le mot "assembleur" a refoulé cette idée définitivement au fin fond de mon inconscient ^^)

en tout cas le calcul m'a l'air assez long finalement, donc comme vous le dites toi et juju12, ça ne sera pas aussi rapide qu'un accès dans un tableau... je vais surement retenir cette méthode.

merci a vous deux !