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

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

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

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

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

×
要求:可以指定任意精度计算√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 次

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

本版积分规则

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

GMT+8, 2024-10-14 22:57 , Processed in 0.027571 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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