We calculate the value of the number e at the compilation stage

Looking through the book "Effective use of C ++" by Scott Meyers, which (and I will not surprise anyone) worthy of all praise, I was very touched, then with what excitement, inspiration, trembling (maybe it seemed to me?) The author talks about patterns and their capabilities. I will give a small piece:

Metaprogramming templates ( template metaprogramming ( TMP )) is the process of writing template-based C ++ programs that are executed at compile time. Think about it for a minute: a template metaprogram is a program written in C ++ that runs inside the C ++ compiler ...
It has been proven that TMP technology provides a complete Turing machine , that is, it has enough power for any calculations ...

Yeah ... my heart beat, I was once again surprised - just to think - a complete Turing machine with all the ensuing consequences ... As for me, this is simply incredible and surprising ... although, who knows ...
')
I propose to look at a very small piece of the world of great opportunities and incredible adventures - we will try to calculate at the compilation stage the value, well-known, of the number e .

How to calculate it (with some error) will be prompted by the Taylor series , or rather the Maclaurin series :


Those. we will need to be able to count factorial numbers, raise to a power, sum up and work with fractional numbers ... and all this with the help of C ++ templates.
First I would like to deal with fractional numbers - you need to somehow save the numerator and denominator, and also have access to them ( N - Numerator, D - Denominator):

template<int n, int d> struct Fractional { enum { N = n, D = d }; }; 

It's simple, but what about the zero denominator? Let's try this:

 template<int n, int d> struct Fractional { private: enum { NonZeroDenominator = n / d }; public: enum { N = n, D = d }; }; 

We use:

 typedef Fractional<9, 0> number; // ... int temp = number::D; 

In the case of msvc10, we get something like error C2057: expected constant expression is not clear, but if we go to the place of the error, we’ll just see the NonZeroDenominator variable - at least something ...

So, we are able to keep 2 numbers, but what about the reduction of fractions? Here we must learn to find the gcd (the most common divisor) of two numbers - we need a recursive algorithm:

 int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); } 

which turns with the help of templates in:

 template<int n1, int n2> struct GCD { enum { value = GCD<n2, n1 % n2>::value }; }; template<int n1> struct GCD<n1, 0> { enum { value = n1 }; }; 

It's simple, isn't it? - we write the most common implementation of the template and we do a private specialization for particular cases (if the second number is zero, the result is the first number).
Using all the above written, we make the final version of the fractional number:

 template<int n, int d> struct Fractional { private: enum { NonZeroDenominator = n / d }; enum { gcd = GCD<n, d>::value }; public: enum { N = n / gcd, D = d / gcd }; }; 

With the help of well-known formulas - divide, multiply, subtract, add our numbers:

 // // Divide // template<typename n, typename d> struct Divide { }; template<int n1, int d1, int n2, int d2> struct Divide<Fractional<n1, d1>, Fractional<n2, d2> > { private: typedef Fractional<n1, d1> n; typedef Fractional<n2, d2> d; public: typedef Fractional<n::N * d::D, n::D * d::N> value; }; // // Multiple // template<typename n, typename d> struct Multiple { }; template<int n1, int d1, int n2, int d2> struct Multiple<Fractional<n1, d1>, Fractional<n2, d2> > { private: typedef Fractional<n1, d1> n; typedef Fractional<n2, d2> d; public: typedef Fractional<n::N * d::N, n::D * d::D> value; }; // // Substract // template<typename n, typename d> struct Substract { }; template<int n1, int d1, int n2, int d2> struct Substract<Fractional<n1, d1>, Fractional<n2, d2> > { private: typedef Fractional<n1, d1> n; typedef Fractional<n2, d2> d; public: typedef Fractional<n::N * d::D - d::N * n::D, n::D * d::D> value; }; // // Add // template<typename n, typename d> struct Add { }; template<int n1, int d1, int n2, int d2> struct Add<Fractional<n1, d1>, Fractional<n2, d2> > { private: typedef Fractional<n1, d1> n; typedef Fractional<n2, d2> d; public: typedef Fractional<n::N * d::D + d::N * n::D, n::D * d::D> value; }; 

Again, we write an empty sketch of our " function ", for example Divide - noting that it (the function) takes 2 arguments. And further, with the help of a partial template specialization, we specify that we want to see not something, but the template ID we need, i.e. Divide<n1, n2> , for example. Use :

  typedef Fractional<4, 20> n1; typedef Fractional<5, 32> n2; typedef Add<n1, n2>::value summ; printf("%i/%i\n", summ::N, summ::D); // 57/160 

We also need a degree and factorial, the definition of which speaks for itself:

 // // Factorial // template<int N> struct Factorial { enum { value = N * Factorial<N - 1>::value }; }; template<> struct Factorial<0> { enum { value = 1 }; }; // // Power // template<int x, int n> struct Pow { enum { value = x * Pow<x, n - 1>::value }; }; template<int x> struct Pow<x, 0> { enum { value = 1 }; }; 

So, now we have the entire set of everything necessary to realize the formula above - it is understandable to summarize, we will not endlessly, but as much as we can, i.e. for example, the expression Exp<4, 8>::value will give a fractional number, which is numerically equal to the exponent to the 4th degree and summation is made only to 8 (infinity near) member inclusive.

The problem arises in that, but how can we sum up fractional numbers that are not even numeric values ​​— these are just types ! Yes, they contain numerical data, but they still need to be reached during the calculation of the sum of the series ... But the solution is and it is that we can get the data (and typedefs - the most important) of the base class from the derived class. Exactly! - to calculate the sum of a series, we will need to be inherited and inherited, and inherited ... ideally to infinity.
A piece of code:

 // // Exponent // template<int x, int n> struct Exp : public Exp<x, n - 1> { private: typedef typename Exp<x, n - 1>::value previous; protected: typedef Fractional<Pow<x, n>::value, Factorial<n>::value> current; public: typedef typename Add<current, previous>::value value; }; template<int x> struct Exp<x, 0> { public: typedef Fractional<Pow<x, 0>::value, Factorial<0>::value> current; public: typedef current value; }; 

current contains the value of one member of the series - i.e. one class in this whole class hierarchy, roughly speaking, is intended to store the value of one member . And with the help of the fact that he can take the data of the base class - that is the value of the previous member of the series - then all this gives us that, apart from the value of one separate element of the series, we in the current class have the sum of the series up to this element (class) inclusive.

And that in the end, but in the end we can proudly write the following:

 int main() { //  typedef Exp<1, 8>::value result; printf("%i/%i\n", result::N, result::D); //   printf("%f\n", result::N / static_cast<float>(result::D)); } 

on a 32 bit machine, no more than 8 row members can be taken - int overflow.

Result : 2.718279 (109601/40320).

Magic :)
Hope you enjoyed it. Thanks for attention.

PS: separately I apologize for the spelling, syntax errors - I was in a drowsy state, bewildered and delighted.