Hello,
The standard representation of constant e as the sum of the infinite series is very inefficient for computation, because of many division operations. So are there any alternative ways to compute the constant efficiently?
Thanks!
EDIT
After following some of your links, I believe that efficiency comes from a technique called binary splitting (while the representation is still mentioned series), which I was not familiar with. If someone is familiar with it, feel free to contribute.
I'm not aware of any "faster" computation than the Taylor expansion of the series, i.e.:
e = 1/0! + 1/1! + 1/2! + ...
or
1/e = 1/0! - 1/1! + 1/2! - 1/3! + ...
Considering that these were used by A. Yee, who calculated the first 500 billion digits of e, I guess that there's not much optimising to do (or better, it could be optimised, but nobody yet found a way, AFAIK)
EDIT
A very rough implementation
#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;
}
Outputs
2.71828152557319224769116772222332656383514404296875
2.71828182845904553488480814849026501178741455078125
If you're using double or float, there is an M_E constant in math.h already.
#define M_E 2.71828182845904523536028747135266250 /* e */
There are other representions of e in http://en.wikipedia.org/wiki/Representations_of_e#As_an_infinite_series; all the them will involve division.
Using the infinite series is efficient because it converges very fast. Now the terms go to zero very fast and so you need high-precision arithmetic to get good results.
If you're ok with an approximation up to seven digits, use
3-sqrt(5/63)
2.7182819
If you want the exact value:
e = (-1)^(1/(j*pi))
where j is the imaginary unit and pi the well-known mathematical constant (Euler's Identity)
You may be able to gain some efficiency. Since each term involves the next factorial, some efficiency may be obtained by remembering the last value of the factorial.
e = 1 + 1/1! + 1/2! + 1/3! ...
Expanding the equation:
e = 1 + 1/(1 * 1) + 1/(1 * 1 * 2) + 1/(1 * 2 * 3) ...
Instead of computing each factorial, the denominator is multiplied by the next increment. So keeping the denominator as a variable and multiplying it will produce some optimization.
Since it's not possible to calculate every digit of 'e', you're going to have to pick a stopping point.
For practical applications, "the 64-bit double precision floating point value that is as close as possible to the true value of 'e' -- approximately 16 decimal digits" is more than adequate.
As KennyTM said, that value has already been pre-calculated for you in the math library. If you want to calculate it yourself, as Hans Passant pointed out, factorial already grows very fast. The first 22 terms in the series is already overkill for calculating to that precision -- adding further terms from the series won't change the result if it's stored in a 64 bit double-precision floating point variable. I think it will take you longer to blink than for your computer to do 22 divides. So I don't see any reason to optimize this further.
As Matthieu M. pointed out, this value has already been calculated, and you can download it from Yee's web site.
If you want to calculate it yourself, that many digits won't fit in a standard double-precision floating-point number. You need a "bignum" library. As always, you can either use one of the many free bignum libraries already available, or re-invent the wheel by building your own yet another bignum library with its own special quirks.
The result -- a long file of digits -- is not terribly useful, but programs to calculate it are sometimes used as benchmarks to test the performance and accuracy of "bignum" library software, and as stress tests to check the stability and cooling capacity of new machine hardware.
One page very briefly describes the algorithms Yee uses to calculate mathematical constants.
The Wikipedia "binary splitting" article goes into much more detail. I think the part you are looking for is the number representation: instead of internally storing all numbers as a long series of digits before and after the decimal point (or a binary point), Yee stores each term and each partial sum as a rational number -- as two integers, each of which is a long series of digits. For example, say one of the worker CPUs was assigned the partial sum,
... 1/4! + 1/5! + 1/6! + ... .
Instead of doing the division first for each term, and then adding, and then returning a single million-digit fixed-point result to the manager CPU:
// extended to a million digits
1/24 + 1/120 + 1/720 => 0.0416666 + 0.0083333 + 0.00138888
that CPU can add all the terms in the series together first with rational arithmetic, and return the rational result to the manager CPU: two integers of perhaps a few hundred digits each:
// faster
1/24 + 1/120 + 1/720 => 1/24 + 840/86400 => 106560/2073600
After thousands of terms have been added together in this way, the manager CPU does the one and only division at the very end to get the decimal digits after the decimal point.
Remember to avoid PrematureOptimization, and always ProfileBeforeOptimizing.
The binary splitting method lends itself nicely to a template metaprogram which produces a type which represents a rational corresponding to an approximation of e. 13 iterations seems to be the maximum - any higher will produce a "integral constant overflow" error.
#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;
}
Another (non-metaprogram) templated variation will, at compile-time, calculate a double approximating e. This one doesn't have the limit on the number of iterations.
#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;
}
In an optimised build the expression CalcE<16>::result () will be replaced by the actual double value.
Both are arguably quite efficient since they calculate e at compile time :-)
From my point of view, the most efficient way to compute e up to a desired precision is to use the following representation:
e := lim (n -> inf): (1 + (1/n))^n
Especially if you choose n = 2^x, you can compute the potency with just x multiplications, since:
a^n = (a^2)^(n/2), if n % 2 = 0