2

我非常惊讶为什么我的代码在第 16512 次迭代中卡住了，尽管它似乎没有语法问题。这是代码：

#include <stdio.h>
/*C version of Newton-Raphson method*/
float sqrt(float num);

main() 
{
    int i;
    for (i = 1; i <= 100000; i++) {
        printf("%d: %.3f\n", i, sqrt(i));
    }
}

float sqrt(float num)

{
    float guess, e, upperbound;
    guess = 1;
    e = 0.001;
    do 
    {
        upperbound = num / guess;
        guess = (upperbound + guess) / 2;
    } while (!(guess * guess >= num - e && 
               guess * guess <= num + e));
    return guess;
}

该代码应该使用 Newtonian-Raphson 方法找到从 1 到 100000 的所有数字的平方根，但在第 16152 次迭代之后没有任何反应。如果该信息有帮助，我正在使用 VS2012 的开发人员命令提示符来编译我的脚本。启蒙将不胜感激。

4

4 回答 4

3

老实说，当我发表我的评论时，这更像是一种预感，而不是真正的知识。该算法是有效的，所以一定是某些东西使 while 循环不终止，并且由于您正确使用了 epsilon，我们正在达到浮点数的限制。

@PaulR 的评论使它更有意义。16512 的 sqrt 是 128.499027233672 ... Float 的精度相当有限，因此它在该数字的 0.001 范围内没有得到任何东西。如果您考虑更大的数字，例如 sqrt(123455555.54321) （即 11111.11111），则更有意义。浮点精度甚至不一定能让你达到 11111，更不用说 11111.111。

更改为双重“修复”此问题，但只是将罐子踢到路上。稍后的某个地方，我们会遇到同样的精度问题，这个算法应该适用于任何大小的数字。

@mrbratch 提出了强大的解决方案 - 将您的容差定义为数字的百分比。如果您设置e = num * 0.00001，您的循环将始终完成。显然，您可以使用 epsilon 并对其进行调整以使您满意。请注意，对于大数字，这可以给你一个整数，它甚至不是最接近正确答案的整数。

我不能代表 python，但我可以确认javascript 使用 double precision。

于 2013-10-04T15:13:15.067 回答
0

简单调整

使用相对浮点精度，而不是绝对精度。

在 0.001 和 0.002 之间的 FP 可表示数字与在 1,000 和 2,000 之间的区域一样多。所以在计算平方根时，迭代次数应该取决于局部相对误差。

不要使用绝对误差范围e = 0.001，但要使用相对误差范围。然后代码运行得很好。

// e = 0.001;
e = 0.001 * num;

[编辑] 我知道@Scott Mermelstein 也有类似的评论。

于 2013-10-04T16:24:45.993 回答
0

正如评论中已经解释的那样，问题是因为任何数字都不能有那么高的精度（0.001）。特别是当数字足够大时，只保存最重要的数字。如果您想了解有关其工作原理的更多信息，请参阅 IEEE 754 标准。http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

现在，我建议您使用误差百分比作为容差：

float sqrt(float num)

{
    float guess, e, upperbound;
    guess = 1;
    e = 0.001;
    do 
    {
        upperbound = num / guess;
        guess = (upperbound + guess) / 2;
    } while (!(guess * guess / num >= 1 - e && 
               guess * guess / num <= 1 + e));
    return guess;
}
于 2013-10-04T15:38:46.793 回答
0

恕我直言，平方会导致精度损失：

#include <stdio.h>
/*C version of Newton-Raphson method*/
float mysqrt(float num); /* avoid conflicts with built-in sqrt() if any */

int main(void)
{
    int i;
    for (i = 1; i <= 100000; i++) {
        printf("%d: %.3f\n", i, (double)mysqrt(i)); /* cast to double, since printf() is varargs */
    }
return 0;
}


float mysqrt(float num)
{
    float newguess, e, oldguess;
    e = 0.001;
    newguess = 1.0;
    do
    {
        oldguess = newguess;
        newguess = (num/oldguess + newguess ) / 2;
        /* compare tor the previous value; avoid squaring */
    } while (newguess / oldguess > (1+e) || oldguess / newguess > (1+e) );
    // } while (newguess < oldguess -e || newguess > oldguess +e); // "mostly works"
    return newguess;
}
于 2013-10-04T15:39:49.160 回答