FaireDesMaths
retour à LaFaq
racine carrée
Newton
extrait de : http://fr.wikipedia.org/wiki/Racine_carr%E9e#Extraction_de_racines_carrées
Un autre algorithme plus couramment utilisé pour approcher √x est basé sur la méthode de Newton et procède de la manière suivante :
1- on place une valeur positive arbitraire dans r (idéalement la plus proche possible de la racine carrée de x)
2- on remplace r par la moyenne de r et de x/r
3- on recommence à l'étape 2
L'algorithme converge de manière quadratique, ce qui signifie que le nombre de chiffres exacts de r double pratiquement à chaque étape.
En C :
float sqrt(float x)
{
if (x==0) return 0;
if (x==1) return 1;
if (x<0) x=-x;
ori=(x+1)/2;
ratio=x/ori;
/*
le principe est d'encadrer la racine entre deux nombres. Ces deux nombres sont obtenus en divisant
x par un premier nombre noté ori (dans notre cas on prends 1). Le ratio ainsi obtenu est forcément
de l'autre côté de la racine. De plus en prenant 1 au départ, on est toujours sur que ori sera
supérieur à la racine et ratio inférieur.
enfin, une fois la racine encadrée, on fait une moyenne entre ces deux valeurs (ce qui nous rapproche
forcément mieux de la racine) et on recommence l'opération. Lorsque la différence entre les valeurs
qui encadrent est inférieur au seuil de précision, on a un résultat satisfaisant.
*/
while(1)
{
if ((ori-ratio) < 0.00001) return ori;
else {ori=(ori+ratio)/2;ratio=x/ori;}
}
A la con
J'ai trouvé une autre méthode. binaire, sans division. (rotations, mais pas divisions décimales à la con :-) ) tirée de http://f-cpu.seul.org/new/manuel_arith.pdf
J'ai pas la justification de la méthode, mais j'ai l'algorithme (accrochez vous quand même :-)
A0 represente la valeur dont on veut extraire la racine. An sera la valeur au cours des itérations. (A1 jusqu'à A8)
R0 represente la valeur de la racine carrée (à la fin bien sur) au début R0=0.
T0 represente la valeur test. Pour 16 bits on part de 0x4000 (en 12 bits on partirai de 0x400 et en 32 de 0x40000000)
faire boucle de n=0
Si An > Rn + Tn
An+1 = An - Rn - Tn
Rn+1 = Tn + ( Rn / 2 )
sinon
An+1 = An
Rn+1 = Rn / 2
Fin Si
Tn+1 = Tn / 4
n = n + 1
jusqu'à ce que Tn = 0
Rn contient alors la racine carrée (partie entière)
An contient le reste du calcul
Vous me croyez pas, a vos crayons, partie entière de Racine de 65432 = ? (pas le droit au multiplications ni au divisions :-) )
en C :
//variable globale :
long A;
//
char racine(void)
{
long T=0x4000;
long R=0;
long TR;
while (T>0)
{
TR=T+R;
if (A >= TR) {A=A-TR;R=R>>1;R=R+T;}
else {R=R>>1;}
T=T>>2;
}
return (R&0xFF); //le résultat est là.
}
Si quelqu'un trouve une justification je prends... parce que là ça me fait mal au bide de voir que ca marche !
Je pense que cela doit être associé à la méthode du compte goutte : http://encyclopedie.izynews.be/fr/lexw.aspx?doc=Technique_de_l'extraction_de_racine
Autre algorithme plus chaud a coder copié de http://encyclopedie.izynews.be/fr/lexw.aspx?doc=Racine_carr%c3%a9e
Nous allons exposer un algorithme qui va nous permettre d'extraire la racine carrée d'un nombre. Évidemment, si la racine carrée n'est pas un nombre décimal , alors l'algorithme ne se termine jamais. Bien que décrite ici pour des nombres écrits en base 10, la procédure fonctionne dans n'importe quelle base, base 2 comprise. Dans ce qui suit, 20 représente le double de la base, et en binaire ce nombre serait remplacé par 100.
Nous commençons par séparer les chiffres du nombre par paires en commençant à partir de la virgule. Nous plaçons le nombre dont on veut extraire la racine à l'écart, de la même façon que lorsque nous effectuons une division classique.
À chaque étape:
- on abaisse la paire de chiffres la plus significative non encore utilisée et on la place au côté d'un reste éventuel
- soit r le résultat intermédiaire de la racine carrée obtenu précédemment (égal à zéro au début). On cherche le plus grand chiffre x tel que le nombre y=(20r + x)x ne dépasse pas la valeur courante. On place ce nouveau chiffre x sur la ligne supérieure au dessus de la paire abaissée
- on soustrait y de la valeur courante pour former un nouveau reste
- si le reste est nul et qu'il n'y a plus de chiffre à abaisser alors l'algorithme se termine sinon on recommence.
Sinus et Cosinus
/**************************************************************************************************/
float sinus(float x)
{
char neg;
/* utilisation du dévellopement limité de sin
sin x = x - x^3/3! + x^5/5! - x^7/7! ...
ce résultat est assez précis pour un angle inférieur à 45°
on pourra utiliser les relations trigo : sin -t=-sint t, sin(pi - t) = sin t , sin t = cos(pi/2 - t)
*/
if (x==0) return 0;
while (x>PI) x=x-PIfois2;
while (x<moinsPI) x=x+PIfois2;
if (x<0) {neg=1; x=-x;} else neg=0; //sin -t=-sint t
if (x>PIsur2) x=PI-x; //sin(pi - t) = sin t
if (x>PIsur4) sum=cos(PIsur2-x); //sin t = cos(pi/2 - t)
else { // calcul dev limité
sum=x;
ori=x*x;
ratio=x*ori;
sum-=ratio/6; //- x^3/3!
ratio=ratio*ori;
sum+=ratio/120; //+ x^5/5!
ratio=ratio*ori;
sum-=ratio/5040; //- x^7/7!
}
if (neg==1) return -sum; else return sum;
}
/**************************************************************************************************/
float cos(float x)
{
/* utilisation du dévellopement limité de sin
cos x = 1 — x^2/2! + x^4/4! — x^6/6! ...
ce résultat est assez précis pour un angle inférieur à 45°
on pourra utiliser les relations trigo : cos –t = cos t, cos t = sin(pi/2 – t), cos(pi – t) = –cos t
*/
char supPI;
if (x==0) return 1;
while (x>PI) x=x-PIfois2;
while (x<moinsPI) x=x+PIfois2;
if (x<0) x=-x; //cos -t = cos t
if (x>PIsur2) {supPI=1;x=PI-x;} else supPI=0; // cos(pi - t) = -cos t
if (x>PIsur4) sum=sinus(PIsur2-x); //cos t = sin(pi/2 - t)
else { // calcul dev limité
sum=1;
ori=x*x;
sum-=ori/2; //- x^2/2!
ratio=ori*ori;
sum+=ratio/24; //+ x^4/4!
ratio=ratio*ori;
sum-=ratio/720; //- x^6/6!
}
if (supPI==1) return -sum;
else return sum;
}
Arc Tangente
/**************************************************************************************************/
float xyarctan(int x,int y)
{
float ax,ay;
if (x==0 && y==0) return 0;
if (y==0) {if (x>0) return 0; else return PI;}
if (x==0) {if (y>0) return PIsur2; else return -PIsur2;}
if (x==y) {if (x>0) return PIsur4; else return -3*PIsur4;}
if (x==-y) {if (x>0) return -PIsur4; else return 3*PIsur4;}
if (x<0) ax=-x; else ax=x;
if (y<0) ay=-y; else ay=y;
if (ay>ax) ratio=ax/ay; else ratio=ay/ax;
/* methode du dev limite dans la section 0 45degre
la formule est x - x3/3 + x5/5 -x7/7 +x9/9 mais la convergence prés de 1 est vraiment pas bonne !
formule utilisée pour le calcul du terme 9 pour reduire l'erreur on divise differement par tranche
IF(Ratio<0,44;Ratio^9/9;IF(Ratio<0,75;3*Ratio^9/36;if(ratio*ratio<0.87;12*Ratio^9/180;ratio^9/15.6))
*/
ori=ratio*ratio;
// ordre 1
sum=ratio;
// ordre 3
ratio=ratio*ori;
sum-=ratio/3;
//ordre 5
ratio=ratio*ori;
sum+=ratio/5;
ratio=ratio*ori;
sum-=ratio/7;
ratio=ratio*ori;
if (ori<0.1936) sum+=ratio/9;
else {
if (ori<0.5625) sum+=ratio/12;
else {
if (ori<0.87) sum+=ratio/15;
else {
if (ori<0.95) sum+=ratio/15.6;
else sum+=ratio/16;
}
}
}
// l'angle est calcule, le remettre dans le bon morceau
if (ay>ax) sum=PIsur2-sum;
if (y<0) sum=-sum;
if (x<0) sum=PI-sum;
return sum;
}
Tracer une droite
Tracer un cercle
algorithme de Bresenham
Private Sub cercle(r As Integer, c As Long, x0 As Integer, y0 As Integer)
Dim x, y, d As Integer
x = 0
y = r
d = 1 - r
Picture1.PSet (x + x0, y + y0), c
Picture1.PSet (-x + x0, y + y0), c
Picture1.PSet (x + x0, -y + y0), c
Picture1.PSet (-x + x0, -y + y0), c
Picture1.PSet (y + x0, x + y0), c
Picture1.PSet (-y + x0, x + y0), c
Picture1.PSet (y + x0, -x + y0), c
Picture1.PSet (-y + x0, -x + y0), c
While (y > x)
If (d < 0) Then
d = d + (2 * x) + 3
Else
d = d + (2 * (x - y)) + 5
y = y - 1
End If
x = x + 1
Picture1.PSet (y + x0, x + y0), c
Picture1.PSet (-y + x0, x + y0), c
Picture1.PSet (y + x0, -x + y0), c
Picture1.PSet (-y + x0, -x + y0), c
Picture1.PSet (x + x0, y + y0), c
Picture1.PSet (x + x0, -y + y0), c
Picture1.PSet (-x + x0, y + y0), c
Picture1.PSet (-x + x0, -y + y0), c
Wend
End Sub
Retour à LaFaq
Page non modifiable
|
