用于计算 c 中 e 的数字的应用程序

Question

谁能解释一下这个计算e的代码是如何工作的？对于如此复杂的任务来说，看起来很简单，但我什至无法理解这个过程。它由 Xavier Gourdon 于 1999 年创建。

int main() {

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

Answer 1

我将该算法追溯到Stanley Rabinowitz 和 Stan Wagon 1995 年发表的一篇论文。这很有趣。

\n\n

首先介绍一下背景。从 e的普通十进制表示开始：

\n\n

\n

e = 2.718281828...

\n

\n\n

这可以表示为无限和，如下所示：

\n\n

\n

e = 2 + ¹ \xe2\x81\x84 ₁₀ ( 7 + ¹ \xe2\x81\x84 ₁₀ ( 1 + ¹ \xe2\x81\x84 ₁₀ ( 8 + ¹ \xe2\x81\x84 ₁₀ ( 2 + ¹ \ xe2\x81\x84 ₁₀ ( 8 + ¹ \xe2\x81\x84 ₁₀ ( 1 ...

\n

\n\n

显然这不是一个特别有用的表示；我们只是将e的相同数字包裹在一个复杂的表达式中。

\n\n

但是看看当我们用自然数的倒数替换这些¹ \xe2\x81\x84 ₁₀因子时会发生什么：

\n\n

\n

e = 2 + ¹ \xe2\x81\x84 ₂ ( 1 + ¹ \xe2\x81\x84 ₃ ( 1 + ¹ \xe2\x81\x84 ₄ ( 1 + ¹ \xe2\x81\x84 ₅ ( 1 + ¹ \ xe2\x81\x84 ₆ ( 1 + ¹ \xe2\x81\x84 ₇ ( 1 ...

\n

\n\n

这种所谓的混合基数表示形式为我们提供了一个由数字 2 后跟重复的 1 序列组成的序列。很容易看出为什么这样做有效。当我们展开括号时，我们最终得到了著名的 e 泰勒级数：

\n\n

\n

e = 1 + 1 + 1/2！+ 1/3！+ 1/4！+ 1/5！+ 1/6！+ 1/7！+ ...

\n

\n\n

那么这个算法是如何工作的呢？好吧，我们首先用混合基数 (0; 2; 1; 1; 1; 1; 1; ...) 填充数组。要生成每个连续的数字，我们只需将该数字乘以 10 并吐出最左边的数字。*

\n\n

但由于数字以混合基数形式表示，因此我们必须对每个数字使用不同的基数。为此，我们从右向左计算，将第n位数字乘以 10，然后将其替换为对n取模的结果值。如果结果大于或等于n，我们将值x / n移至左边的下一位。（除以n会将基数从 1/n! 更改为 1/(n-1)!，这就是我们想要的）。这实际上就是内循环的作用：

\n\n

  while (--n) {\n      a[n] = x % n;\n      x = 10 * a[n-1] + x/n;\n  }\n

\n\n

这里，x在程序开始时被初始化为零，并且数组开头的初始 0 确保每次内部循环结束时它都重置为零。因此，随着程序的运行，数组将逐渐从右侧填充零。这就是为什么n可以在外循环的每一步用递减的值N进行初始化。

\n\n

数组末尾的额外 9 位数字可能是为了防止舍入错误而包含在内。运行此代码时，x达到最大值 89671，这意味着商将跨越多个数字。

\n\n

笔记：

\n\n

\n

1. 这是一种套管算法，因为它使用简单的整数算术输出e的连续数字。

\n

2. 正如 Rabinowitz 和 Wagon 在他们的论文中指出的，该算法实际上是由 AHJ Sale 于 50 年前发明的

\n

\n\n\n\n

^{* 除了在第一次迭代时输出两位数字（“27”）}

\n