Project Euler 46 solution optimized using C++ meta-programming

3082 ワード

Continued with last post.. now I'm using C++ meta-programming to solve this problem - all computation moved to compile time.
But there are limitations for G++ to compile template like recursion depth limitation and greediness... Please find comments below to get more details.
/*
	Works with following g++ commands by G++ 4.8.1
	
	g++ -g -c riddle_meta.cpp -std=c++11 -ftemplate-depth=3000
	g++ -o riddle_meta.exe riddle_meta.o -pg
 */
#include 
using namespace std;

#define MID(a, b) ((a+b)/2)
#define POW(a) (a*a)

//	Calculate Square Root using binary search
//
template 
class SQRT 
{
   static const int mid = MID(r, l);
   static const int mid_pow = POW(mid);
   static const int nl = mid_pow >= v ? l : mid + 1;
   static const int nr = mid_pow >= v ? mid : r;
public:
   static const int value = SQRT::value;
};

template
class SQRT;

template
class SQRT 
{
public:
   static const int value = r;
};

//	Perfect Square Checking
//
template
class PSQRT
{
	static const int sqrt = SQRT::value;
public:
	static const bool value = (sqrt * sqrt) == VAL;
};

//	Prime Number Checking
//
template
class PRIME
{
public:
	static const bool value = (VAL % DIV == 0) ? false : PRIME::value;
};
template
class PRIME
{
public:
	static const bool value = VAL % 2 == 1;
};
template
class PRIME
{
public:
	static const bool value = VAL % 3 != 0;
};

//	Goldbach other Conjecture Checking
//
template
class Goldbach
{
	static const int next_odd = (P%2)?(P-2):(P-1);
public:
	static const bool value = (!PRIME

::value>::value) ? Goldbach::value: // if P is not prime, we try next odd number (PSQRT::value ? true: (Goldbach::value) ); }; template class Goldbach { public: static const bool value = PSQRT::value; }; template class Goldbach { public: static const bool value = PSQRT::value; }; template<> class Goldbach<3, 1> { public: static const bool value = true; }; // Main Loop: check odd numbers one by one, starting from VAL // template class Driver { public: // HACK: With primality checking expression enabled, G++ suffers from out of memory error. static const int value = ( /*(!PRIME::value) ||*/ Goldbach::value) ? (Driver::value) : VAL; }; // HACK: G++ doesn't initialize template lazily, so there must be an ending criteria for upper-bound template<> class Driver<5801> { public: static const int value = 5801; }; // int main() { // HACK: there's memory limitation when G++ compiles templates std::cout << Driver<5651>::value << endl; return 0; }