*Full disclosure: if the potential payout gets large enough, I might occasionally buy a ticket
constexpr functions introduced in C++14.
I recently picked up a problem a colleague pointed out to me last year and as it turned out to be from Project Euler, I decided to try to create a zero-runtime version after I came up with a correct solution. It is more challenging than I expected, so I may be doing the occasional Euler Zero solution after all.
Euler Zero code and wiki are now in a GitHub repository, at https://github.com/frasnian/euler-zero. Any solutions will be linked from here, but for the most part, code will be in the repository and commentary will be in the accompanying repo wiki.
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().
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.
Problem 001
The first problem is simple: calculate the sum of all multiples of 3 or 5 less than 1000. Time for some template metaprogramming, as this can be solved in a fairly straightforward way with simple template recursion.
The first thing to do is calculate the correct answer, for verification of the minimal runtime solution.
For a problem this basic, it's simply:
euler001-poc.cpp:
#include <iostream> // using a const int here instead of hard-coding in the for loop // so you can change it to 10 and verify against the example on // the project page (or change it to whatever if Project Euler // changes the parameters of the problem). const int limit = 1000; int main() { int sum = 0; for (int i = 3; i < limit; i++){ if ( ((i % 3) == 0) || ((i % 5) == 0)){ sum += i; } } std::cout << "Sum = " << sum << "\n"; return 0; }
Not surprisingly, the template-based solution is also fairly simple:
euler001-opt.cpp:
#include <iostream> const int term = 2; // counting backwards from limit-1 to 3, inclusive const int limit = 1000; // same reason as proof-of-correctness version template<int i> struct PrevMultiple { enum { sum = (((i % 3) == 0) || ((i % 5) == 0) ? i : 0) + (PrevMultiple<i - 1>::sum) }; }; template<> struct PrevMultiple<term> { enum { sum = 0 }; }; int main() { std::cout << "Sum = " << PrevMultiple<limit-1>::sum << "\n"; return 0; }
Instead of using a loop, we count backwards by recursing until we reach the explicit specialization for 2 (which does not itself recurse, thereby ending the cycle). Alternatively, we could have counted up to 1000 instead.
One interesting thing that came up in this problem was that Visual C++ can not compile it because it has a hard-coded limit to the depth of template recursion. You have to use gcc to compile it, with:
gcc -std=c++03 -Wall -pedantic -ftemplate-depth=1000 -lstdc++ -o euler001-opt euler001-opt.cpp
Note that it doesn't even require C++11, although even using gcc the -ftemplate-depth=1000 is the key to getting this to compile without hitting a default limit on template recursion (VC++ has no such option). To see the actual runtime cost, you can look at the generated assembly code with:
gcc -std=c++03 -Wall -pedantic -ftemplate-depth=1000 -S -masm=intel euler001-opt.cpp
This shows us that main() looks like this (the assembly source will be in euler001-opt.s):
main:
.LFB1196:
.cfi_startproc
push rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
mov rbp, rsp
.cfi_def_cfa_register 6
mov esi, OFFSET FLAT:.LC0
mov edi, OFFSET FLAT:_ZSt4cout
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
mov esi, 233168
mov rdi, rax
call _ZNSolsEi
mov esi, OFFSET FLAT:.LC1
mov rdi, rax
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
mov eax, 0
pop rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
As you can see from the line in blue, the template recursion results in an integer literal (a constant) that the compiler has been forced to calculate for us at compile time. The rest of the assembly code is fluff related to using std::cout to display the result.
Total runtime cost: zero
Each solution will have two variants - a proof-of-correctness version ("POC"), and the zero-runtime solution ("OPT") we can check against it. I do not plan on spending any time whatsoever trying to optimize the proof version. I do not care if the POC version is slow - the goal is simply to obtain a correct answer we can use as a check on the result of the optimal version, so I am not going to spend any time trying for a faster or more "elegant" solution. I'd rather aim for as much simplicity as possible, as I anticipate a zero-runtime solution for some of the later problems could get a bit... complex. If the zero-runtime solution uses a somewhat suboptimal method to generate the result, it doesn't even matter because everything is calculated before the program is ever run.
But before I get to that:
After doing the first problem, I had a dilemma. The Project Euler web site asks that people not post the correct answer (or their solution), so that others may enjoy the challenge (paraphrasing). While on the one hand I understand (and respect) their request, on the other hand there are entire sites dedicated to publishing solutions and answers for Project Euler problems.
In the end, I decided the cat was already out of the bag, so I'll be posting my solutions. If someone genuinely wants to solve a given Project Euler problem on their own, they won't just google for the answer anyway. I will be prefacing each post that contains a solution to a Project Euler problem with a spoiler alert notice, so anyone actually working through the problems on their own shouldn't have anything ruined for them.
All that being said, I'll reiterate that the theoretical minimum run-time for anything is zero. So that's the goal: a zero-run-time solution to each problem from Project Euler.
Welcome to Euler Zero. Posts will be labeled accordingly.