Project Euler 46 solution optimized using C++ meta-programming
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;
}