高精度计算sqrt(2)

gxqcn

要求：可以指定任意精度计算√2 　　前段时间，在northwolves发的 http://bbs.emath.ac.cn/thread-86-1-1.html 中，大家快速求出了(sqrt(2)-1)的幂展开形式，mathe说可以稍加修改就可计算高精度的√2，当时我也知道，但有个难题：如何在设定指定精度后，快速计算√2，即要做到刚刚好，既要保证精度，又不要过于精确浪费精度？ 　　虽然可直接计算√(2*10^2k)，得到小数点后k位精确的√2；但经测试，效率并不是很高。 　　不过，这个问题我现在终于有了个巧妙解决方案，到时将会整理好后与大家分享。 　　从现在起，大家可以来参与这个擂台赛，看看谁的方法最巧妙？谁的效率最高？语言、算法库均不限，可以先公开编译好的程序，后公开源代码或算法。对于优胜者，我将从我的社区银行中的户头转汇一定数额的金币奖励给他(她)。

liangbch

关于 √2 算法最详细的文章见 Pythagoras' Constant :√2，我曾计划翻译此文，但直到现在仍没有来得及动工。 个人认为，最快的算法应该是基于使用 大数乘法 的牛顿迭代法，借用楼主的库，应该很容易实现。

gxqcn

我测试过，单纯用牛顿法速度并不快。 很遗憾，近来一直很忙，还没空写相关代码，虽然算法已形成。 BTW，非常渴望能早日看到楼上的译作。

mathe

最好翻译以后再用郭的库文件实现一个代码

liangbch

附件是采用楼主的库实现的计算sqrt(2)高精度算法的程序，各位可测试一下，看看结果是否正确，速度如何？

gxqcn

非常感谢楼上提供的实例。 我现在在公司里，无法下载论坛附件，晚上回家后再测试吧。。。

mathe

用的什么算法？ 运行一下1,000,000位0.17429秒,10,000,000位用时2.44733秒（计算时间）

风云剑

mathe的电脑真是快啊。 calc sqrt(2) how digital is needed,0 will exit,n=?1000000 计算用时 0.503586 秒 输出到文件用时 0.027065 秒 how digital is needed,0 will exit,n=?10000000 计算用时 6.550695 秒 输出到文件用时 0.189900 秒

gxqcn

calc sqrt(2) how digital is needed,0 will exit,n=?100000 计算用时 0.063791 秒 输出到文件用时 0.135063 秒 how digital is needed,0 will exit,n=?1000000 计算用时 0.552405 秒 输出到文件用时 0.166164 秒 how digital is needed,0 will exit,n=?10000000 计算用时 8.026279 秒 输出到文件用时 1.852541 秒 how digital is needed,0 will exit,n=?0 测试环境：Windows XP SP2，Intel Pentium 4 CPU 2.93GHz，512MB DDR - 133MHz 速度确实很快。 如果这周末有空，我将也完成一个实例，看看还有多少提升空间。。。

liangbch

1. 昨天对程序进行了一些修改，使其通行性更强，可以计算 int 范围内所有正整数的平方根。见附件。

用的什么算法？ 运行一下1,000,000位0.17429秒,10,000,000位用时2.44733秒（计算时间）

2.算法描述和示例代码 /* sqrt(a) 算法： step1: 得到一个 1/sqrt(a) 近似值 x0 step2: x[n+1]= 3/2*x[n] + a/2 x[n]^3 另一个形式： ( x[n+1]= x[n] + x[n] ( 1/2- a/2 *x[n]^2) 不断计算step2,x[n+1]精度逐步提高，每次迭代精度提高一倍。 最后：计算 x[n+1]* a 得到 sqrt(a) */ double int_sqrt_demo(int n) { double x0; double x1; double c0,c1; c0=0.5; c1=double(n)/2; x0= 1 /sqrt( n ); x0= floor(x0 * 10000.0) /10000; //取前4位有效数字 while (true) { x1= x0 + x0 * (c0- c1 * x0 * x0); if ( (x1- x0)/x0 <1e-15) { break; } x0=x1; } return double(n) * x1; } 3.我的程序中调用HugeCalc的函数有： GetStr，GetDigits，DecRShift，DecLShift，Pow，+，-，*，+=，-=，*= 4.我的程序用到的算法并不难，麻烦的是精度控制，即既要在每次计算中使用尽可能少的有效数字以节省时间，又要保证计算结果的准确性。