Υπολογισμός ρίζας σε C με μέθοδο Newton

[giannisosfp]

Καλησπέρα παιδιά, χρειάζομαι την βοήθειά σας. Πρέπει να κάνουμε ένα πρόγραμμα σε C που να υπολογίζει την τετραγωνική ρίζα ενός αριθμού με την μέθοδο Newton-Raphson.

Μας είπε ότι γίνεται Χj+1=1/2(Xj+a/Xj) μέχρι να είναι δύο διαδοχικά Χ ίσα. Δηλαδή για παράδειγμα η ρίζα του 4 είναι Xo=1, X1=1/2(1+1/4)=2,5 , X2=1/2(2,5+4/2,5)=2,05 ,X3=2, X4=4

Αυτό που έχω κάνει εγώ είναι το εξής:

>#include <stdio.h>

float sqNR(float);

int main(){
float num;


printf ("\nΠληκτρολογήστε τον αριθμό για να βρώ την τετραγωνική ρίζα.\n");
 scanf ("%f",&num);

if (num>0)
 printf ("\nΗ τετραγωνική ρίζα με την μέθοδο Newton-Raphson είναι ίση με: %.1f",sqNR(num));

else 
 printf ("\nΔεν υπολογίζεται η τετραγωνική ρίζα αρνητικού αριθμού.\n");

return 0;
}

float sqNR(float N){
float x=1,xn=1/2*(x+(N/x));
while (x!=xn){
 x=xn;
 xn=1/2*(x+(N/x));
}

return xn;
};	

 

Περνάει από το compile κανονικά και μόλις δώσω τον αριθμό φαίνεται σαν να έχω σταματήσει να τρέχει και δεν κάνει τίποτα. Μπορείτε να μου πείτε τι κάνω λάθος;

 

Σας ευχαριστώ πολύ!

[nilosgr]

Κατ αρχην στο if-else πρεπει να βαζεις {} και στο if και στο else (τουλαχιστον τωρα στην αρχη για να μην μπερδευεσαι). Τωρα για το προβλημα σου πιθανοτατα το x!=xn ειναι παντα true και γι αυτο "φαίνεται σαν να έχει σταματήσει να τρέχει", επειδη κολλαει μεσα στο loop. So, για την ορθοτητα του αλγοριθμου καλυτερα ειναι να βρεις μονος σου την ακρη...

[giannisosfp]

Ναι, όντως το είδα γιατί σταματάει. Ωραία σε ευχαριστώ, αλλά ένα στοιχείο για το πως να το κάνω όχι απαραίτητα την λύση αλλά κυρίως τον τρόπο αν είναι εύκολο. (Καταλαβαίνω γιατί το λες και έχεις απόλυτο δίκαιο.)

[nilosgr]

Μπορεις να βαλεις εναν μετριτη στο loop ωστε να κανει το πολυ (πχ) 100 επαναλυψεις, οι οπποιες ειναι ικανες να προεγγισουν τη ριζα

[defacer]

Υπάρχει ένα βασικό πρόβλημα με τον κώδικά σου, που είναι ότι ποτέ δεν μπορείς να συγκρίνεις floating point αριθμούς για ισότητα (και φυσικά επίσης για ανισότητα). Ποτέ, σε καμία γλώσσα, πουθενά και για κανένα λόγο. (υπάρχουν ίσως κάποιες εξαιρέσεις εδώ, αλλά αν καταλάβεις το γιατί θα καταλάβεις μόνος σου και ποιές μπορεί να είναι αυτές)

 

Μπορείς να διαβάσεις λεπτομερέστατη εξήγηση του γιατί (στα αγγλικά) εδώ (θα σε βοηθούσε αν ήξερες το πως αναπαρίστανται οι αριθμοί κινητής υποδιαστολής κατά IEEE 754, αλλά δεν είναι εντελώς απαραίτητο).

 

Αντί γι' αυτό, θα πρέπει να συγκρίνεις τους floats και να τους "βαφτίσεις" ίσους όταν η διαφορά τους είναι μικρότερη από κάποια τιμή την οποία μπορείς να θέσεις αυθαίρετα όσο μικρή θέλεις.

 

Κάνοντας λοιπόν αυτή την αλλαγή, και ξαναγράφοντας το loop σαν do...while (που βολεύει περισσότερο στη συγκεκριμένη περίπτωση) έχουμε:

 

>float sqNR(float N){
   float prev, current = (N + 1)/2;
   do {
       prev = current;
       current = (current+(N/current)) / 2;
   } while(abs(current - prev) > 1e-6);
   return current;
};

 

Δες το να τρέχει.

[giannisosfp]

Οπότε θα πρέπει να πάει κάπως έτσι;

>
float sqNR(float N){
       float x=1,xn=1/2*(x+(N/x));
       int i=0;

       while (x!=xn || i++<100){
        x=xn;
        xn=1/2*(x+(N/x));
       }

       return xn;
}; 

 

Πάλι κάτι δεν υπολογίζω λογικά για το xn...

 

Υπάρχει ένα βασικό πρόβλημα με τον κώδικά σου, που είναι ότι ποτέ δεν μπορείς να συγκρίνεις floating point αριθμούς για ισότητα (και φυσικά επίσης για ανισότητα). Ποτέ, σε καμία γλώσσα, πουθενά και για κανένα λόγο. (υπάρχουν ίσως κάποιες εξαιρέσεις εδώ, αλλά αν καταλάβεις το γιατί θα καταλάβεις μόνος σου και ποιές μπορεί να είναι αυτές)

 

Αντί γι' αυτό, θα πρέπει να συγκρίνεις τους floats και να τους "βαφτίσεις" ίσους όταν η διαφορά τους είναι μικρότερη από κάποια τιμή την οποία μπορείς να θέσεις αυθαίρετα όσο μικρή θέλεις.

 

Κάνοντας λοιπόν αυτή την αλλαγή, και ξαναγράφοντας το loop σαν do...while (που βολεύει περισσότερο στη συγκεκριμένη περίπτωση) έχουμε:

 

>float sqNR(float N){
   float prev, current = (N + 1)/2;
   do {
       prev = current;
       current = (current+(N/current)) / 2;
   } while(abs(current - prev) > 1e-6);
   return current;
};

 

Δες το να τρέχει.

 

To έχασα λιγάκι εώς πολύ. Σ' ευχαριστώ πολύ πάντως που ασχολήθηκες!

[defacer]

To έχασα λιγάκι εώς πολύ. Σ' ευχαριστώ πολύ πάντως που ασχολήθηκες!

 

Δες το edit μου (συνέχιζα να προσθέτω πληροφορίες όσο το διάβαζες).

 

Δεν καταλαβαίνω όπως που το έχασες. Αυτό που λέω είναι πολύ απλό. Αν x, y είναι float ή double, δεν μπορείς ποτέ να γράψεις x == y ή x != y και να περιμένεις να πάρεις σωστό αποτέλεσμα. Αν δεις τον κώδικά μου, "βαφτίζω" τους δύο floats ίσους μόλις η διαφορά τους γίνει μικρότερη από 0.000001 (αυτό φυσικά σημαίνει ότι η function μου ποτέ δε θα μπορέσει να βρει τη ρίζα με ακρίβεια μεγαλύτερη των 6 δεκαδικών).

 

Επίσης: Μην κάνεις βλακείες (ας μου επιτραπεί η έκφραση) με loops. Αυτό δεν είναι newton-raphson, και δεν θα λύσει το πρόβλημα που θα έχεις αύριο κάπου αλλού αν πας να κάνεις το ίδιο πράγμα. Προσπάθησε πρώτα να καταλάβεις γιατί έχεις πρόβλημα, αλλιώς δεν υπάρχει (προφανώς) περίπτωση να το λύσεις.

[giannisosfp]

Σε ευχαριστώ πολύ που με βάζεις σε δρόμο και μου εξηγείς. Και ΝΑΙ ξέρω ότι πολλές φορές κάνω βλακείες ... Ευχαριστώ πολύ έχω μπει σε διαδικασία και σκέφτομαι...

 

Edit: Μετά από αυτή την αλλαγή στην συνάρτηση

>float sqNR(float N){
float x=1,xn;	
int i=0;

do{
 xn=x+(N/x)/2;
 x=xn;
 i++;
 printf ("\t%.1f\t%.1f %10d\n\n",xn,x,i);
} while (x!=xn);

return xn;
};	

Μου βγάζει αυτό:

 

Πληκτρολογήστε τον αριθμό για να βρώ την τετραγωνική ρίζα.

4

3.0 3.0 1

 

 

Η τετραγωνική ρίζα με την μέθοδο Newton-Raphson είναι: 3.0

 

Κάτι που σίγουρα δεν ισχύει.

 

Edit2: Λύθηκε τελικά, ευχαριστώ πολύ για τον χρόνο και τις συμβουλές σας.

Επεξ/σία 10 Δεκεμβρίου 2011 από giannisosfp