# Template Recursion

This topic is 4890 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've been playing with template recursion to compute constants at compile time. I have successfully implemented a factorial based one. I was trying to write one that computed e. e is defined as 1 + 1/1! + 1/2! + 1/3! + 1/n! So I tried
namespace KS
{
namespace Math
{
template <unsigned int Limit, typename T>
struct E
{
//static const T	result;
};

template <unsigned int Limit>
struct E <Limit, float>
{
static const float	result;
};
template <>
const float E <0, float>::result = 1.0f;
//  Assume that KS::Math::Factoral does return a succesful factorial, which tests show that it does
template <unsigned int Limit>
const float E <Limit, float>::result = ((KS::Math::E<(Limit - 1), float>::result) + (1.0f / KS::Math::Factorial<(Limit)>::result));
}
}


	//  Here is my test code
std::cout << KS::Math::E<0, float>::result << std::endl;
std::cout << KS::Math::E<1, float>::result << std::endl;
std::cout << KS::Math::E<2, float>::result << std::endl;
std::cout << KS::Math::E<6, float>::result << std::endl;


Here is the result of the code. 1 (This would be doing 1 which would be a straight constant, so corect) 2 (This should be 1/1! + 1, so again correct. Note that if I didn't actually put the std::cout << KS::Math::E<0, float>::result << std::endl; before it, it resolves to just 1, which would just be 1/1!) 2.5 (This should be 1/2! + 1/1! + 1, so again correct. Note that if I didn't actually put the std::cout << KS::Math::E<0, float>::result << std::endl; & std::cout << KS::Math::E<1, float>::result << std::endl; before it, it resolves to just 0.5, which would just be 1/2!) 0.00138889 (This is just resolving to 1/6!, instead of doing any of the recursion, as the above 3 show, I would guess that if I manually do E<3>, E<4>, & E<5> before it, they would all resolve correctly. So what it looks like it is doing is if a E<some number, float> is on its own, it just does the 1 / some number! math. If all of the neccessary calculations are predefined before it is needed, it is successfully solving for it. Is there just a problem with my logic somewhere? Note: You can't go higher than E<12, float>, because the factorial would overflow an int.  This is all purely academic. So please, do not recommend using someone else's libraries ala boost or just using a constant. [/edit]

##### Share on other sites
I get the same behavior if I don't use the previous precisions.

This is my code (compiled with VC++.NET 2003):
// factorial.h -----------------------------------------------------#pragma oncenamespace Test {	template< unsigned i > struct factorial {		static const unsigned int result = i * Test::factorial< i - 1 >::result;	};	template<> struct factorial< 1 > {		static const unsigned int result = 1;	};	template<> struct factorial< 0 > {		static const unsigned int result = 1;	};}// e.h ------------------------------------------------------------#pragma once#include "factorial.h"namespace Test {	template< unsigned int precision > struct e {		static const float result;	};	template< unsigned int precision >	const float e< precision >::result =		Test::e< precision - 1 >::result + 			( 1.0f / Test::factorial< precision >::result );	template<> struct e< 0 > {		static const float result;	};	const float e< 0 >::result = 1.0f;}// main.cpp --------------------------------------------------------#include <iostream>#include <iomanip>#include "factorial.h"#include "e.h"using std::cout;using std::endl;int main() {	cout.precision( 20 );	cout << Test::factorial< 4 >::result << endl;	cout << Test::e< 1 >::result << endl		<< Test::e< 2 >::result << endl		<< Test::e< 3 >::result << endl		<< Test::e< 4 >::result << endl;	return 0;}

The result is:
2422.52.66666674613952642.7083334922790527

Which seems fine.

If I remove the first three Test::e templates, I get this:
240.041666667908430099

So, the same problem, it is only doing 1 / precision!.

I too would be interested in an academic solution.

 slight changes to code
[edit2] Tested on:
G++ 3.2.3 - same problem
G++ 3.4.4 - works

jfl.

[Edited by - jflanglois on September 1, 2005 12:15:59 AM]

##### Share on other sites
#include <iostream>namespace Test {        template< unsigned i > struct factorial {                static const float result = i*Test::factorial< i - 1 >::result;        };        template<> struct factorial< 1 > {                static const float result = 1;        };        template<> struct factorial< 0 > {                static const float result = 1;        };        template <unsigned int Limit>        struct E        {                static const float      result;        };        template <> const float E <0>::result = 1.0f;        template <unsigned int Limit> const float E <Limit>::result = ((E<(Limit - 1)>::result) + (1.0f / factorial<(Limit)>::result));}int main(){        std::cout << Test::E<1>::result << std::endl;        std::cout << Test::E<3>::result << std::endl;        std::cout << Test::E<6>::result << std::endl;        std::cout << Test::E<20>::result << std::endl;        std::cout << Test::E<25>::result << std::endl;        return 0;}

Gives me the following output:
2
2.66667
2.71806
2.71828
2.71828

This is with
powerpc-apple-darwin8-g++-4.0.0 (GCC) 4.0.0 20041026 (Apple Computer, Inc. build 4061) compiled.

##### Share on other sites
I tested it with gcc in cygwin with 3.4.4. And it looks like it resolves correctly. So this looks like a problem with Visual C++ (I am currently compiling it in VS2005 beta 2).

Thanks for the help guys.

##### Share on other sites
Just for an update, here is the official answer from Microsoft

Quote:
 Resolved as Postponed by Microsoft on 2005-09-02 at 09:18:22 The order of initialization of static data members of class templates is not defined by the standard. Please refer to section 3.6.2 of the standard. You can also examine the DR link below:http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#270The implementation does not require us to deal with this, and our compiler does not. We are not in the position that we can examine such a change for the current ship cycle, as we are only taking critical fixes. We will reexamine this after VC2005 ships.For managed classes, the order is well defined and will produce the desired results.Thank You,Dean WillsVisual C++ Team.

##### Share on other sites
template<bool TemplateTricksAreSilly>struct E{    static const float result;};template<>const float E<true>::result = 2.718281828f;

[grin]

##### Share on other sites
I just have to be a smart ass.

Quote:
 Original post by RattrapThis is all purely academic. So please, do not recommend using someone else's libraries ala boost or just using a constant.

And besides wouldn't you want to do this

template<bool TemplateTricksAreSilly>struct E{    static const float result;};template<bool TemplateTricksAreSilly>const float E<TemplateTricksAreSilly>::result = 2.718281828f;ortemplate<bool TemplateTricksAreSilly = true>struct E{    static const float result;};template<>const float E<true>::result = 2.718281828f;template<>const float E<false>::result = 2.718281828f;

##### Share on other sites
I don't think it's semantically valid to set TemplateTricksAreSilly=false. [wink]

##### Share on other sites
You can do it using function calls. In a release build this will be optimized away to loading a floating point constant for each value of limit (I checked):

#include "stdafx.h"using namespace std;template<int n>class factorial{public:    static const int value = n * factorial<n - 1>::value;};template<>class factorial<0>{public:    static const int value = 1;};template<int limit>class e{public:    static double value()    {        return e<limit - 1>::value() + double(1) / double(factorial<limit>::value);    }};template<>class e<0>{public:    static double value()    {        return double(1);    }};int _tmain(int , _TCHAR* []){    cout << factorial<5>::value << endl;    cout << e<0>::value() << endl;    cout << e<1>::value() << endl;    cout << e<2>::value() << endl;    cout << e<3>::value() << endl;    cout << e<4>::value() << endl;    cout << e<5>::value() << endl;    cout << e<6>::value() << endl;    cout << e<7>::value() << endl;    cout << e<8>::value() << endl;    cout << e<9>::value() << endl;    return 0;}

##### Share on other sites
Yeah, I have gotten a version that would work that did involve function calls. Also just for a test, it is actually bad to do the e<x> in order, but it did work if you did 0,1,2,3,4,5,6,7 in a row, just not a value by itself (if a recursive call was needed).

And actually, it is even optimized away to a constant in debug. That is one of the cool things about these "Silly Template Tricks" :) Templates are resolved at compile-time, not at runtime.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 10
• 9
• 34
• 16
• ### Forum Statistics

• Total Topics
634125
• Total Posts
3015668
×