一种计算数学常数的有效方法e

Question

由于许多除法运算,常数e作为无穷级数之和的标准表示对于计算是非常低效的.那么有没有其他方法可以有效地计算常数？

谢谢!

编辑

在关注了一些链接之后,我相信效率来自于一种称为二进制分裂的技术(虽然表示仍然是系列),我并不熟悉.如果有人熟悉它,请随时贡献.

Answer 1

由于无法计算'e'的每个数字,因此您将不得不选择一个停止点.

双精度:16位十进制数

对于实际应用,"64位双精度浮点值尽可能接近'e'的真值 - 大约16位小数"是绰绰有余的.

正如KennyTM所说,这个值已经在数学库中预先计算好了.如果你想自己计算,正如汉斯帕斯特所指出的那样,因子已经快速增长.系列中的前22个项对于计算精度已经过度 - 如果将其存储在64位双精度浮点变量中,则从系列中添加更多项不会改变结果.我认为你需要花费更长的时间来眨眼,而不是让你的电脑做22次分裂.所以我认为没有任何理由进一步优化这一点.

数千,数百万或数十亿的十进制数字

正如Matthieu M.指出的那样,这个值已经计算好了,你可以从Yee的网站上下载.

如果您想自己计算,那么许多数字将不适合标准的双精度浮点数.你需要一个"bignum"图书馆.与往常一样,您可以使用现有的许多免费bignum库中的一个,或者通过构建您自己的另一个具有自己特殊怪癖的bignum库来重新发明轮子.

结果 - 一个长数字的数字 - 并不是非常有用,但计算它的程序有时被用作测试"bignum"库软件的性能和准确性的基准,并作为压力测试来检查稳定性和冷却能力新机器硬件.

一页非常简要地描述了Yee用于计算数学常数的算法.

维基百科的"二元分裂"文章更详细.我认为您正在寻找的部分是数字表示:而不是将所有数字内部存储为小数点前后的一长串数字(或二进制点),Yee将每个项和每个部分和存储为有理数 - 作为两个整数,每个整数是一长串数字.例如,假设其中一个工作CPU被分配了部分总和,

... 1/4! + 1/5! + 1/6! + ... .

而不是先为每个术语进行除法,然后添加,然后将一个百万位的定点结果返回给管理器CPU:

// extended to a million digits
1/24 + 1/120 + 1/720 => 0.0416666 + 0.0083333 + 0.00138888

CPU可以先用有理算法将系列中的所有项加在一起,然后将合理的结果返回给管理器CPU:两个整数,可能是几百个数字:

// faster
1/24 + 1/120 + 1/720 => 1/24 + 840/86400 => 106560/2073600

在以这种方式将数千个术语加在一起之后,管理器CPU在最后执行唯一的除法以获得小数点后的小数位数.

请记住避免PrematureOptimization,并始终使用ProfileBeforeOptimizing.

Answer 2

我不知道任何"更快"的计算,而不是系列的泰勒展开,即:

e = 1/0!+ 1/1!+ 1/2!+ ...

要么

1/e = 1/0! - 1/1!+ 1/2! - 1/3!+ ...

考虑到这些是由计算e的前500亿个数字的 A. Yee使用的,我想没有太多的优化要做(或者更好,它可以优化,但没有人找到方法,AFAIK)

编辑

一个非常粗略的实现

#include <iostream>
#include <iomanip>

using namespace std;

double gete(int nsteps)
{
  // Let's skip the first two terms
  double res = 2.0;
  double fact = 1;

  for (int i=2; i<nsteps; i++)
  {
    fact *= i;
    res += 1/fact;
  }

  return res;
}

int main()
{
  cout << setprecision(50) << gete(10) << endl;
  cout << setprecision(50) << gete(50) << endl;
}

输出

2.71828152557319224769116772222332656383514404296875
2.71828182845904553488480814849026501178741455078125

Answer 3

如果您正在使用double或已经float有一个M_E常数math.h.

#define M_E         2.71828182845904523536028747135266250   /* e */

e在http://en.wikipedia.org/wiki/Representations_of_e#As_an_infinite_series中还有其他代表; 所有这些都将涉及分裂.

Answer 4

这个页面有一个很好的不同计算方法的概述.

这是来自Xavier Gourdon的一个微小的C程序,用于计算计算机上的9000个十进制数字.对于π和由超几何系列的平均值定义的一些其他常数存在相同类型的程序.

[来自https://codereview.stackexchange.com/a/33019的 degolfed版本]

#include <stdio.h>
int main() {
      int N = 9009, a[9009], x;
      for (int n = N - 1; n > 0; --n) {
          a[n] = 1;
      }
      a[1] = 2;
      while (N > 9) {
          int n = N--;
          while (--n) {
              a[n] = x % n;
              x = 10 * a[n-1] + x/n;
          }
          printf("%d", x);
      }
      return 0;
  }

这个程序[代码打高尔夫球]有117个字符.它可以更改为计算更多数字(将值9009更改为更多)并更快(将常量10更改为10的另一个幂和printf命令).一个不太明显的问题是找到使用的算法.

Answer 5

我在CodeReviews上给出了关于通过泰勒系列定义计算e的问题的答案(因此,其他方法不是一种选择).评论中提出了这里的交叉帖子.我删除了与其他主题相关的评论; 有兴趣进一步解释migth的人想查看原帖.

C中的解决方案(应该很容易适应C++):

#include <stdio.h>
#include <math.h>

int main ()
{
    long double n = 0, f = 1;
    int i;
    for (i = 28; i >= 1; i--) {
        f *= i;  // f = 28*27*...*i = 28! / (i-1)!
        n += f;  // n = 28 + 28*27 + ... + 28! / (i-1)!
    }  // n = 28! * (1/0! + 1/1! + ... + 1/28!), f = 28!
    n /= f;
    printf("%.64llf\n", n);
    printf("%.64llf\n", expl(1));
    printf("%llg\n", n - expl(1));
    printf("%d\n", n == expl(1));
}

输出:

2.7182818284590452354281681079939403389289509505033493041992187500
2.7182818284590452354281681079939403389289509505033493041992187500
0
1

有两个要点:

1. 此代码不计算1,1*2,1*2*3,...即O(n ^ 2),但在一次通过中计算1*2*3*...(即O(n) )).

2. 它从较小的数字开始.如果我们试图计算

   1/1 + 1/2 + 1/6 + ... + 1/20!

   并尝试添加它1/21!,我们将添加

   1/21!= 1/51090942171709440000 = 2E-20,

   2.something,对结果没有影响(double约有16位有效数字).此效果称为下溢.

   然而,当我们从这些数字开始时,即,如果我们计算1/32!+ 1/31!+ ......它们都会产生一些影响.

这个解决方案似乎符合C计算的expl功能,在我的64位机器上,用gcc 4.7.2 20120921编译.