Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Re: algorithme de la fonction pow

61 views
Skip to first unread message

Olivier Miakinen

unread,
Sep 13, 2011, 5:30:01 AM9/13/11
to
[Copie et suivi vers fr.comp.algorithmes]

Le 13/09/2011 10:24, Etienne a écrit dans fr.sci.maths :
>
> est ce que quelqu'un saurait il quel est l'algorithme utilisé pour
> implémenter la fonction pow !

Dans quelle implémentation sur quelle machine ? Sans cette précision,
je ne vois pas bien qui pourrait deviner de quel algorithme il s'agit
exactement !

À tout hasard, un algorithme est exposé ici pour le calcul de
l'exponentielle (paragraphe 6.3) et du logarithme (6.4) :
<http://hal.inria.fr/inria-00071477/PDF/>.

Sachant que a^b = exp(b.ln(a)), tu as tout ce qu'il te faut.

Je fais suivre la discussion vers fr.comp.algorithmes qui me semble
plus adapté.

Cordialement,
--
Olivier Miakinen

Etienne

unread,
Sep 13, 2011, 8:53:26 AM9/13/11
to
Le 13/09/2011 11:30, Olivier Miakinen a écrit :
> [Copie et suivi vers fr.comp.algorithmes]
>
> Le 13/09/2011 10:24, Etienne a écrit dans fr.sci.maths :
>>
>> est ce que quelqu'un saurait il quel est l'algorithme utilisé pour
>> implémenter la fonction pow !
>
> Dans quelle implémentation sur quelle machine ? Sans cette précision,
> je ne vois pas bien qui pourrait deviner de quel algorithme il s'agit
> exactement !
>
> Sachant que a^b = exp(b.ln(a)), tu as tout ce qu'il te faut.
>
> Cordialement,

Ok.
bon, en fait je cherche a porter ça en assembleur.
J'ai accès aux opérations "cablées" suivantes:
- division, multiplication, addition, soustraction et racine carré.
- et j'ai trouvé les algorithmes pour le sinus et le cosinus.

Donc a^b = exp(b.ln(a)) c'est bien mais du coup ça soulève deux questions:

comment implémente t-on l'exponentiel et le logarithme.

Le but ultime étant la résolution d'une équation du 3émé degré qui
nécessites des racines cubiques.

Etienne

Ps: Olivier, j'ai rien compris au pdf que tu m'as filé ;)

Pascal J. Bourguignon

unread,
Sep 13, 2011, 9:34:15 AM9/13/11
to
Etienne <eti...@tlk.fr> writes:
> comment implémente t-on l'exponentiel et le logarithme.

Si tu es perdu sur une planète déserte, tu utilises les séries de
Taylor. Par exemple,

e^x = 1 + x^1/1! + x^2/2! + x^3/3! ...

Donc un algorithme simple et naïf pour calculer e^x est:

(defparameter *precision* 1e-6)

(defun taylor-exp (x)
(loop
for n from 1
for n! = 1 then (* n n!)
for x^n = x then (* x x^n)
for e = 1 then new-e
for new-e = (+ e (/ x^n n!))
until (< (abs (- e new-e)) *precision*)
finally (return new-e)))

(list (taylor-exp 3.0) (exp 3.0))
--> (20.085539 20.085537)


Sinon tu utilises Google (par exemple: exponential numerical algorithm),
ce qui te donnera en général un meilleur algorithme, mais plus compliqué
à implémenter.

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

Pascal J. Bourguignon

unread,
Sep 13, 2011, 9:35:04 AM9/13/11
to
Etienne <eti...@tlk.fr> writes:

> comment implémente t-on l'exponentiel et le logarithme.

Il y a aussi une troisième solution, qui consiste à récupérer les
bibliothèques numériques fournies par le fabriquant du processeur en
question...

Paul Gaborit

unread,
Sep 13, 2011, 11:25:18 AM9/13/11
to

À (at) Tue, 13 Sep 2011 15:34:15 +0200,
"Pascal J. Bourguignon" <p...@informatimago.com> écrivait (wrote):

> Etienne <eti...@tlk.fr> writes:
>> comment implémente t-on l'exponentiel et le logarithme.
>
> Si tu es perdu sur une planète déserte, tu utilises les séries de
> Taylor. Par exemple,
>
> e^x = 1 + x^1/1! + x^2/2! + x^3/3! ...
>
> Donc un algorithme simple et naïf pour calculer e^x est:
>
> (defparameter *precision* 1e-6)
>
> (defun taylor-exp (x)
> (loop
> for n from 1
> for n! = 1 then (* n n!)
> for x^n = x then (* x x^n)
> for e = 1 then new-e
> for new-e = (+ e (/ x^n n!))
> until (< (abs (- e new-e)) *precision*)
> finally (return new-e)))
>
> (list (taylor-exp 3.0) (exp 3.0))
> --> (20.085539 20.085537)
>
>
> Sinon tu utilises Google (par exemple: exponential numerical algorithm),
> ce qui te donnera en général un meilleur algorithme, mais plus compliqué
> à implémenter.

Pour résoudre une équation du troisième degré (ou le cas particulier
d'une racine cubique), une bonne vieille méthode de Newton-Raphson me
semble tout à fait adaptée (plus rapide et plus précise).

--
Paul Gaborit - <http://perso.mines-albi.fr/~gaborit/>

Etienne

unread,
Sep 14, 2011, 3:14:33 AM9/14/11
to
Le 13/09/2011 17:25, Paul Gaborit a �crit :
>> Si tu es perdu sur une plan�te d�serte, tu utilises les s�ries de

>> Taylor. Par exemple,
>>
>> e^x = 1 + x^1/1! + x^2/2! + x^3/3! ...
>>
> Pour r�soudre une �quation du troisi�me degr� (ou le cas particulier
> d'une racine cubique), une bonne vieille m�thode de Newton-Raphson me
> semble tout � fait adapt�e (plus rapide et plus pr�cise).

Merci pour votre aide. J'ai fini par trouver une lib qui a impl�ment�
toutes les fonction voulues en assembleur pour le processeur concern�.

http://code.google.com/p/math-neon/source/browse/#svn%2Ftrunk

bon faudrait que j'arrive a comprendre et voir si c'est assez pr�cis
pour ce dont j'ai besoin.

Etienne.

0 new messages