计算百万位e

liangbch

当然，我这个基于利用小质数的对数的查表法，既可以用来计算e^x,也可以用来求log(n)
若 t[ i ]是对数表的一个表项， t[ i ].n 表示真数， t[ i ].v = log(t[ i ].n), t[ i ].n 是一个分数，它的所有质因数都是一定范围内的小质数(12/5的质因数只有2,3,5这3个质数)

    对于求 e^x, 我们需要在对数表中找一个对数值刚刚小于x的表项t[ i ], 如此则  e^x  可化为 t[ i ].n * e^(x-t[ i ].v), 将e^x这个问题转化为求e^y,如果表的项数较多可使得y远小于x。

    对于求 log(x), 我们需要在对数表中找一个真数刚刚小于x的表项t[ i ], 如此则  log(x)  可化为 log( x/ t[ i ].n) + t[ i ].v, 将log(x) 这个问题转化为求log(y),y比x更接近于1。

     所以对于求e^x, 运行过程中需要多重精度乘以单精度的乘法 和 多重精度减法。而对于求log(x),运行过程中需要需要多重精度除以单精度的除法和多重精度加法。

liangbch

没有看懂你这样做的意思，这样只能使得计算的工作量加大，对提高性能没有好处。我想你还没有实现基于2^k和基于10^k大数运算的经验吧？

无心人

呵呵

昨天找到了那个问题的新思路了
今天尝试写程序
似乎还比较容易
所以对高精度对数的需求不是很迫切了

仙剑魔

x^k在k是整数的时候有快速算法
而且x*x还能用FFT

但是ln(x)难求啊...
用级数展开是不现实的,收敛太慢了
我找不到快速的算法呀...

gxqcn

原帖由 仙剑魔 于 2008-12-16 20:30 发表
x^k在k是整数的时候有快速算法
而且x*x还能用FFT
...

x^k当k是整数的时候的快速算法 是指数转二进制后从左至右不断地平方及相乘，
对于要求完全精确时，似乎没有更好的手段大幅提高效率了。

但若是指定精度，比如计算一个百位数的一千万次方的前一百位，
则也许存在更优的算法，可以减少一些大数平方及乘法次数。

至于第二句话，那是大数乘法（或平方）所用的快速算法，已属于其大数算法的核心层，
我们现在讨论的是稍高于其上的外围算法，
即便用 liangbch 的算法，最终在用到 x*x 时也会调用到它。

无心人

存在更快的幂算法
但要复杂的多
参考TAOCP V2

仙剑魔

请教liangbch
有什么方法可以快速计算ln(x)的高精度值
x不超过2位数
我曾经尝试
级数展开(速度很不理想)
公式转换(还是不理想)
迭代(稍微好了一点点)
实在没办法...

liangbch

给你几个参考：

• 本站链接：孪生小素因子数
  
• 本站链接：超越函数的高精度计算
  
• 我在CSDN上的关于这个问题的回复：紧急求助:如何只用"加减乘除"基础运算,求任意数的任意次方
  

仙剑魔

想找AGM的原理,但是搜不到...厄...

liangbch

关于AGM(算术集合平均数),在几乎所有关于圆周率计算的资料都会提到的。
那篇 The logarithm constant: log 2  文章中不是提到了嘛，你还想要什么？
“想找AGM的原理,但是搜不到”，你只是为了应用，要原理干什么，你又不是数学家。