计算百万位e

liangbch

原帖由 无心人 于 2008-4-16 21:37 发表


我想
我想
是不是有更精彩更复杂的算法

比如类似阶乘的？

7# 的算法很精彩，既简单，又有效，很且很难有这个更有效的算法了。
关于计算e更详细的资料，请参见http://numbers.computation.free.fr/Constants/E/e.html

无心人

能不能有二次迭代的公式计算e?

liangbch

从算法上 9# 程序使用的是目前最好的算法，但计算速度同PiFast依然有很大的差距，个人认为，造成这个差距的主要原因是，HugeCalc 的大数乘法和大数除法的速度仍然有待提高。

liangbch

原帖由 无心人 于 2008-4-16 21:46 发表
能不能有二次迭代的公式计算e?

计算e不同于计算$sqrt 2 $,是可以直接计算的，无需使用牛顿迭代法，因此也谈不上使用2次迭代公式。

gxqcn

北大的刘楚雄老师好像对高精计算e有研究。

我一直不想碰这些超越数的计算，主要是里面需要恰到好处的误差分析，少了不行，多了白费。

难得楼主给出了源代码，但作为库的开发者，发现局部调用可以改得更高效，明天将抽空优化一下。

今早我已对9#的代码略作了一下优化（直接在原帖上修改的），
在开启“MODIFIED_BY_GxQ”宏定义时，计算100万位e可提速3.6%

阶乘的优化，我们曾将连乘转换为分解成素数之后再运算，并藉此而大幅提速，
e的计算与阶乘紧密相联，是否还存在更高效的算法？我表示怀疑和期待。。。

——2008-04-17 09:15

无心人

liangbch的意思是计算$e$没有高速算法？

mathe

我们知道$log(n!)=O(nlog(n)-n)$
所以实际上计算K位时，我们只需要计算到一个n使得$nlog(n)-n>=C*K$,也就是计算K位时间复杂度O(nK)略微低于O(K^2)的。

mathe

连分数形式:
${e-1}/2 = [0;1,6,10,14,18,22,26,30,34,38,42,46,50,...]
应该挺不错的

无心人

2.3  An algorithm using continued fraction
Let $p_k/q_k$ be the convergent of order $k$ of a simple continued fraction of a number $x$ and let $x=[a0;a1,a2,...,ak,...]$, we know that the convergents may be computed at any order thanks to the following recurrence relations
  
  $p_k=a_kp_{k-1}+p_{k-2}$

  $q_k=a_kq_{k-1}+q_{k-2}$

with the initial conditions

  $p_{-1}=1,p_0=a_0 $

  $q_{-1}=0,q_0=1$

It's a well known properties on continued fraction that
  
    $lim_{k->infty}p_k/q_k = x$

with the bound
   
    $p_k/q_k - x < 1/q_k^2$

If we use the continued fraction for $(e-1)/2$, then

   $a_0=0,a_1=1$,

and $a_k=4(k-1)+2$ for $k > 1$. It's therefore very easy to build an efficient algorithm to compute a fast converging sequence to the constant $e$. With $k=1500$, $e$ may be computed to $10^4$ decimal places, with $k=12000$, $10^5$ digits of $e$ will be reached.

shshsh_0510

mathe说的是，我以前推荐过这个网站，我想诸位会喜欢
http://numbers.computation.free.fr/Constants/constants.html