C 中的平方根算法

Question

出于练习的原因，我在 C 中编写了以下算法：

#include <stdio.h>
#include <stdlib.h>


int main(){

double x=0;

printf("Enter the number: ");

scanf("%lf", &x);

int i = 0;

double v = 0;
double n=0;
int grenze = 12;
double z = 10;
/*
for(i=1; i<(x/2+1); i++){
    v=i;
    if((v*v) <= x){
        n = i;
    }
}

v=n;
*/
for(i=1; i<grenze+1; i++){
    z = z * 0.1;

    while(v*v<x){
        v = v + z;
        if(v*v<x){
            n = v;
        }
    }
    v=n;
}
printf("%.10f\n", n);



}

这很好用，但是对于大于某个值的数字（我不知道什么时候开始），例如 50.000.000.000，程序会冻结。

这里有什么我没看到的吗？

Answer 1

对于足够大的数字v和足够小的数字z，v = v + z；是一个空操作——v 不会改变。这使你的循环运行很长一段时间。

该算法不是一个好的选择——您应该查找 Newton-Raphson 方法。我不相信你的算法会适用于像 1E-70 这样的极端数字（而且你已经证明它不适用于 1E+70 这样的数字）。请注意，在大多数支持 IEEE 浮点数的机器上，double 的范围高达 1E±300 或更多。

Could you maybe explain why for a certain limit v = v + z is a no-op please?

浮点数的小数位数是有限的——对于双精度数，通常大约为 16 位。如果加上1E+16和1E-16，那么结果就是1E+16；没有足够的有效数字来存储额外的信息。您以 5E+10 作为起点；你生成分数 z = 1.0 然后 0.1, 0.01, … 0.000 000 000 01 左右（朋友之间的数量级是多少？）。当您四处添加最小值时，您最终不会改变任何东西。

关于该主题的规范文档是 What Every Computer Scientist Should Know About Floating-Point Arithmetic or from the ACM。

Answer 2

如果你在 while 循环中写一个 printf 语句来显示 v，你会发现它在某个时候停止变化（这很糟糕，因为你用它来退出你的循环！）。

我将 printf("DEBUG: entered for loop, v=%lf\n", v); 放入 while 循环并看到：

DEBUG: entered for loop, v=173205.080757
DEBUG: entered for loop, v=173205.080757
DEBUG: entered for loop, v=173205.080757
DEBUG: entered for loop, v=173205.080757
DEBUG: entered for loop, v=173205.080757
DEBUG: entered for loop, v=173205.080757
DEBUG: entered for loop, v=173205.080757
DEBUG: entered for loop, v=173205.080757

您添加的 z 太小以至于当 v 为 173205 时它实际上并没有改变值。您可以通过将 v 的类型更改为 long double 来扩展范围；但是，由于我们只有一定数量的位可以使用，因此仍然存在一个上限，即向其添加足够小的数字不会改变可表示的值。

C 中的平方根算法

Square root algorithm in C

c

algorithm

square-root