超越函数的高精度计算

gxqcn · 发表于 2009-1-7 19:48:54

原帖由 无心人 于 2009-1-7 19:40 发表
GxQ说的是牛顿二次收敛方法？

非也。

是一种称之为“Karatsuba Square Root”的算法。

liangbch · 发表于 2009-1-7 20:01:24

另外，当a_n和b_n很接近时，在计算a_n^2-b_n^2 时，也可采用这样的方法,或许可提高速度
令 a_n=b_n+d
则：a_n^2-b_n^2= 2b^n*d+d^2

注意，不直接计算a和b的平方，并不一定可提高速度，所有我用了或许2字。因为不同级别的乘法（硬乘法，分治法，FFT/FNT算法），对于平方运算，都有比普通乘法更快的运算。

楼上分析过没有，楼上提到的平方根算法，比常规的牛顿迭代法快多少。其实传统的牛顿迭代法已经很快了，使用此法计算大数平方根，用时仅比同等长度乘法运算慢50%。我的那个计算$sqrt2$的帖子就是一个例证。

gxqcn · 发表于 2009-1-7 20:06:44

计算 $sqrt(2)$ 用牛顿迭代法的优势是被开方数有效数字很短，
大数乘法运算退化成大数x小整数的情形。

如果被开方数也是很多数字的数，则牛顿迭代法并不见得占优。

无心人 · 发表于 2009-1-7 20:35:09

那在起先几个步骤
完全可以用很准确的方法估计出好的近似值

比如，根据初始数字和数字长度来产生初始值
使得初始有效数字至少有2－4位
那完全是可能的

仙剑魔 · 发表于 2009-1-7 20:37:20

我用的全是牛顿法
如果有更快的算法,我很乐意尝试一下
毕竟速度才是我的追求

无心人 · 发表于 2009-1-7 20:49:58

呵呵
才明白GxQ的意思

那和算法无关的
你有更好的思路？

仙剑魔 · 发表于 2009-1-11 23:38:55

话说复数的agm要怎么算?
照理说公式是不变的
那么仍旧是
an+1=(an+bn)/2
bn+1=sqrt(an*bn)
但是复数开根号会有2重根,那么取那个?
是不是幅角介于an,bn之间的那个?
我之前推了一下式子,迭代一次似乎就得开2次根号的说

kakery1986 · 发表于 2009-1-19 15:46:45

这个论坛人不是很多但水平很高啊，见到1年前做数独的mathe啦

mathkid · 发表于 2009-2-17 22:20:28

没钱下载附件了

没——问题 · 发表于 2010-8-10 20:47:09

15分钟前平生第一次决定用gmp，apt-get之后就边查手册边写代码，代码写了大半发现找不到对数函数。。。。
google之来到此页

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 超越函数的高精度计算

没钱下载附件了