Discussion :

[pipip]

Bonjour ,

Est ce que vous connaissez des (méthodes, tutoriels....) pour comprendre pourquoi le temps d'exécution des fonctions mathématique par exemple

exp(x+1)

est plus long que celui de

racine(x+1)/42

qui est plus long que

1/(x^2+1)

j'ai fais le test avec des données de tailles 4 MO

[JeromeBcx]

Bonjour Pipip,

Je ne répondrai pas précisément à la question sur les fonctions décrites, mais d'un ordre général.

Les processeurs ne sont pas capables de calculer avec leurs opérateurs de bases certaines fonctions, même de base comme la racine carrée d'un nombre.
Il faut s'imaginer que le processeur possède simplement des opérateurs tels que addition/soustraction, multiplication/division, opérateurs logiques, ....

Donc, pour les exemples cités :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

exp(x+1)

la machine va réaliser "x" multiplication de e si x est entier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

racine(x+1)/42

Pour la racine carré, c'est un algorithme plus complexe qui est utilisé. Petite recherche sur google pour avoir des exemples

enfin :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1/(x^2+1)

est plus simple que les autres car :
1 multiplication,
1 addition,
1 division.

De plus, les temps peuvent varier suivant le type de x : entier, entier long, floatant, ....
Et pour compliquer, suivant le langage et même les librairies utilisées, les temps de calculs (liés aux nombres d'opérations et leurs natures) peuvent varier.
On peut également prendre en compte l'architecture du processeur....

En espérant vous avoir mis sur la piste...

[Zavonen]

Est ce que vous connaissez des (méthodes, tutoriels....) pour comprendre pourquoi le temps d'exécution des fonctions mathématique par exemple

La meilleure méthode consiste à prendre un crayon un papier et à se palucher les calculs un à un en mesurant le temps mis avec un chrono. Sûr que si tu fais ça tu vas comprendre, et tu vas apprendre quelque chose par dessus le marché.

[ToTo13]

Bonsoir,

euh... pour l'exponentielle et la racine il me semble que l'ordi utilise des fonctions convergentes qui donnent de bon résultat plus rapidement que ce que l'on nous enseigne en math.

[souviron34]

pas franchement..

La racine carrée est, si ne me trompe, toujours calculée comme série de Taylor approchée... (d'où l'intérêt, lorsqu'on a à comparer des distances, à comparer au carré... Et ne prendre la racine que à la sortie du calcul).

[FR119492]

toujours calculée comme série de Taylor approchée

Désolé de te contredire, mais on utilise le plus souvent des polynômes orthogonaux (Legendre, Tchébyscheff, Laguerre ou Hermite)
Jean-Marc

[souviron34]

Désolé de te contredire, mais on utilise le plus souvent des polynômes orthogonaux (Legendre, Tchébyscheff, Laguerre ou Hermite)
Jean-Marc

ok pas de problème

c'était juste pour dire que les algos ne sont pas directs, et que ça "coûte"...

[alex_pi]

Donc, pour les exemples cités :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

exp(x+1)

la machine va réaliser "x" multiplication de e si x est entier

Puisqu'on est sur forum d'algo, je me permets de souligner que même pour n^p, avec n et p entier, on ne fait pas p - 1 multiplication, mais plus de l'ordre de log(p) (log en base 2)

Sinon pour le reste de ce qui a été dit, je suis d'accord

[souviron34]

Désolé de te contredire, mais on utilise le plus souvent des polynômes orthogonaux (Legendre, Tchébyscheff, Laguerre ou Hermite)
Jean-Marc

une petite précision, Jean-Marc :

j'étais quand même pas si hors-sujet que ça

Mechanical Verification of a Square Root Algorithm using Taylor Theorem

Mes maths sont (très très) loin, mais j'ai quelques.... racines

Un article de 2000 mentionne :

http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf

Et il me semble que j'avais trouvé une petite bibliographie quelque part...


[EDIT]

ça y est.. J'ai retrouvé

Post #13

d'un thread portant le même nom que celui-ci, mais dans le forum Langages Général :
Temps de calcul - Coût d'une opération

[Jean-Marc.Bourguet]

j'étais quand même pas si hors-sujet que ça

Mechanical Verification of a Square Root Algorithm using Taylor Theorem

Où on lit que la technique classique pour les racines carrées est l'utilisation d'une approximation suivie d'une série d'itérations Newton-Raphson. Que pour le POWER4, ils ont remplacé ces itérations par un polynôme de Chebyshev (ils ont utilisé le théorème de Taylor pour prouver que l'approximation était suffisante), peut-être plus coûteux en calcul si on ne fait que compter les opérations mais se prêtant mieux à une exploitation du micro-parallélisme (faire 4 opérations plutôt que 3 peut donner un résultat plus rapidement si on peut les grouper 2 par 2 dans le premier cas).

Un problème des l'utilisation des séries de Taylor est qu'elles ont une erreur qui augmente plus on s'éloigne du point autour duquel le développement est fait. Donc pour un intervalle et un degré donné du polynôme, c'est rarement le polynôme qui offre la meilleur erreur maximale (en fait, on travaille plutôt dans l'autre sens: on cherche dans un intervalle donné le polynôme de degré le plus faible qui a une erreur maximale inférieure à une borne donnée).

[souviron34]

je ne disais pas le contraire

Je parlais du nom...

Pour quelqu'un qui n'a pas touché aux maths de ce style depuis plus de 30 ans, je trouve que j'avais une (assez) bonne mémoire


(d'ailleurs, les séries de Taylor c'est pas pour les divisions ??)

[JeromeBcx]

Puisqu'on est sur forum d'algo, je me permets de souligner que même pour n^p, avec n et p entier, on ne fait pas p - 1 multiplication, mais plus de l'ordre de log(p) (log en base 2)

Sinon pour le reste de ce qui a été dit, je suis d'accord

Autant pour moi...
J'ai répondu un peu trop rapidement pour la fonction "x^y". Il est vrai que l'on peut réaliser le calcul sans faire les p-1 multitplications