frasnian: Euler Zero: DOA

Well, that didn't take long.

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:

***SPOILER ALERT*** Solution to a Project Euler problem follows: If you have not already done so, read this post before continuing. If you are working through the Project Euler problems and wish to solve them on your own (in C++), you might want to stop reading now if you have any self-respect. You've been given fair notice.

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";
}

*/

Take the code for Problem 2 and paste it into Matt Godbolt's excellent compiler explorer at https://gcc.godbolt.org/. Select "x86 clang 3.4.1" as the compiler (gcc does not yet support relaxations on 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

And there's your (zero-runtime) answer. To compile under gcc or MSVC to verify, just remove the 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;
}
*/

Take the code for Problem 3 and paste it into https://gcc.godbolt.org/ as with Problem 2 (same compiler and options).

The Assembly output window will show:

1  lpf:
2      .quad    6857            # 0x1ac9

Again, there's your answer.

Euler Zero, R.I.P.

Wednesday, February 4, 2015

Euler Zero: DOA