Problème avec une fonction récursive pour trouver sqrt d'un nombre

Voici un programme simple qui calcule sqrt d'un nombre en utilisant Bisection. En cours d'exécution avec un appel comme sqrtr (4,1,4) dans va dans une récursivité sans fin. Je suis incapable de comprendre pourquoi cela se produit. Ci-dessous la fonction:Problème avec une fonction récursive pour trouver sqrt d'un nombre

double sqrtr(double N , double Low ,double High ) 
{ 

    double value = 0.00; 

    double mid = (Low + High + 1)/2; 

    if(Low == High) 
    { 
     value = High; 

    } 

    else if (N < mid * mid) 
    { 
     value = sqrtr(N,Low,mid-1) ; 


    } 
    else if(N >= mid * mid) 
    { 
     value = sqrtr(N,mid,High) ; 

    } 

    return value; 

}

Source

2010-05-20 Eternal Learner

Je sens une condition de limite d'incohérence d'arrondi. –

http://docs.sun.com/source/806-3568/ncg_goldberg.html –

@Platinum Azure: étonnamment, je ne le fais pas. Crédits à jpalecek, qui a noté que la partie +1 a été volée d'un algorithme entier. Cela vous donne complètement les mauvaises limites, donc cela n'a plus d'importance comment vous les arrondissez. – MSalters

Vous pouvez avoir à mettre une gamme sur votre comparaison low == high, à savoir high - low < .000001 pour six places de précision décimale.

Source

2010-05-20 22:39:50

Euh, que diriez-vous de N = 143214.4213e22? Maintenant, comment aimez-vous le test, haut-bas <0.000001? Voir ma réponse. –

En plus d'avoir une condition mauvaise de terminaison, comment avez-vous ceci:

else if (N < mid * mid) 
{ 
    value = sqrtr(N,Low,mid-1) ;

Comment est le mid-1 justifié? N'avez-vous pas copié-collé du code pour une recherche binaire entière?

Source

2010-05-20 22:42:37 jpalecek

Pensait la même chose moi-même. Que -1 doit partir! –

Yup. Essayez 'sqrtr (0.0001, 0.0, 0.1)' pour une preuve instantanée. – MSalters

Il est rarement judicieux de s'appuyer sur des valeurs à virgule flottante qui se correspondent. Il est très facile pour eux d'être légèrement décalés puisque, contrairement aux entiers, ils ne peuvent pas représenter toutes les valeurs dans la gamme de valeurs qu'ils représentent. Par conséquent, vous devrez probablement effectuer une comparaison avec une précision donnée plutôt qu'avec une égalité exacte.

Comme indiqué dans l'un des commentaires ci-dessus, vous devriez regarder l'article "What Every Computer Scientist Should Know About Floating-Point Arithmetic". C'est un excellent document classique sur la nature des nombres à virgule flottante.

Source

2010-05-20 22:56:57

Il existe plusieurs problèmes. Comme noté par jpalecek, il semble que vous ayez coupé et collé une routine de recherche binaire (pas très bonne) pour un tableau indexé sans comprendre comment cela fonctionne. De plus, le critère de terminaison est trop strict. Je suppose que c'est un exercice d'apprentissage, parce que la bissection et la récursion est une très mauvaise façon de résoudre sqrt().

Le code ci-dessous fonctionne, mais il est horriblement lent et inexact.

#include <iostream> 
using namespace std; 

double sqrtr(double N , double Low ,double High ) 
{ 
    // Precondition: Low and High, Low <= High, must be non-negative, and must 
    // bracket sqrt(N). 

    const double sqrt_mef = 1e-8; // Approximate square root of machine efficiency 

    double mid = (Low + High)/2; // No +1 

    if((High-Low)/(1+mid) < sqrt_mef) 
    { 
     return mid; 
    } 

    else if (N < mid * mid) 
    { 
     return sqrtr(N,Low,mid) ; // No -1 
    } 
    else 
    { 
     return sqrtr(N,mid,High) ; 
    } 

} 

int main() 
{ 
    double sqrt_2 = sqrtr(2.0, 0, 2.0); 
    cout << sqrt_2*sqrt_2 << endl; 
    getchar(); 
}

Source

2010-05-21 01:02:19

Problème avec une fonction récursive pour trouver sqrt d'un nombre

Répondre

Questions connexes