Version imprimable
Bonjour :D,
Est ce que vous connaissez des (méthodes, tutoriels....) pour comprendre pourquoi le temps d'exécution des fonctions mathématique par exempleest plus long que celui deCitation:
exp(x+1)
qui est plus long queCitation:
racine(x+1)/42
j'ai fais le test avec des données de tailles 4 MOCitation:
1/(x^2+1)
:?
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 :
la machine va réaliser "x" multiplication de e si x est entierCode:exp(x+1)
Pour la racine carré, c'est un algorithme plus complexe qui est utilisé. Petite recherche sur google pour avoir des exemplesCode:racine(x+1)/42
enfin :
est plus simple que les autres car :Code:1/(x^2+1)
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...
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é.Citation:
Est ce que vous connaissez des (méthodes, tutoriels....) pour comprendre pourquoi le temps d'exécution des fonctions mathématique par exemple
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.
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).
Désolé de te contredire, mais on utilise le plus souvent des polynômes orthogonaux (Legendre, Tchébyscheff, Laguerre ou Hermite)Citation:
toujours calculée comme série de Taylor approchée
Jean-Marc
Citation:
Envoyé par FR119492
ok pas de problème ;)
c'était juste pour dire que les algos ne sont pas directs, et que ça "coûte"...
:D
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)Citation:
Envoyé par JeromeBcx
Sinon pour le reste de ce qui a été dit, je suis d'accord :)
une petite précision, Jean-Marc :Citation:
Envoyé par FR119492
j'étais quand même pas si hors-sujet que ça :P
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é :D
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
:D
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).Citation:
Envoyé par souviron34
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).
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 :cry:
(d'ailleurs, les séries de Taylor c'est pas pour les divisions ??)
Autant pour moi...Citation:
Envoyé par alex_pi
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