During this day, when I was idle, I saw SICP (Structure and Interpretation of Computer Programs) and found that it was interesting. I saw an algorithm for square roots. The brain search, it seems that I haven't studied how to calculate the square root from a small child, I only know the definition of the square root. So I plan to record it. Square root with Newton method: Enter: x output: y Require: (Y * Y - x) <0.001 (Note: Because the square root operation is generally involved in a precision problem) Algorithm: 1. Guess a value as Y2. If y Insufficient accuracy, use the following formula to improve Y: Y = (Y X / Y) / 2; then repeat the second step; if Y is enough, then output Y; do not know if the above expression is clear enough . Let's give my program. #include
Double my_abs (double y) {if (y <0) return (-y); else returno}
Bool Good_enough (Double Guess, Double X) {Return (MY_ABS ((Guess * Guess) - x) <0.001);}
Double try_sqrt (Double Guess, Double X) {IF (Good_enough (X)) Return Guess; Else Return Try_SQRT ((Guess (X / Guess)) / 2.0, x);} Double My_SQRT (Double X) {Return TRY_SQRT (1.0, x);}
INT main () {cout << my_sqrt (2) << Endl; return 0;} Of course, you can see that this is the value of the initial guess, it is 1.0, about this initial value, I don't know No good way. There is also a problem that about how to determine if it is accurate enough. The algorithm here only determines whether the difference between the value of the value is less than 0.001. There is also a method of judging to compare the last results and the difference between this result. I haven't considered the difference between the method of the above. Finally, there is another problem with the SQRT () function of the standard library. The operation results of the above program are as follows: 1.41422 The results of the standard library are: 1.41421 I don't know what algorithm is used in the standard library. In addition, if 0.001 of the judgment accuracy is changed to 0.0001, there is no change in the results. However, if it is changed to 0.01, it will clearly see the error of the result, the result of this algorithm is: 1.41667. In addition, if the square root of 36 is taken as accuracy, the result is problematic. The result of this algorithm is: 6.00025, if 0.001 is taken as accuracy, then the result is correct, 嘻嘻 ~ wait until there is time Go see the algorithm of the standard library, it is suspected that it is the difference between the judgment accuracy. Ha ha. Oh, there is another way to record, it is to see the SICP saying, seeking a square root is only a special case of Newton, it also has the algorithm for cubic roots. Its universal form seems to be a way to solve the equation, wait for me to see again. Record. Supplement: Without solving the problem, I always feel that I have a heart, so I will try it again. This time I take the difference between the two adjacent calculations as accuracy, the findings are different from the above, or the first paste procedure: bool good_enough2 (double guess1, double guess2) {if (my_abs (guess1 - guess2) <0.01) return true; else return false;} double try_sqrt2 (double guess, double x) {double next_guess = (guess (x / guess)) / 2.0; if (good_enough2 (next_guess, guess) Return next_guess; else return try_sqrt2 (next_guess, x);}
