Saturday, March 26, 2011 and C++ meta-programming

I was introduced to 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...


Unknown said...

casino, poker room, blackjack, bingo
casino, poker room, blackjack, bingo communitykhabar room, blackjack, bingo room, poker room, poker 출장샵 room, poker room, poker room, poker titanium ring room, poker room,

Post a Comment