I've been doing a lot of template metaprogramming over the past few years. They can be useful in some circumstances, but when working (playing) with them on my own time it was primarily as 1) a challenge to see how far I could push them (without the compiler dying, as it did when template metaprogramming was proven Turing-complete), and 2) a source of amusement, like Sudoku. Although I'd been following the evolution of the C++14 Standard pretty closely (especially constexpr), for some reason I really didn't give much thought to it when I decided to write a zero-runtime solution for every Project Euler problem. I was just thinking in terms of templates and metaprogramming, rather than thinking about the undertaking as a whole in the context of all the Project Euler problems. Until Problem 2.
Problem 2 is extremely easy: Calculate the sum of all even Fibonacci numbers less than four million. Well, an iterative solution is easy. However, we can't really use an equally straightforward (but less efficient) recursive solution with a depth of 4,000,000 (actually, ~3.52M). After thinking about different ways to accomplish this with template metaprogramming (all of which are essentially ugly workarounds to the fact that all C++ TMP looping basically boils down to recursion of some sort), I decided I would just go the easy route and use the relaxations on constexpr in C++14.
And that was the nail in the coffin for Euler Zero. Initially, simply using constexpr functions felt almost...dirty, like I was cheating. It was just too easy. But after thinking about it, I thought "WTF am I doing wasting my time on template metaprogramming when it's effectively dead, killed by N3652" (more on this in a later post). So, my whole idea about presenting each solution as two files - one I could use as a check for correctness and a zero-runtime TMP solution now seems to me to be a colossal waste of time. With the relaxations on constexpr functions, any problem with parameters, constraints and definitions fixed at compile-time can be expressed as a series of constexpr functions with a zero-runtime solution. No template metaprogramming needed (or wanted).
So while the Project Euler problems may still be interesting or fun to solve in their own right, finding a zero-runtime solution in C++ is no longer of any interest to me whatsoever as a separate challenge: finding a correct solution is by definition a zero-runtime solution if you express it using constexpr. As a bonus, it's a hell of a lot cleaner and easier to understand than an equivalent TMP solution. Just to illustrate the point, soutions for problems 2 and 3 follow. As promised, both solutions will be preceded by a spoiler alert.
I'm not even going to bother posting each solution twice (verification implementation and zero-runtime implementation) - it is exactly the same code for each one. So here's the spoiler alert, for the last time on this blog:
Problem 002
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Solution:
constexpr unsigned SumEvenFibs(const unsigned lim) { unsigned sum = 0; unsigned prev2 = 1; unsigned prev1 = 1; unsigned next = 2; while (prev1 < lim){ if (!(prev1 & 1)){ sum += prev1; } prev2 = prev1; prev1 = next; next = prev1 + prev2; } return sum; } const unsigned long sum = SumEvenFibs(4000000); /* #include <iostream> int main() { std::cout << sum << "\n"; } */
constexpr, expected in GCC 5; expected in VC++ sometime before never "if all goes well"). Use the following command line options:
--std=c++1y -Wall -pedantic -S
The Assembly output window will show:
1 sum: 2 .quad 4613732 # 0x466664
constexpr specifier and uncomment main().
Problem 003
What is the largest prime factor of the number 600851475143 ?
Solution:
constexpr unsigned long LargestPrimeFactor(unsigned long long n) { unsigned long lpf = 0; unsigned long divisor = 2; while (n > 1){ while(0 == (n % divisor)){ if (divisor > lpf){ lpf = divisor; } n /= divisor; } ++divisor; if ((divisor*divisor) > n){ if (n > 1){ if (n > lpf){ lpf = n; } break; } } } return lpf; } const unsigned long lpf = LargestPrimeFactor(600851475143); /* #include <iostream> int main() { std::cout << lpf << "\n"; return 0; } */
The Assembly output window will show:
1 lpf: 2 .quad 6857 # 0x1ac9
Euler Zero, R.I.P.
