c - 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 float 的机器上， double 的范围高达 1E±300 或更多。

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

float 的小数位数是有限的——对于 double ，通常大约为 16 位。如果将1E+16和1E-16相加，那么结果就是1E+16；没有足够的有效数字来存储额外的信息。您将 5E+10 作为起点；你生成分数 z = 1.0 然后 0.1, 0.01, ... 0.000 000 000 01 左右(什么是顺序 friend 之间的大小？)。当您四处添加最小值时，您最终不会更改任何内容。

关于该主题的规范文档是 What Every Computer Scientist Should Know About Floating-Point Arithmetic或来自 ACM .