13,090,519 members (59,766 online)
alternative version

#### Stats

30.1K views
23 bookmarked
Posted 24 Aug 2007

# Template Meta Programming and Number Theory: Part 2

, 24 Aug 2007
 Rate this:
Using C++ language constructs to introduce abstraction layers

## 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.

```// 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 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.

```// return the value of first 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.

```// add two numbers.
// If second value is missing then return the first value
template <int u, int v = 0>
{
enum { value = u + v };
};

// subtract one number from another
// If second value is missing then return the first value
template <int u, int v = 0>
struct Subtract
{
enum { value = u - v };
};

// subtract one number from another
// If second value is missing then return the first value
template <int u, int v = 1>
struct Multiply
{
enum { value = u * v };
};

// divide one number by another
// If second value is missing then return the first value
template <int u, int v = 1>
struct Divide
{
enum { value = u / v };
};

// Modulo operator
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:

```// number of divisor of any positive digit
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:

```// sum of divisor of any positive digit
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:

```// totient function
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.

```// 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.

```// divisor function
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

1. "C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Byond"
by David Abrahams, Aleksey Gurtovoy
2. "Python in a NutShell"
by Alex Martelli
O'Reilly 2003
3. "Re-factoring- Improve The Design of Existing Code"
by Martin Flower
4. "Template Meta Programming and Number Theory"

## History

• 24 August, 2007 -- Original version posted

## About the Author

 Software Developer (Senior) Bloomberg LP United States
Working as a Sr C++ Developer at Bloomberg LP

## Comments and Discussions

 First Prev Next
 Thank you! Windmiller26-Aug-07 1:25 Windmiller 26-Aug-07 1:25
 Thank you for adding one H of a great article! You gave me some new ideas now Regards, Morgan The day I became a WhuShu coder..
 My head asplode! Shawn Poulson24-Aug-07 15:26 Shawn Poulson 24-Aug-07 15:26
 Typo Shmoopty24-Aug-07 14:38 Shmoopty 24-Aug-07 14:38
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Aug-17 18:41 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.