一个更好的程序来评估数字的平方根
我是C编程语言的初学者，我被赋予这个任务来编写一个程序来计算自然数的平方根，而不使用math.h或除stdio.h之外的任何其他库函数。
请参阅我们在整个过程中使用int ，因此对于非平方数，我们找到n的平方根的底数。 现在我制作了这个程序，但它只适用于完美的正方形，但对于非正方形，它不起作用。 我在这里引用它，我希望有一些方法可以修改它。
#include main() { int a; scanf("%d", &a); int s = 1, l = a, mid = 0; while(s < l) { mid=(s + l)/2; if((mid * mid) == a) { break; } else if ((mid * mid) < a) { s = mid + 1; } else { l = mid; } } printf("%d", mid); }
非常感谢您的帮助，请尽可能纠正我。
编辑：很抱歉给您带来不便。
您似乎正在使用二分法。 这将起作用，并且是一种稳定的近似方法，但速度很慢。
更好的方法是Newton-Raphson方法。 有些情况下它会变得不稳定（即：n阶多项式根求解，其中多个根彼此非常接近，例如： y=(x-1)(x-1.1)(x-1.1) ，但它得到了完成工作。通过更快，我的意思是，与您的方法相比，它需要更少的迭代才能达到所需数量的重要数字。
编辑：由于您必须使用分而治之的方法，我已将两种算法都放在代码中。
代码清单
/* Preprocessor inclusions */ #include /* Preprocessor Macros */ #define TOL (0.001) /* Error tolerance bound */ #define FABS(a) ((a)>0.0?(a):-(a)) /* Function Prototypes */ double sq_root(double x); int divideAndConquerAndTruncateForSquareRoot(int n); /* Function Definitions */ double sq_root(double x) { double rt = 1, ort = 0; while(FABS(ort-rt) > TOL) { ort = rt; rt = ((x/rt) + rt) / 2; } return rt; } int divideAndConquerAndTruncateForSquareRoot(int n) { int low = 0; int high = n+1; int mid; while ((high-low) > 1) { mid = (low+high) / 2; if ((mid*mid) <= n) { low = mid; } else { high = mid; } } return low; } int main(void) { int i; printf("Calculating floating point square roots with Newton-Raphson method with a tolerance of %lf\n", TOL); for(i = 2; i<10; i++) { printf("square root of %d is %f\n",i, sq_root(i)); } printf("Calculating truncated integer square roots with divide and conquer approach\n"); for(i = 2; i<10; i++) { printf("square root of %d is %d\n",i, divideAndConquerAndTruncateForSquareRoot(i)); } return 0; }
样本输出
Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.001000 square root of 2 is 1.414214 square root of 3 is 1.732051 square root of 4 is 2.000000 square root of 5 is 2.236068 square root of 6 is 2.449490 square root of 7 is 2.645751 square root of 8 is 2.828427 square root of 9 is 3.000000 Calculating truncated integer square roots with divide and conquer approach square root of 2 is 1 square root of 3 is 1 square root of 4 is 2 square root of 5 is 2 square root of 6 is 2 square root of 7 is 2 square root of 8 is 2 square root of 9 is 3
此外，这里演示了为根求解算法定义误差范围和容差的重要性。 注意错误界限的变化程度：
代码清单
/* Preprocessor inclusions */ #include /* Preprocessor Macros */ #define FABS(a) ((a)>0.0?(a):-(a)) double TOL = 1.0; /* Function Prototypes */ double sq_root(double x); /* Function Definitions */ double sq_root(double x) { double rt = 1, ort = 0; while(FABS(ort-rt) > TOL) { ort = rt; rt = ((x/rt) + rt) / 2; diff = ort-rt; } return rt; } int main(void) { int i; int j; TOL = 1.0; for (i=0; i<5; i++, TOL /= 10) { printf("Calculating floating point square roots with Newton-Raphson method with a tolerance of %lf\n", TOL); for(j = 2; j<10; j++) { printf("square root of %d is %f\n", j, sq_root(j)); } } return 0; }
样本输出
Calculating floating point square roots with Newton-Raphson method with a tolerance of 1.000000 square root of 2 is 1.000000 square root of 3 is 1.000000 square root of 4 is 1.000000 square root of 5 is 1.000000 square root of 6 is 1.000000 square root of 7 is 1.000000 square root of 8 is 1.000000 square root of 9 is 1.000000 Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.100000 square root of 2 is 1.416667 square root of 3 is 1.732143 square root of 4 is 2.000610 square root of 5 is 2.238095 square root of 6 is 2.449494 square root of 7 is 2.645767 square root of 8 is 2.828469 square root of 9 is 3.000092 Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.010000 square root of 2 is 1.414216 square root of 3 is 1.732051 square root of 4 is 2.000000 square root of 5 is 2.236069 square root of 6 is 2.449494 square root of 7 is 2.645767 square root of 8 is 2.828427 square root of 9 is 3.000000 Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.001000 square root of 2 is 1.414214 square root of 3 is 1.732051 square root of 4 is 2.000000 square root of 5 is 2.236068 square root of 6 is 2.449490 square root of 7 is 2.645751 square root of 8 is 2.828427 square root of 9 is 3.000000 Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.000100 square root of 2 is 1.414214 square root of 3 is 1.732051 square root of 4 is 2.000000 square root of 5 is 2.236068 square root of 6 is 2.449490 square root of 7 is 2.645751 square root of 8 is 2.828427 square root of 9 is 3.000000 Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.000010 square root of 2 is 1.414214 square root of 3 is 1.732051 square root of 4 is 2.000000 square root of 5 is 2.236068 square root of 6 is 2.449490 square root of 7 is 2.645751 square root of 8 is 2.828427 square root of 9 is 3.000000 Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.000001 square root of 2 is 1.414214 square root of 3 is 1.732051 square root of 4 is 2.000000 square root of 5 is 2.236068 square root of 6 is 2.449490 square root of 7 is 2.645751 square root of 8 is 2.828427 square root of 9 is 3.000000 Calculating floating point square roots with Newton-Raphson method with a tolerance of 0.000000 square root of 2 is 1.414214 square root of 3 is 1.732051 square root of 4 is 2.000000 square root of 5 is 2.236068 square root of 6 is 2.449490 square root of 7 is 2.645751 square root of 8 is 2.828427 square root of 9 is 3.000000
最后，这是用于比较每种方法用于生成相同结果的迭代次数的最后一个示例。
代码清单
/******************************************************************************* * Preprocessor Inclusions and Definitions ******************************************************************************/ #include #define FABS(a) ((a)>0.0?(a):-(a)) typedef double (*fcnPtr)(double, double, int*); /******************************************************************************* * Function Prototypes ******************************************************************************/ double sqrt_bisection(double x, double tolerance, int* iterations); double sqrt_newton_raphson(double x, double tolerance, int* iterations); /******************************************************************************* * Function Definitions ******************************************************************************/ /******************************************************************************/ double sqrt_newton_raphson(double x, double tolerance, int* iterations) { if (!iterations || tolerance < 0.0) { printf("Invalid input\n"); return 0.0; } *iterations = 0; double rt = 1, ort = 0; while(FABS(ort-rt) > tolerance) { (*iterations)++; ort = rt; rt = ((x/rt) + rt) / 2; } return rt; } /******************************************************************************/ double sqrt_bisection(double x, double tolerance, int* iterations) { if (!iterations || tolerance < 0.0) { printf("Invalid input\n"); return 0.0; } *iterations = 0; double low = 0; double high = x+1; double mid; while (FABS(high-low) > tolerance) { (*iterations)++; mid = (low+high) / 2; if ((mid*mid) <= x) { low = mid; } else { high = mid; } } return low; } /******************************************************************************/ int main(void) { int i, j, k; fcnPtr fn = NULL; double tolerance; int iterations; fcnPtr functions[2] = { sqrt_bisection, sqrt_newton_raphson }; char* functionNames[2] = { "Bisection Method", "Newton Raphson Method" }; for (i=0; i<2; i++) { fn = functions[i]; for(j = 2; j<10; j++) { tolerance = 0.1; for (k=0; k<10; k++) { printf("square root of %d is %lf (%d iterations for tolerance of %e) using %s\n", j, fn((double)j, tolerance, &iterations), iterations, tolerance, functionNames[i]); tolerance /= 10; } } } return 0; }
样本输出
square root of 2 is 1.406250 (5 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 2 is 1.412109 (9 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 2 is 1.413574 (12 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 2 is 1.414124 (15 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 2 is 1.414209 (19 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 2 is 1.414213 (22 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 2 is 1.414213 (25 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 2 is 1.414214 (29 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 2 is 1.414214 (32 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 2 is 1.414214 (35 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 3 is 1.687500 (6 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 3 is 1.726562 (9 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 3 is 1.731445 (12 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 3 is 1.731995 (16 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 3 is 1.732048 (19 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 3 is 1.732050 (22 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 3 is 1.732051 (26 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 3 is 1.732051 (29 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 3 is 1.732051 (32 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 3 is 1.732051 (36 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 4 is 1.953125 (6 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 4 is 1.992188 (9 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 4 is 1.999512 (13 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 4 is 1.999969 (16 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 4 is 1.999998 (19 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 4 is 2.000000 (23 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 4 is 2.000000 (26 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 4 is 2.000000 (29 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 4 is 2.000000 (33 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 4 is 2.000000 (36 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 5 is 2.156250 (6 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 5 is 2.232422 (10 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 5 is 2.235352 (13 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 5 is 2.235992 (16 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 5 is 2.236067 (20 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 5 is 2.236068 (23 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 5 is 2.236068 (26 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 5 is 2.236068 (30 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 5 is 2.236068 (33 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 5 is 2.236068 (36 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 6 is 2.406250 (7 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 6 is 2.447266 (10 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 6 is 2.448975 (13 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 6 is 2.449455 (17 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 6 is 2.449489 (20 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 6 is 2.449489 (23 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 6 is 2.449490 (27 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 6 is 2.449490 (30 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 6 is 2.449490 (33 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 6 is 2.449490 (37 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 7 is 2.625000 (7 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 7 is 2.640625 (10 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 7 is 2.645508 (13 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 7 is 2.645691 (17 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 7 is 2.645744 (20 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 7 is 2.645751 (23 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 7 is 2.645751 (27 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 7 is 2.645751 (30 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 7 is 2.645751 (33 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 7 is 2.645751 (37 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 8 is 2.812500 (7 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 8 is 2.821289 (10 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 8 is 2.827881 (14 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 8 is 2.828362 (17 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 8 is 2.828422 (20 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 8 is 2.828427 (24 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 8 is 2.828427 (27 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 8 is 2.828427 (30 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 8 is 2.828427 (34 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 8 is 2.828427 (37 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 9 is 2.968750 (7 iterations for tolerance of 1.000000e-01) using Bisection Method square root of 9 is 2.998047 (10 iterations for tolerance of 1.000000e-02) using Bisection Method square root of 9 is 2.999878 (14 iterations for tolerance of 1.000000e-03) using Bisection Method square root of 9 is 2.999954 (17 iterations for tolerance of 1.000000e-04) using Bisection Method square root of 9 is 2.999992 (20 iterations for tolerance of 1.000000e-05) using Bisection Method square root of 9 is 3.000000 (24 iterations for tolerance of 1.000000e-06) using Bisection Method square root of 9 is 3.000000 (27 iterations for tolerance of 1.000000e-07) using Bisection Method square root of 9 is 3.000000 (30 iterations for tolerance of 1.000000e-08) using Bisection Method square root of 9 is 3.000000 (34 iterations for tolerance of 1.000000e-09) using Bisection Method square root of 9 is 3.000000 (37 iterations for tolerance of 1.000000e-10) using Bisection Method square root of 2 is 1.416667 (2 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 2 is 1.414216 (3 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 2 is 1.414214 (4 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 2 is 1.414214 (4 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 2 is 1.414214 (4 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 2 is 1.414214 (5 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 2 is 1.414214 (5 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 2 is 1.414214 (5 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 2 is 1.414214 (5 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 2 is 1.414214 (5 iterations for tolerance of 1.000000e-10) using Newton Raphson Method square root of 3 is 1.732143 (3 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 3 is 1.732051 (4 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 3 is 1.732051 (4 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 3 is 1.732051 (4 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 3 is 1.732051 (5 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 3 is 1.732051 (5 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 3 is 1.732051 (5 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 3 is 1.732051 (5 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 3 is 1.732051 (6 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 3 is 1.732051 (6 iterations for tolerance of 1.000000e-10) using Newton Raphson Method square root of 4 is 2.000610 (3 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 4 is 2.000000 (4 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 4 is 2.000000 (4 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 4 is 2.000000 (5 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 4 is 2.000000 (5 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 4 is 2.000000 (5 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 4 is 2.000000 (5 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 4 is 2.000000 (6 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 4 is 2.000000 (6 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 4 is 2.000000 (6 iterations for tolerance of 1.000000e-10) using Newton Raphson Method square root of 5 is 2.238095 (3 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 5 is 2.236069 (4 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 5 is 2.236068 (5 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 5 is 2.236068 (5 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 5 is 2.236068 (5 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 5 is 2.236068 (5 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 5 is 2.236068 (6 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 5 is 2.236068 (6 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 5 is 2.236068 (6 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 5 is 2.236068 (6 iterations for tolerance of 1.000000e-10) using Newton Raphson Method square root of 6 is 2.449494 (4 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 6 is 2.449494 (4 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 6 is 2.449490 (5 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 6 is 2.449490 (5 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 6 is 2.449490 (5 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 6 is 2.449490 (6 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 6 is 2.449490 (6 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 6 is 2.449490 (6 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 6 is 2.449490 (6 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 6 is 2.449490 (6 iterations for tolerance of 1.000000e-10) using Newton Raphson Method square root of 7 is 2.645767 (4 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 7 is 2.645767 (4 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 7 is 2.645751 (5 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 7 is 2.645751 (5 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 7 is 2.645751 (6 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 7 is 2.645751 (6 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 7 is 2.645751 (6 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 7 is 2.645751 (6 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 7 is 2.645751 (6 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 7 is 2.645751 (6 iterations for tolerance of 1.000000e-10) using Newton Raphson Method square root of 8 is 2.828469 (4 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 8 is 2.828427 (5 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 8 is 2.828427 (5 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 8 is 2.828427 (5 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 8 is 2.828427 (6 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 8 is 2.828427 (6 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 8 is 2.828427 (6 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 8 is 2.828427 (6 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 8 is 2.828427 (6 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 8 is 2.828427 (7 iterations for tolerance of 1.000000e-10) using Newton Raphson Method square root of 9 is 3.000092 (4 iterations for tolerance of 1.000000e-01) using Newton Raphson Method square root of 9 is 3.000000 (5 iterations for tolerance of 1.000000e-02) using Newton Raphson Method square root of 9 is 3.000000 (5 iterations for tolerance of 1.000000e-03) using Newton Raphson Method square root of 9 is 3.000000 (5 iterations for tolerance of 1.000000e-04) using Newton Raphson Method square root of 9 is 3.000000 (6 iterations for tolerance of 1.000000e-05) using Newton Raphson Method square root of 9 is 3.000000 (6 iterations for tolerance of 1.000000e-06) using Newton Raphson Method square root of 9 is 3.000000 (6 iterations for tolerance of 1.000000e-07) using Newton Raphson Method square root of 9 is 3.000000 (6 iterations for tolerance of 1.000000e-08) using Newton Raphson Method square root of 9 is 3.000000 (7 iterations for tolerance of 1.000000e-09) using Newton Raphson Method square root of 9 is 3.000000 (7 iterations for tolerance of 1.000000e-10) using Newton Raphson Method
参考
- 1.1.7示例：牛顿方法的平方根 ，访问2014-08-19，
- C中的平方根使用Newton-Raphson方法 ，访问2014-08-19，
- 牛顿方法 ，访问2014-08-19，
OP的方法可以通过以下方法修复。 该方法仅适用于0 <= x < sqrt(INT_MAX)*2范围内的int 。
scanf("%d", &a); int s = 1, l = a, mid = 0; while (s <= l) { mid = (s + l) / 2; if ((mid * mid) == a) { break; } if ((mid * mid) < a) { s = mid + 1; } else { l = mid - 1; } } mid = (s + l) / 2; printf("%d\n", mid);
Wiki有一个很好的解决方案 。 以下是一个适用于所有unsigned的无符号版本。 它快速而简单。 在没有1指令时钟的嵌入式处理器上，可能是最快的。
[编辑2017]增加了便携式最强的4次幂代码
#include #include // greatest power of 4 <= a power-of-2 minus 1 #define POW4_LE_POW2M1(pow2m1) ((((pow2m1)/2) + 1) >> ((pow2m1)%3==0)) unsigned isqrt(unsigned num) { unsigned res = 0; // The greatest power-of-4 unsigned bit = POW4_LE_POW2M1(UINT_MAX); // "bit" starts at the highest power of four <= the argument. while (bit > num) bit >>= 2; while (bit != 0) { if (num >= res + bit) { num -= res + bit; res = (res >> 1) + bit; } else res >>= 1; bit >>= 2; } return res; }
[编辑]在另一个答案的评论中，@ Nils Pipenbrinck请求基于Newton-Raphson的整数sqrt函数。 以下执行速度比请求快一点，因为它比假设1更好地进行第一次猜测。对于32位unsigned ，它执行5次最大迭代。 棘手的一点是处理适当的终止条件。
unsigned isqr_Newton(unsigned x) { unsigned rt[3] = {1,0,0}; // current and previous 2 root candidates unsigned x2 = x; // Form initial guess while (x2 > rt[0]) { x2 >>= 1; rt[0] <<= 1; } do { rt[2] = rt[1]; rt[1] = rt[0]; rt[0] = (x/rt[0] + rt[0])/2; } while (rt[1] != rt[0] && rt[2] != rt[0]); return (rt[0] + rt[1])/2; }