fonction exp

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

Rien ne sera plus rapide que des valeurs pré-enregistrées...

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...

---

3ème année en ecole d'ingé d'info cherche stage de 4 mois à partir du 01/04/08

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 !