## Saturday, March 26, 2011

### projecteuler.net and C++ meta-programming

I was introduced to projecteuler.net at a recent Guelph Coffee & Code meeting. The concept's quite simple: math problems of increasing difficulty to be solved using your programming language of choice. Sounds fun, no? We had a look at the first problem on the list:
Add all the natural numbers below one thousand that are multiples of 3 or 5.

On the walk home, I found myself thinking about the problem and I wondered if it would be possible to use C++ template meta-programming to obtain the solution at compile time. Here's what I came up with:

`template< int n >struct sum_integers_up_to{  static const int result =    (n * (n + 1)) / 2;};template< int upper_limit, int x >struct sum_multiples{  static const int result =    x * sum_integers_up_to< (upper_limit - 1)/ x >::result;};template< int upper_limit, int x, int y >struct sum_two_multiples{  static const int sum_of_multiples_of_x =    sum_multiples< upper_limit, x >::result;  static const int sum_of_multiples_of_y =    sum_multiples< upper_limit, y >::result;  static const int sum_of_multiples_of_xy =    sum_multiples< upper_limit, x*y >::result;  static const int result =    sum_of_multiples_of_x + sum_of_multiples_of_y - sum_of_multiples_of_xy;};int main(){  return sum_two_multiples< 1000, 3, 5 >::result;}`

Having a look at the assembly code generated by MSVC, we see that it's about as minimal as it gets (spoiler alert!):
`_main   PROC        mov     eax, 233168        ret     0_main   ENDP`

One down, 328 to go...