Discussion :

[le_voisin]

Bonjour à tous,

je recherche des informations concernant le cout en temps de calcul de divers opérations mathématiques (multipication, division, racine carré, exposant etc...)
Entre autre, y a t il une différence entre calculer une racine carré et mettre au carré une valeur ?

Merci, bonne journée.

[Garulfo]

Le coût réel ?

Très très petit et dépendant d'un paquet de facteurs.

Pour ta deuxième question je suppose que tu parles de différences de temps de calcul ? Il y en a certainement...

[souviron34]

Bonjour à tous,

je recherche des informations concernant le cout en temps de calcul de divers opérations mathématiques (multipication, division, racine carré, exposant etc...)
Entre autre, y a t il une différence entre calculer une racine carré et mettre au carré une valeur ?

Merci, bonne journée.

il me semble (mais mes souvenirs sont lointains et vagues), qu'une racine se calcule par série, alors qu'une multiplication est directe...

donc normalement T racine >> T carré

Si c'est pour une optimisation cependant, c'est du cas par cas, car en général c'est l'algo qu'il faut optimiser, pas les opérations.

La seule est effectivement la racine, lors d'un calcul de distance. Dans ce cas (par exemple calcul d'une distance min ou max), il est inutile de calculer la racine sauf au dernier stade... Cela consomme du temps inutile, et les comparaisons entre les carrés sont identiques aux comparaisons entre les racines...

[Scyrius]

Hello,

Les operation de base ( +,-, *) sont extrement rapides car integrée au processeur.
La division aussi mais elle se fait en plusieurs etapes.

Quand aux operations mathematiques, celles qui dependent des operations ci dessus sont rapides ( le carré)
Celles qui dependent d'un algorithme sont plus lentes, mais s'il y a maintenant des algos rapides

Derniers points aussi tres importants: le type des variables: il y a une enorme difference si tu travaille avec un octet ou si tu travaille avec des doubles. Il y a aussi la precision du resultat ( je parle de calcul type racine) qui peut augmenter le temps.

Si tu veux tester, prends un compilo, boucle 100 000 fois une operation et tu aura un ordre d'idée.

[le_voisin]

ok merci pour ces quelques elements de reponse.

Ou est ce que je pourrais avoir des infos sur l'optimisation d'algorithmes ?

Merci, bonne journée.

[souviron34]

pas de méthodes toutes faites..

• a) faut savoir le but global
• b) réfléchir à quelle serait la manière la plus efficace de l'atteindre
• c) le programmer
• d) éventuellement optimiser la programmation

mais les parties essentielles sont a et b...

Tu peux éventuellement poser ton problème sur le forum algorithmes , on verra...

[GnuVince]

Utilise un profiler, ça va te donner ta réponse. Par exemple, en Python:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> import timeit

>>> t1 = timeit.Timer(stmt='10**2')

>>> t2 = timeit.Timer(stmt='math.sqrt(10)', setup='import math')

>>> t1.timeit(1000000)
0.25965595245361328

>>> t2.timeit(1000000)
0.66619300842285156

>>>

Pour faire un million de 10**2, Python prend un quart de seconde sur ma machine et pour faire un million de math.sqrt(10), il prend deux tiers de seconde.

[corrector]

il me semble (mais mes souvenirs sont lointains et vagues), qu'une racine se calcule par série, alors qu'une multiplication est directe...

Tu veux dire que la racine carré est approchée par une série entière?

[souviron34]

Série de Taylor, si mes souvenirs sont bons (mais d'une part ils sont lointains en info. de ce style, les compilos et les algos ont certainement changé, et ils sont encore plus lointains en maths..)

[corrector]

Il y a une différence fondamentale?

Le calcul se fait à quel ordre?

(Je trouve ça extrêmement générique comme méthode, pour une fonction réciproque.)

[millie]

Série de Taylor, si mes souvenirs sont bons (mais d'une part ils sont lointains en info. de ce style, les compilos et les algos ont certainement changé, et ils sont encore plus lointains en maths..)

C'est plutôt la méthode de newton (éventuellement couplée avec des valeurs précalculées) ? Ca converge plus vite qu'une série entière (classique de taylor) pour la racine carré.

Il doit y avoir des méthodes plus récentes et plus rapides

[souviron34]

visiblement, apres une recherche rapide sur Google ("algorithm square root processor") il y a encore beaucoup de recherches dessus, car on est loin encore d'avoir une "bonne" solution (c'est une des operations "simples" les plus longes).

Un exemple est :
http://www.ecs.umass.edu/ece/arith14/program.html
(1999)

ou

http://www3.interscience.wiley.com/c...TRY=1&SRETRY=0
(2007)

Sinon un bref resume (je ne connais pas la date) est ici :
http://www.dattalo.com/technical/theory/sqrt.html

de ce style (sur des PIC)

http://www.dattalo.com/technical/sof...c/picsqrt.html

24 words long (It turns out it was actually 28 words)
requires only 4 bytes of RAM - Including the 2 for the 16 bit input
Executes in 95 cycles

28 bytes long
requires only 4 bytes of RAM - Including the 2 for the 16 bit input
Executes in about 145 cycles

30 bytes long
requires only 3 bytes of RAM - Including the 2 for the 16 bit input ( a savings of one byte)
Executes in 104 cycles best case, 109 average, 122 worst case.