Je dois coder un algorithme dichotomique qui permet de calculer une approximation (à une précision près donnée en argument) de la racine carrée d'un flottant.
J'ai codé l'algorithme, mais peu importe la précision que je donne, la boucle while ne sera jamais parcourue plus d'une fois, et la racine calculée ne respecte donc pas la précision.
Je n'arrive vraiment pas à voir pourquoi, pourriez-vous m'aider ?
#include <stdio.h>
double valeur_absolue(double x){
if(x>=0){
return x;
} else {
return -x;
}
}
double racine_par_dichotomie(double x, double precision){
double r = (x+1)/2;
while(valeur_absolue(((r*r)-x) > precision)){
if(x>=1){ //racine<=x
if ((r*r) > x+precision){ //borne sup
r = (r+1)/2;
} else if ((r*r)<x-precision){ //borne inf
r = (r+x)/2;
}
} else { //racine>x
if((r*r) > x+precision){ //borne sup
r = (r+x)/2;
} else if ((r*r) < x-precision){ //borne inf
r = (r+1)/2;
}
}
}
return r;
}
int main(){
racine_par_dichotomie(8.,0.0005);
return 0;
}
- Edité par Edeilwess 25 septembre 2022 à 10:48:14
Bonjour ! Je crois que ça vient des parenthèses dans la condition :
while(valeur_absolue(((r*r)-x) > precision))
Je les sépare :
while( valeur_absolue( ((r*r)-x) > precision ) )
Tu vois le problème ? Tu ne calcules pas la valeur absolue de r*r-x mais de (r*r-x > precision), qui vaut 0 (si c'est faux) ou 1 (si c'est vrai). Au début c'est faux, donc ça vaut 0, et la valeur absolue de 0 est 0. Donc tu fais : while(0) : on sort de la boucle.
J'ajoute un truc... Le problème venait de ce qu'il y avait beaucoup de parenthèses. Je trouve qu'on est typiquement dans un cas où utiliser des booléens est intéressant.
En français : on boucle tant qu'on n'a pas trouvé la racine carrée. Donc :
bool trouve = false; // au début on n'a pas trouvé
while(! trouve) // tant qu'on n'a pas trouvé
{
// on cherche
}
Et maintenant on se focalise sur le critère :
while(! trouve) // tant qu'on n'a pas trouvé
{
// ici on calcule r par dichotomie
trouve = (valeur_absolue(r*r - x) <= precision) ;
}
Il y a moins de parenthèses, donc moins de risque de mal les placer, et je trouve que c'est plus facile à comprendre (quand on se relira deux ans plus tard). En fait, utiliser des booléens permet de se rapprocher du langage naturel (d'ailleurs ce serait mieux avec des noms de variable en anglais : while not found, on peut pas faire mieux).
Pourquoi des if derrière les else lignes 17 et 23 ? Si jamais, pour une raison quelconque, le test est faux (je n'ai pas cherché à savoir si c'était possible) , r ne change pas.... et ça boucle.
Et ton code est vraiment mal indenté. Un exemple où les blocs sont bien visibles
double racine_par_dichotomie(double x, double precision) {
double r = (x+1)/2;
while(valeur_absolue(((r*r)-x) > precision)) {
if(x>=1) { // racine<=x
if ((r*r) > x+precision) { // borne sup
r = (r+1)/2;
}
else
if ((r*r)<x-precision) { // borne inf
r = (r+x)/2;
}
}
else { // racine>x
if((r*r) > x+precision) { // borne sup
r = (r+x)/2;
}
else
if ((r*r) < x-precision) { // borne inf
r = (r+1)/2;
}
}
}
return r;
}
Edit: les commentaires ne sont pas alignés, problème de tabulation
- Edité par edgarjacobs 25 septembre 2022 à 19:30:49
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent
Je ne vois pas trop où est la dichotomie là dedans.
La dichotomie, c'est quand on cerne une valeur dans un intervalle (avec valeurs inf et sup) et qu'on réduit l'intervalle en le coupant en deux.
La méthode de Newton (de mémoire) : on part d'une approximation r de la racine de x, et on calcule une meilleure approximation qui est la moyenne de r et de son "jumeau" x/r qui est "de l'autre côté" de x.
On montre facilement que la distance entre r et x/r se réduit à chaque étape, etc. bref ça marche.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
bool racine_ok(double r, double x, double precision) {
return fabs(r*r - x) <= precision;
}
// x doit être > 0
double racine(double x, double precision)
{
double r = x;
while (! racine_ok(r, x, precision)) {
r = (r + x/r) / 2;
printf("%f -> %f\n", x, r);
}
return r;
}
int main()
{
double r = racine (100.0, 0.001);
printf("racine de 100 = %f\n", r);
r = racine (0.0004, 0.00001);
printf("racine de 0.0004 = %f\n", r);
return EXIT_SUCCESS;
}
@michelbillaud: J'ai modifié ton code pour illustrer, d'une part, la rapidité de convergeance de cet algorithme. Et d'autre part, l'avantage d'avoir une bonne approximation de départ. Sur certaines machines, on peut extraire l'exposant et le diviser par deux puis le remettre en place. C'est ce que j'ai essayé de faire en multipliant ou divisant par sqrt(2). - #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <math.h>
// x doit être > 0 double racine(double x, double precision, double approx) { int count = 0; double r = approx; while (! racine_ok(r, x, precision)) { r = (r + x/r) / 2; count++; } printf("%d itérations\n", count); return r; }
int main(void) { double r = racine(100.0, 1e-3, 100.0); r = racine(100.0, 1e-5, 100.0); r = racine(100.0, 1e-5, 10.0*sqrt(2)); r = racine(100.0, 1e-5, 10.0/sqrt(2)); r = racine(100.0, 1e-10, 10.0*sqrt(2)); r = racine(100.0, 1e-15, 10.0*sqrt(2)); } - 7 itérations 7 itérations 4 itérations 4 itérations 5 itérations 5 itérations
-
edit: On peut le simuler en C avec les union et les bit field dans des structures. Ne pas oublier que le remplissage se fait à partir des bits les moins significatifs. On obtiens une assez bonne approximation de la racine. - #include <stdio.h>
typedef struct Double Double; struct Double { union { double d; struct { unsigned int f : 32; unsigned int m : 20; unsigned int e : 11; unsigned int s : 1; }; }; };
J'ai pris en compte chacune de vos remarques, et j'ai non seulement réussi à corriger mon erreur, mais aussi à faire un programme plus clair (et qui ressemble plus à un algorithme dichotomique) :
Avant ta boucle while, on devrait avoir r = (debut + fin) / 2; Tu ne les as pas évalués pour rien. if ((r*r)>x+precision){ Où est ta valeur absolue?
Le problème dans cet algo est que x est supérieur à la racine si x > 1 et inversement si x < 1. En général, on retourne la valeur dans le main et c'est lui qui décide s'il doit l'afficher.
- Edité par PierrotLeFou 26 septembre 2022 à 18:07:36
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Petit algorithme dichotomique
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
On écrit "j'ai tort", pas "tord" qui est le verbe "tordre" à la 3ème personne de l'indicatif présent
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.