Template Meta Programming and Number Theory, Part 2

1. Introduction

In my previous article, I tried to implement some basic functions of number theory using C++ template Meta programming technique [4]. In that article, the main focus was the implementation of different number theory algorithms and functions; therefore, the code written in that article was just a proof of concept code or, in other words, “First, make it work. Then, make it right. Then, make it fast” [2]. If you look at that code more closely, you easily can figure out some repeated patterns with little modification. In this article, you are trying to see the implementation from a computer programmer’s point of view and use the C++ language construct such as “Template template parameters” [2] to introduce the abstraction layers not only to improve the quality of code but also to make it more reusable. In other words, you are trying to find the bad code and re-factor it [3].

2. Re-factoring

One definition of bad code is defined by Martin Flower as “Duplication Code” [3]. You can quickly figure out the duplication loop code with a little bit of difference.


// loop for total no of divisors
template <int Start, int End>
struct NumDivisorsLoop
{
enum { value = Divisible<nd, Start>::value +
NumDivisorsLoop<Start + 1, End>::value };
};

// partial specialization to terminate loop
template <int End>
struct NumDivisorsLoop<End, End>
{
enum { value = 1 };
};

// loop for sum of divisor
template <int Start, int End>
struct SumOfDivisorLoop
{
enum { value = DivisibleDigit<End, Start>::value +
SumOfDivisorLoop<Start + 1, End>::value };
};

template <int End>
struct SumOfDivisorLoop<End, End>
{
enum { value = DivisibleDigit<End, End>::value };
};

// helper template loop for calculate totient function
template <int Start, int End>
struct TotientLoop
{
enum { value = CoPrime<Start, End>::value + TotientLoop<Start +
1, End>::value };
};

template <int End>
struct TotientLoop<End, End>
{
enum { value = 0 };
};

// totient summatory function loop
template <int Start, int End>
struct TotientSummatoryLoop
{
enum { value = Totient<Start>::value +
TotientSummatoryLoop<Start + 1, End>::value };
};

template <int End>
struct TotientSummatoryLoop<End, End>
{
enum { value = Totient<End>::value };
};

// loop for divisor function
template <int Start, int End, int x>
struct DivisorLoop
{
enum { value = (Divisible<End, Start>::value == 1 ?
Power<Start, x>::value : 0) +
DivisorLoop<Start+1, End, x>::value };
};

template <int End, int x>
struct DivisorLoop<End, End, x>
{
enum { value = Power<End, x>::value };
};

Here you have five different algorithms in the form of loop. All of them share a similar structure define in the form of pseudo code, similar to C++.


for (int iIndex = Start; iIndex <= End; ++iIndex)
{
value += SomeFunction();
}

You are trying to make a single structure of this and pass the calling function as a parameter, just like a predicate (function object, or function pointer) of STL. Its pseudo code might be something like this.


void fun(int Start, int End, int Inc, Fun FunctionObject)
{
for (int iIndex = Start, iIndex <= End; ++iIndex)
{
value += FunctionObject();
}
}

Now, start the process step by step. In the first step, you will implement the “for loop” with the help of template meta-programming and then try to make it customizable. Here is your first step to implement the “for” loop.


template <int Start, int End, int Exp = 1>
struct ForLoop
{
enum { value = Start + ForLoop<Start + Exp, End, Exp>::value };
};

template <int End, int Exp>
struct ForLoop<End, End, Exp>
{
enum { value = End };
};

This meta-program is something similar to the following C++ function.


int ForLoop(int Start, int End, int Exp = 1)
{
int retValue = 0;

for (int iIndex = Start; iIndex <= End; iIndex += Exp)
{
retValue += iIndex;
}

return retValue;
}

Here are a few examples to demonstrate the usage of this structure.


cout << ForLoop<3, 9, 2>::value << endl;
cout << ForLoop<1, 10>::value << endl;

This code is still not very useful and reusable with different functions. You might not add the value of variables blindly; instead, you might want to do some comparison, such as divisibility, check for co-prime, and so forth before adding. In non-template meta-programming-based code, you might add one more parameter to the function that can be a function object or function pointer do perform the comparison (just like the predicate of STL).

More by Author

Previous articleProject Estimation Geometry
Next articleSqlProcessor

Must Read