C++: Catalan Numbers

Catalan numbers are a sequence of numbers which can be defined directly:

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad\mbox{ for }n\ge 0.$

Or recursively:

$C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;$

Or alternatively (also recursive):

$C_0 = 1 \quad \mbox{and} \quad C_n=\frac{2(2n-1)}{n+1}C_{n-1},$

Implement at least one of these algorithms and print out the first 15 Catalan numbers with each. Memoization is not required, but may be worth the effort when using the second method above.

4 Classes

We declare 4 classes representing the four different algorithms for calculating Catalan numbers as given in the description of the task. In addition, we declare two supporting classes for the calculation of factorials and binomial coefficients. Because these two are only internal supporting code they are hidden in namespace ‘detail’. Overloading the function call operator to execute the calculation is an obvious decision when using C++. (algorithms.h)

#if !defined __ALGORITHMS_H__
#define __ALGORITHMS_H__

namespace rosetta
{
	namespace catalanNumbers
	{
		namespace detail
		{

			class Factorial
			{
			public:
				unsigned long long operator()(unsigned n)const;
			};

			class BinomialCoefficient
			{
			public:
				unsigned long long operator()(unsigned n, unsigned k)const;
			};

		} //namespace detail

		class CatalanNumbersDirectFactorial
		{
		public:
			CatalanNumbersDirectFactorial();
			unsigned long long operator()(unsigned n)const;
		private:
			detail::Factorial factorial;
		};

		class CatalanNumbersDirectBinomialCoefficient
		{
		public:
			CatalanNumbersDirectBinomialCoefficient();
			unsigned long long operator()(unsigned n)const;
		private:
			detail::BinomialCoefficient binomialCoefficient;
		};

		class CatalanNumbersRecursiveSum
		{
		public:
			CatalanNumbersRecursiveSum();
			unsigned long long operator()(unsigned n)const;
		};

		class CatalanNumbersRecursiveFraction
		{
		public:
			CatalanNumbersRecursiveFraction();
			unsigned long long operator()(unsigned n)const;
		};

	}   //namespace catalanNumbers
}     //namespace rosetta

#endif //!defined __ALGORITHMS_H__

In order to test what we have done, a class Test is created. Using the template parameters N (number of Catalan numbers to be calculated) and A (the kind of algorithm to be used) the compiler will create code for all the test cases we need. What would C++ be without templates 😉 (tester.h)

#if !defined __TESTER_H__
#define __TESTER_H__

#include <iostream>

namespace rosetta
{
	namespace catalanNumbers
	{

		template <int N, typename A>
		class Test
		{
		public:
			static void Do()
			{
				A algorithm;
				for(int i = 0; i <= N; i++)
				std::cout<<"C("<<i<<")\t= "<<algorithm(i)<<std::endl;
			}
		};

	} //namespace catalanNumbers
}   //namespace rosetta

#endif //!defined __TESTER_H__

Finally, we test the four different algorithms. Note that the first one (direct calculation using the factorial) only works up to N = 10 because some intermediate result (namely (2n)! with n = 11) exceeds the boundaries of an unsigned 64 bit integer. (catalanNumbersTest.cpp)

#include "algorithms.h"
#include "tester.h"
using namespace rosetta::catalanNumbers;

int main(int argc, char* argv[])
{
	Test<10, CatalanNumbersDirectFactorial>::Do();
	Test<15, CatalanNumbersDirectBinomialCoefficient>::Do();
	Test<15, CatalanNumbersRecursiveFraction>::Do();
	Test<15, CatalanNumbersRecursiveSum>::Do();
	return 0;
}

Output:

(source code is compiled both by MS Visual C++ 10.0 (WinXP 32 bit) and GNU g++ 4.4.3 (Ubuntu 10.04 64 bit) compilers)

Direct calculation using the factorial
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 429
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
Direct calculation using a binomial coefficient
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 428
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
C(11)   = 58786
C(12)   = 208012
C(13)   = 742900
C(14)   = 2674440
C(15)   = 9694845
Recursive calculation using a fraction
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 429
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
C(11)   = 58786
C(12)   = 208012
C(13)   = 742900
C(14)   = 2674440
C(15)   = 9694845
Recursive calculation using a sum
C(0)    = 1
C(1)    = 1
C(2)    = 2
C(3)    = 5
C(4)    = 14
C(5)    = 42
C(6)    = 132
C(7)    = 429
C(8)    = 1430
C(9)    = 4862
C(10)   = 16796
C(11)   = 58786
C(12)   = 208012
C(13)   = 742900
C(14)   = 2674440
C(15)   = 9694845

SOURCE

Content is available under GNU Free Documentation License 1.2.