数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 7173|回复: 14

[擂台] 高精度计算sqrt(2)

[复制链接]
发表于 2008-2-3 14:02:53 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
要求:可以指定任意精度计算√2

  前段时间,在northwolves发的 http://bbs.emath.ac.cn/thread-86-1-1.html 中,大家快速求出了(sqrt(2)-1)的幂展开形式,mathe说可以稍加修改就可计算高精度的√2,当时我也知道,但有个难题:如何在设定指定精度后,快速计算√2,即要做到刚刚好,既要保证精度,又不要过于精确浪费精度?

  虽然可直接计算√(2*10^2k),得到小数点后k位精确的√2;但经测试,效率并不是很高。

  不过,这个问题我现在终于有了个巧妙解决方案,到时将会整理好后与大家分享。

  从现在起,大家可以来参与这个擂台赛,看看谁的方法最巧妙?谁的效率最高?语言、算法库均不限,可以先公开编译好的程序,后公开源代码或算法。对于优胜者,我将从我的社区银行中的户头转汇一定数额的金币奖励给他(她)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-20 11:45:43 | 显示全部楼层
关于 √2 算法最详细的文章见 Pythagoras' Constant :√2,我曾计划翻译此文,但直到现在仍没有来得及动工。

个人认为,最快的算法应该是基于使用 大数乘法 的牛顿迭代法,借用楼主的库,应该很容易实现。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-20 12:32:40 | 显示全部楼层
我测试过,单纯用牛顿法速度并不快。

很遗憾,近来一直很忙,还没空写相关代码,虽然算法已形成。

BTW,非常渴望能早日看到楼上的译作。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-20 13:03:27 | 显示全部楼层
最好翻译以后再用郭的库文件实现一个代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-20 23:07:53 | 显示全部楼层
附件是采用楼主的库实现的计算sqrt(2)高精度算法的程序,各位可测试一下,看看结果是否正确,速度如何?

sqrt2.rar

28.23 KB, 下载次数: 53, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-21 08:00:34 | 显示全部楼层
非常感谢楼上提供的实例。
我现在在公司里,无法下载论坛附件,晚上回家后再测试吧。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-21 08:10:30 | 显示全部楼层
用的什么算法?
运行一下1,000,000位0.17429秒,10,000,000位用时2.44733秒(计算时间)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-21 10:24:08 | 显示全部楼层
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 秒
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-21 19:42:22 | 显示全部楼层

测试结果

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

速度确实很快。

如果这周末有空,我将也完成一个实例,看看还有多少提升空间。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-22 10:36:10 | 显示全部楼层
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.我的程序用到的算法并不难,麻烦的是精度控制,即既要在每次计算中使用尽可能少的有效数字以节省时间,又要保证计算结果的准确性。

int_sqrt.rar

30.33 KB, 下载次数: 21, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-7-26 18:34 , Processed in 0.215059 second(s), 25 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表