计算百万位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的原理,但是搜不到”，你只是为了应用，要原理干什么，你又不是数学家。