带停止条件的欧拉数

Question

原始过时代码：

我的算法课程教授给我布置了以下作业：

Write a C/C++ program that calculates the value of the Euler's number (e) with a given accuracy of eps > 0. Hint: The number e = 1 + 1/1! +1/2! + ... + 1 / n! + ... = 2.7172 ... can be calculated as the sum of elements of the sequence x_0, x_1, x_2, ..., where x_0 = 1, x_1 = 1+ 1/1 !, x_2 = 1 + 1/1! +1/2 !, ..., the summation continues as long as the condition |x_(i+1) - x_i| >= eps is valid.

正如他进一步解释的那样，eps 是算法的精度。例如，精度可以是 1/100 |x_(i + 1) - x_i| = ( x_(i+1) - x_i )

的绝对值

目前，我的程序如下所示：

#include<iostream>
#include<cstdlib>
#include<math.h>

// Euler's number

using namespace std;

double factorial(double n)
{
    double result = 1;
    for(double i = 1; i <= n; i++)
    {
        result = result*i;
    }
    return result;
}

int main()
{
    long double euler = 2;

    long double counter = 2;
    long double epsilon = 1.0/1000;
    long double moduloDifference;

    do
    {
        euler+=  1 / factorial(counter);
        counter++;
        moduloDifference = (euler + 1 / factorial(counter+1) - euler);
    } while(moduloDifference >= epsilon);
    printf("%.35Lf ", euler );
    return 0;
}

问题：

我的 epsilon 值似乎无法正常工作。它应该控制精度。例如，当我希望精度为 5 位数字时，我将其初始化为 1.0/10000，它输出 3 位数字，然后在 8 (.7180) 之后被截断。
当我使用 long double 数据类型并且 epsilon = 1/10000 时，我的 epsilon 得到值 0，我的程序无限运行。然而，如果将数据类型从 long double 更改为 double，它就可以工作。为什么使用 long double 数据类型时 epsilon 变为 0？
如何优化求欧拉数的算法？我知道，我可以摆脱该功能并即时计算欧拉值，但每次尝试这样做后，我都会收到其他错误。

Answer 1

用这种方式计算欧拉常数的一个问题非常简单：您从一些相当大的数字开始，但由于每一项的分母是 N!，因此每一项相加的数量会减少非常很快。使用简单的求和，您很快就会达到一个点，即您添加的值足够小，不再影响总和。

在欧拉常数的特定情况下，由于数字不断减少，我们可以更好地处理它们的一种方法是计算并存储所有项，然后以相反的顺序将它们相加。

另一种更普遍的可能性是改用 Kahan 求和算法。这会在进行求和时跟踪运行错误，并在添加每个连续项时考虑当前错误。

例如，我重写了您的代码以使用 Kahan 求和来计算（大约）典型（80 位）long double:

的精度极限

#include<iostream>
#include<cstdlib>
#include<math.h>
#include <vector>
#include <iomanip>
#include <limits>

// Euler's number

using namespace std;

long double factorial(long double n)
{
    long double result = 1.0L;
    for(int i = 1; i <= n; i++)
    {
        result = result*i;
    }
    return result;
}

template <class InIt>
typename std::iterator_traits<InIt>::value_type accumulate(InIt begin, InIt end) {
    typedef typename std::iterator_traits<InIt>::value_type real;
    real sum = real();
    real running_error = real();

    for ( ; begin != end; ++begin) {
        real difference = *begin - running_error;
        real temp = sum + difference;
        running_error = (temp - sum) - difference;
        sum = temp;
    }
    return sum;
}

int main()
{  
  std::vector<long double> terms;
  long double epsilon = 1e-19;

  long double i = 0;
  double term;
 
  for (int i=0; (term=1.0L/factorial(i)) >= epsilon; i++)
    terms.push_back(term);

  int width = std::numeric_limits<long double>::digits10;

  std::cout << std::setw(width) << std::setprecision(width) << accumulate(terms.begin(), terms.end()) << "\n";
}

结果：2.71828182845904522

公平地说，我实际上应该补充一点，我没有使用简单求和检查您的代码会发生什么——您看到的问题可能来自其他来源。另一方面，这确实非常适合 Kahan 求和至少有合理机会改善结果的情况。

Answer 2

#include<iostream>
#include<cmath>
#include<iomanip>

#define EPSILON  1.0/10000000
#define AMOUNT  6

using namespace std;

int main() {
    
    long double e = 2.0, e0;
    long double factorial = 1;

    int counter = 2;
    long double moduloDifference;

    do {
        e0 = e;
        factorial *= counter++;
        e += 1.0 / factorial;

        moduloDifference = fabs(e - e0);
    } while (moduloDifference >= EPSILON);

    cout << "Wynik:" << endl;
    cout << setprecision(AMOUNT) << e << endl;
    return 0;
}

这是一个优化版本，没有单独的函数来计算阶乘。

问题 1：我仍然不确定 EPSILON 如何管理精度。

问题2：我不明白long double和double的真正区别。关于我的代码，为什么 long double 需要小数点 (1.0/someNumber)，而 double 不需要 (1/someNumber)

带停止条件的欧拉数

Euler's number with stop condition

c++

algorithm

factorial

eulers-number