binomial numbers "n over k" in C++ with a template.

#ifndef BINOMIAL_HPP_INCLUDED #define BINOMIAL_HPP_INCLUDED template<int n, int k> struct Binomial { const static int value = (Binomial<n-1,k-1>::value + Binomial<n-1,k>::value); }; template<> struct Binomial<0,0> { const static int value = 1; }; template<int n> struct Binomial<n,0> { const static int value = 1; }; template<int n> struct Binomial<n,n> { const static int value = 1; }; template<int n, int k> inline int binomial() { return Binomial<n,k>::value; } #endif

Now let's try it with a short main:

#include "Binomial.hpp" #include <iostream> int main() { std::cout << "30 over 15: " << binomial<30,15>() << std::endl; return 0; }

30 over 15: 155117520It works! When it will break depends on your compiler. I used g++ 4.6.2

It works only for constants. Trying to pass variables causes compile error.

ReplyDeleteyes of course!

ReplyDeleteThat's how template metaprogramming works: it shifts computation from runtime to compile time. A variable's value is unknown during compilation.

The purpose of a program like this is that you could write

binomial in your code instead of, say 155117520,

(x,y being constants) and the compiler will generate that constant for you.

If you want runtime binomials, you would write a simple (unless you need to deal with real big numbers) function instead

it should read

ReplyDeletebinomial <x,y>()

not binomial, sorry

You are right, I ended up writing simple recursive function (I only need binomials of small degree).

ReplyDelete