Эффективный способ вычислить математическую константу e

С моей точки зрения, наиболее эффективный способ вычислить e с желаемой точностью - использовать следующее представление:

e: = lim (n -> inf): ( 1 + (1 / n)) ^ n

Особенно, если вы выберете n = 2 ^ x , вы можете вычислить потенцию с умножением всего на x, поскольку:

a ^ n = (a ^ 2) ^ (n / 2), если n% 2 = 0

Метод двоичного деления хорошо поддается метапрограмме шаблона, которая производит тип, представляющий рациональный тип, соответствующий приближенному значению e. 13 итераций кажется максимумом - любое большее число вызовет ошибку "переполнение интегральной константы".

#include <iostream>
#include <iomanip>

template<int NUMER = 0, int DENOM = 1>
struct Rational
{
    enum {NUMERATOR = NUMER};
    enum {DENOMINATOR = DENOM};

    static double value;
};

template<int NUMER, int DENOM>
double Rational<NUMER, DENOM>::value = static_cast<double> (NUMER) / DENOM;

template<int ITERS, class APPROX = Rational<2, 1>, int I = 2>
struct CalcE
{
    typedef Rational<APPROX::NUMERATOR * I + 1, APPROX::DENOMINATOR * I> NewApprox;
    typedef typename CalcE<ITERS, NewApprox, I + 1>::Result Result;
};

template<int ITERS, class APPROX>
struct CalcE<ITERS, APPROX, ITERS>
{
    typedef APPROX Result;
};

int test (int argc, char* argv[])
{
    std::cout << std::setprecision (9);

    // ExpType is the type containing our approximation to e.
    typedef CalcE<13>::Result ExpType;

    // Call result() to produce the double value.
    std::cout << "e ~ " << ExpType::value << std::endl;

    return 0;
}

Другой (не метапрограммный) вариант шаблона при компиляции вычисляет двойное приближение к e. В этом варианте нет ограничения на количество итераций.

#include <iostream>
#include <iomanip>

template<int ITERS, long long NUMERATOR = 2, long long DENOMINATOR = 1, int I = 2>
struct CalcE
{
    static double result ()
    {
        return CalcE<ITERS, NUMERATOR * I + 1, DENOMINATOR * I, I + 1>::result ();
    }
};

template<int ITERS, long long NUMERATOR, long long DENOMINATOR>
struct CalcE<ITERS, NUMERATOR, DENOMINATOR, ITERS>
{
    static double result ()
    {
        return (double)NUMERATOR / DENOMINATOR;
    }
};

int main (int argc, char* argv[])
{
    std::cout << std::setprecision (16);

    std::cout << "e ~ " <<  CalcE<16>::result () << std::endl;

    return 0;
}

В оптимизированной сборке выражение CalcE<16>::result () будет заменено фактическим двойным значением.

Оба выражения, вероятно, достаточно эффективны, поскольку вычисляют e во время компиляции :-)

Если вы используете 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 ; все они будут связаны с разделением.

Возможно, вам удастся повысить эффективность. Поскольку каждый член включает факториал следующий , некоторая эффективность может быть получена путем запоминания последнего значения факториала.

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

Расширение уравнения:

e = 1 + 1/(1 * 1) + 1/(1 * 1 * 2) + 1/(1 * 2 * 3) ...

Вместо вычисления каждого факториала знаменатель умножается на следующее приращение. Таким образом, сохранение знаменателя как переменной и его умножение приведет к некоторой оптимизации.

Если вы согласны с приближением до семи цифр, используйте

3-sqrt(5/63)
2.7182819

Если вам нужно точное значение:

e = (-1)^(1/(j*pi))

где j - мнимая единица, а пи - хорошо известная математическая константа (тождество Эйлера)

Я не знаю ни одного "более быстрого" вычисления, чем разложение ряда Тейлора, т.е.:

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

или

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

Учитывая, что они были использованы A. Yee, который вычислил первые 500 миллиардов цифр e, я полагаю, что не нужно много оптимизировать (или лучше, это можно оптимизировать, но никто еще не нашел способ, AFAIK)

EDIT

Очень грубая реализация

#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

На этой странице есть хороший обзор различных методов вычисления.

Это маленькая программа на языке Си от Ксавье Гурдона для вычисления 9000 десятичных цифр e на вашем компьютере. Подобная программа существует для π и для некоторых других констант, определяемых средним значением гипергеометрических рядов.

[degolfed version from https://codereview.stackexchange.com/a/33019 ]

#include 
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). Не столь очевидный вопрос - найти используемый алгоритм.

Из Википедии замените x на 1