超越函数的高精度计算

gxqcn

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

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

liangbch

另外，当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

计算 $sqrt(2)$ 用牛顿迭代法的优势是被开方数有效数字很短， 大数乘法运算退化成大数x小整数的情形。 如果被开方数也是很多数字的数，则牛顿迭代法并不见得占优。

无心人

那在起先几个步骤 完全可以用很准确的方法估计出好的近似值 比如，根据初始数字和数字长度来产生初始值 使得初始有效数字至少有2－4位 那完全是可能的

仙剑魔

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

无心人

呵呵 才明白GxQ的意思 那和算法无关的 你有更好的思路？

仙剑魔

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

kakery1986

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

mathkid

没钱下载附件了

没——问题

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