Racine carrée pour 0<=x<=1; - Page 1

Bon si vous voulez une suite pour la calculer rapidement:
P0(x)=0;
2P(n+1)(x)=x+2*p(n)(x)-p^2(n)(x);
(Pn) converge uniformement vers x^(1/2).

Voila si ca vous interesse

Mais l'algo de Newton est meilleur.....

Si on appelle e(n) = Pn(x)-x^(1/2) l'erreur au rang n, on a :

2(e(n+1)+sqrt(x)) = x + 2(e(n)+sqrt(x)) - (e(n)+sqrt(x))^2
2e(n+1) + 2sqrt(x) = x + 2e(n) + 2sqrt(x) - e(n)^2 - 2e(n)sqrt(x) - x
2e(n+1) = 2e(n) - e(n)^2 - 2e(n)sqrt(x)

=> e(n+1) = (1-sqrt(x))*e(n) - 1/2*e(n)^2

Comme e(n)->0, on a e(n+1) ~ (1-sqrt(x))*e(n)
Donc e(n) ~ (1-x^(1/2)) ^ n
convergence géométrique, meilleure quand x est proche de 1, et mauvaise quand x est proche de 0... (L'algo de Newton donne une convergence quadratique)

Le but c'est de mettre les algorithmes de maths qu'on a vu en cours ici?
Moi je peux vous donner l'algorithme d'exponentiation rapide, si vous voulez.
Ca serait sympa que tout le monde mettent des algos. Enfin que la partie algo serve à quelque chose quoi!

telchar : c'est quoi une convergence quadratique ?

le nombre de décimales justes double à chaque étape... (ou bien : l'erreur est du genre epsilon^(2^n) )

Thanks

Vous auriez pas des algos pour calculer les (a)cos, (a)sin, (a)tan, , exp et ln ?

si x vaut 0
retourne 0
sinon
retourne sinus(x)
finsi

Bah ca fait déjà une étape qui marche ;D

bein pour calculer exponentiel:
(+x/n)^n converge uniformement vers exp

1/k! aussi si vous on veut un truc plus long !

VOus auriez pas plutot des polygones / fractions rationnelles pour les evaluer sur des intervalles. Parce que les series, bof. La difference n'est pas repartie de facon homogene.

Pour x petit, il y a une très bonne approximation de exp (en o(x^3)) par une fonction du type x->(ax+b)/(cx+d).
Je sais plus les coefficients, mais je crois que c un truc genre approximation de Badé, Badet, comme ça...

=> http://www.google.com

Oué oué. Merci.

pour l'exp, je crois que c pas possible avec des polygones (enfin, mon niveau en maths laisse à désiré )

Tu peux aussi utiliser des procédés de résolution numérique d'équations différentielles pour calculer e^x. Si tu en cherches un: L'algorithme Runge-Kutta est décrit dans le manuel de TI.

Il me semble que ca ne sera pas des plus rapides .... et il m'a semblé que pphd désorais un algo assez rapide

PpHd, essaie quand même les séries : je n'ai rien trouvé de plus rapide et c'est déjà pas mal.
J'ai une moyenne de 1036 cycles pour un cos/sin sur 16 bits.

Je prefere utiliser les fractions rationnelles. A degre egal on obtient une approximation de bien meilleure qualite qu'avec les polygones (du a la presence des poles et pas que de zeros). J'ai trouve un algo pour calculer une approximation rationnelle d'une fonction (par intervalle). Reste a savoir si c'est correct.

Pour atn, j'utilise un développement en fraction continue qui converge assez vite...
Ordre 1 : atn(x) = x
Ordre 3 : atn(x) = 3x/(3+x^2)
Ordre 5 : atn(x) = x(15+4x^2)/(15+9x^2)
Ordre 7 : atn(x) = x(105+55x^2)/(105+90x^2+9x^4)
Ordre 9 : atn(x) = x(945+735x^2+64x^4)/(945+1050x^2+225x^4)
Réduire l'intervalle de calcul en utilisant :
atn(x) = PI/4 - atn(1/x) permet de réduire l'intervalle de 0..1
atn(x) = atn(k) + atn((x-k)/(1+kx))
Par exemple pour une précision de 16bits, prendre ordre 3, k = 1/4, 1/2, ou 3/4

Pour le log, les fractions continue tronquées marches bien, aussi (convergence plus rapide que dev de ln(1+x))
(Voir une revue disparue, je crois "Computer Langage" années 86-95)

Pour sin et cos, il y a des polynomes qui marchent bien (voir -ancienne- note d'application DSP ADSP2100 Analog Device)

Pour sin cos atn exp ln sh... on peut aussi utiliser CORDIC

Kevin Kofler a écrit :
Tu peux aussi utiliser des procédés de résolution numérique d'équations différentielles pour calculer e^x. Si tu en cherches un: L'algorithme Runge-Kutta est décrit dans le manuel de TI.

manuel de TI, tu plaisantes, t'as vu celui de la v200!
d'ailleurs, vous sauriez pas ou je peux trouver tout le manuel ti en un seul bloc en pdf

Oui, sur le site de Texas Iinstruments ! Ça fait 50 fois qu'on le dit

y333 : il parlait du manuel complet, pas du truc livré avec les TI.

Ben le manuel complet est sur le site de TI, non ?

/me parlait de Kevin, pas de toi

Kevin Kofler a écrit :
Tu peux aussi utiliser des procédés de résolution numérique d'équations différentielles pour calculer e^x. Si tu en cherches un: L'algorithme Runge-Kutta est décrit dans le manuel de TI.

exact, et cet algo a fait l'objet d'un TIPE dans ma classe cette année

au fait, si quelqu'un a un truc mieux que ca pour calculer 1.0f / sqrtf(n) je suis preneur

float                   rsqrt(float n)
{
  long                  i;
  float                 y;
  register float        x2;
  register float        halfs;
[b][/b]
  halfs = 1.5f;
  x2 = n * 0.5f;
  y  = n;
  i  = *(long*) &y;
  i  = 0x5f3759df - (i >> 1);
  y  = *(float*) &i;
  y  = y * (halfs - (x2 * y * y));
  y  = y * (halfs - (x2 * y * y)); /* this iteration is only needed on alphas, precision on sparcs and i386 are ok with two iterations */
  return (y);
}