Introduction
In my previous article, I was trying to implement some basic functions of number theory using the C++ template meta-programming technique [4]. In that article, our main focus was the implementation of different number theory algorithms and functions. Therefore the code written in that article was just proof-of-concept code or, in other words, "First make it work. Then make it right. Then make it fast" [2]. If we take a look at that code more closely, then we can easily figure out some repeated patterns with little modification.
In this article, we are trying to see the implementation from the computer programmer's point of view and trying to use a C++ language construct such as "Template template parameters" [2] to introduce the abstraction layers. This is not only to improve the quality of the code, but also to try to make it more reusable. In other words, we are trying to smell the bad code and re-factor it [3].
Re-factoring
One of the bad code smells defined by Martin Flower is "Duplication Code" [3]. We can quickly figure out duplication loop code with little differences.
template <int Start, int End>
struct NumDivisorsLoop
{
enum { value = Divisible<nd, Start>::value +
NumDivisorsLoop<Start + 1, End>::value };
};
template <int End>
struct NumDivisorsLoop<End, End>
{
enum { value = 1 };
};
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 };
};
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 };
};
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 };
};
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 we have five different algorithms in the form of a loop. All of them share a similar structure, defined in the form of pseudo-code similar to C++.
for (int iIndex = Start; iIndex <= End; ++iIndex)
{
value += SomeFunction();
}
We are trying to make a single structure of this and pass the calling function as a parameter, just like the 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();
}
}
Let's start the process step-by-step. In the first step, we are going to implement the "for loop" with the help of template meta-programming. Then we will try to make it customizable step-by-step. Here is our first step to implementing 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 or reusable with different functions. We may not add the value of variables blindly. Instead of this, we might want to do some comparisons such as divisibility, check for co-prime, etc. before adding. In non-template meta-programming based code, we might add one more parameter to the function. This can be a function object or function pointer to perform the comparison, just like the predicate of STL.
In the meta-programming world, we can do the same thing with the help of the "template template parameter." Here we are going to add one more parameter to the template-based structure. The type of the new parameter is "template template parameter."
template <int Start, int End, int Exp,
template<int u, int v> class BiFun>
struct ForLoop
{
enum { value = BiFun<Start, End>::value
+ ForLoop<Start + Exp, End, Exp, BiFun>::value };
};
template <int End, int Exp,
template<int u, int v> class BiFun>
struct ForLoop<End, End, Exp, BiFun>
{
enum { value = BiFun<End, End>::value };
};
We select the name of the parameter as BiFun because this will work as a function that will take two parameters. Here we cannot set the default value of Exp equal to one, like we did in previous example, because the next template parameter that is equivalent to a function object does not have a default value. We can make a small template-based utility class to set the default value of the last parameter.
template <int u, int v>
struct Value
{
enum { value = u };
};
Although we are using only one parameter in this structure, we still need to pass two parameters because the ForLoop template expects the two parameters of BiFun. We could use this structure as a default value of the last parameter of the ForLoop structure. It would become something like this.
template <int Start, int End, int Exp = 1,
template<int u, int v> class BiFun = Value>
struct ForLoop
{
enum { value = BiFun<Start, End>::value
+ ForLoop<Start + Exp, End, Exp, BiFun>::value };
};
template <int End, int Exp,
template<int u, int v> class BiFun>
struct ForLoop<End, End, Exp, BiFun>
{
enum { value = BiFun<End, End>::value };
};
And here is the usage of it.
cout << ForLoop<1, 5>::value << endl;
cout << ForLoop<1, 9, 2, Value>::value << endl;
This is a pretty basic form of for loop with lots of restrictions, such as it can traverse only in ascending order. We know that for loops can be traversed in reverse (descending) order, but here we hard-coded the operation in the form of Start + Exp. We can overcome this situation by introducing another "template template parameter" (in other words, another function object) to control the direction of the loop. Of course, we need a few more utility structures for some basic math structures. Here are our few basic mathematical operators.
template <int u, int v = 0>
struct Add
{
enum { value = u + v };
};
template <int u, int v = 0>
struct Subtract
{
enum { value = u - v };
};
template <int u, int v = 1>
struct Multiply
{
enum { value = u * v };
};
template <int u, int v = 1>
struct Divide
{
enum { value = u / v };
};
template <int u, int v>
struct Mod
{
enum { value = u % v };
};
Why do we need to create wrappers on these basic operations? Because we can pass the structure as a template parameter, but we can't pass the operator. Now our for loop structure will look like this.
template <int Start, int End, int Exp = 1,
template <int u, int v> class ExpOperator = Add,
template<int u, int v> class BiFun = Value>
struct ForLoop
{
enum
{
value =
BiFun<Start, End>::value +
ForLoop<ExpOperator<Start, Exp>::value, End, Exp,
ExpOperator, BiFun>::value
};
};
template <int End, int Exp,
template <int u, int v> class ExpOperator,
template<int u, int v> class BiFun>
struct ForLoop<End, End, Exp, ExpOperator, BiFun<
{
enum { value = BiFun<End, End>::value };
};
We can traverse it in both the forward and reverse directions.
cout << ForLoop<1, 9, 2, Add, Value>::value << endl;
cout << ForLoop<16, 1, 3, Subtract, Value>::value << endl;
Before moving back to our topic of number theory algorithms, take a look at the last piece of the for loop structure. In all of our for loop examples, we add the value with whatever is returned by the "template template parameter" (function object). Let's add another parameter to make it generalize, so the user can not only add the values, but perform other operations too.
template <int Start, int End, int Exp = 1,
template <int u, int v> class ExpOperator = Add,
template <int u, int v> class Operator = Add,
template <int u, int v> class BiFun = Value>
struct ForLoop
{
enum
{
value =
Operator<BiFun<Start, End>::value,
ForLoop<ExpOperator<Start, Exp>::value, End, Exp,
ExpOperator, Operator, BiFun>::value>::value
};
};
template <int End, int Exp,
template <int u, int v> class ExpOperator,
template <int u, int v> class Operator,
template <int u, int v> class BiFun>
struct ForLoop<End, End, Exp, ExpOperator, Operator, BiFun>
{
enum { value = BiFun<End, End>::value };
};
This for loop structure became quite horrible, but we can customize each and every piece of it by its parameters. Here are a few examples of its usage.
cout << ForLoop<-5, 7, 2, Add, Multiply, Value>::value << endl;
cout << ForLoop<16, 1, 3, Subtract, Add, Value>::value << endl;
Here is the pseudo-code of these statements.
value = 1;
for (int iIndex = -5; iIndex < 7; iIndex += 2)
{
value *= iIndex;
}
value = 1;
for (int iIndex = 16; iIndex > 1; iIndex -= 3)
{
value += iIndex;
}
Number Theory Functions
In this section, we are going to re-implement the number theory algorithms with the help of the new tools we just created. Instead of repeating all the code of the previous article, here we are going to discuss only those number theory functions that use for loops.
Numbers of Factors
Every positive integer has one or more positive factors. In fact, all integers other than 1 have at least two factors: one and that number itself. For example "12" has 6 factors: 1, 2, 3, 4, 6 and 12. We can define an arithmetic function t(n) to be the number of factors of n, where n is a positive integer. Mathematically, we can write it as:
template <int n>
struct NoOfDivisor
{
enum { value = ForLoop<1, n, 1, Add, Add, Divisible>::value };
};
Sum of Divisor (Sigma Function)
The Simga function is similar to the number of divisors function. The only difference is that instead of counting the number of factors, we sum all the factors of a given number. Mathematically, it can be written as:
template <int n>
struct SumOfDivisor
{
enum { value = ForLoop<1, n, 1, Add, Add, DivisibleDigit>::value };
};
Totient Function
The Totient function, also known as the Phi function and Euler's Totient function, is defined as the number of positive integers less than or equal to the given number and the co-prime of it. For example, Phi (9) = 6 because 1, 2, 4, 5, 7 and 8 are co-prime of 9 and Phi (11) = 10 because 11 is a prime number and it is co-prime of all the numbers less than itself. Mathematically, Totient functions can be written as:
From the definition of the Totient function, if "p" is a prime number then:
template <int n>
struct Totient
{
enum { value = ForLoop<1, n, 1, Add, Add, CoPrime>::value };
};
Totient Summatory Function
The Totient Summatory function returns the sum of all the Totient function values less than or equal to the given number. Mathematically, it can be written as:
Or
We cannot simply pass the Totient structure in ForLoop as a parameter because ForLoop accepts only those structures that take two parameters. We can solve this solution in two ways, either by adding one dummy parameter in the Totient structure, just like we did for the Value structure, or create a wrapper on the top of it with one extra parameter. Here we create a wrapper of the Totient structure.
template <int n, int v = 0>
struct TotientVal
{
enum { value = Totient<n>::value };
};
Now it is very easy to create a structure for the Totient Summatory function.
template <int n>
struct TotientSummatory
{
enum { value = ForLoop<1, n, 1, Add, Add, TotientVal>::value };
};
The purpose of selecting TotientSummatory is to demonstrate nested for loops, as well as show an example of when a function takes only one parameter. We have to run two nested for loops to calculate the value of the TotientSummatory function.
Divisor Function
The Divisor function is a generalized form of the Sigma function. In other words, the Sigma function is a special case of the Divisor function. It is defined as the sum of the xth power of the positive divisor of a given number "n." Mathematically, it can be written as:
The Divisor function is different from other functions. In the case of the Totient Summatory function, we came across one parameter structure, but here we are supposed to pass three parameters. We cannot pass that function directly into the ForLoop structure because ForLoop accepts a function object with only two parameters. We can solve this problem with the help of a nested structure.
template <int n, int x>
struct Divisor
{
template <int Start, int End>
struct DivisorPow
{
enum
{
value =
Divisible<Start, End>::value ==
1 ? Power<Start, x>::value : 0
};
};
enum { value = ForLoop<1, n, 1, Add, Add, DivisorPow>::value };
};
Here we re-implemented all the number theory algorithms in the STL predicate way. Instead of one large header file, I divide the code into three header files containing mathematical functions, control structures and implementations of number theory algorithms, respectively, for better organization.
References
- "C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Byond"
by David Abrahams, Aleksey Gurtovoy
Addison Wesley, 2004 - "Python in a NutShell"
by Alex Martelli
O'Reilly 2003 - "Re-factoring- Improve The Design of Existing Code"
by Martin Flower
Addison Wesley, 1999 - "Template Meta Programming and Number Theory"
by Zeeshan Amjad
History
- 24 August, 2007 -- Original version posted
