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

Template Meta Programming and Number Theory, Part 2

In the meta-programming world, you can do the same thing with the help of a "template template parameter." Here, you are going to add one more parameter to the template-based structure and 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 };
};

You select the name of the parameter, "BiFun", because this will work as a function that will take two parameters. Here, you cannot set the default value of Exp equal to one, just as you did in previous example, because the next template parameter (that is equivalent to a function object) does not have a default value. You 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 you are using only one parameter in this structure, you still need to pass two parameters because the ForLoop template expects two parameters of BiFun. You can use this structure as a default value of the last parameter of the LorLoop structure and 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 pretty basic form of the for loop with lots of restrictions such as it can traverse only in ascending order. You know that the for loop can be traversed in reverse (descending) order, but here you hard-coded the operation in the form of "Start + Exp". You 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, you need few more utility structures for some basic math structures. Here are your few basic mathematical operators.

// add two numbers.
// If second value is missing then return the first value
template <int u, int v = 0>
struct Add
{
   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 you need to create a wrapper on these basic operations? Because you can pass the structure as a template parameter, but you can't pass the operator. Now your "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 };
};

And you can traverse it in both 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 the topic of number theory algorithms, take a look at the last piece of the for loop structure. In all of your for loop example, you add the value with whatever is returned by the "template template parameter" (function object). Add another parameter to make it generalized, so that theuser 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 you 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;
}

Template Meta Programming and Number Theory, Part 2

3. Number Theory Functions

In this section, you are going to re-implement the number theory algorithms with the help of the new tools you just created. Instead of repeating all the code of the previous article, here you only are going to learn about those number theory functions that use the for loop.

3.1. 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. You can define an arithmetic function t(n) such as number of factors of n where n is a positive integer. Mathematically, you can write it in this manner.

// number of divisor of any positive digit
template <int n>
struct NoOfDivisor
{
   enum { value = ForLoop<1, n, 1, Add, Add, Divisible>::value };
};

3.2. Sum of Divisor (Sigma function)

The simga function is similar to the number of divisor function; the only difference is that, instead of counting the number of factors, you sum all the factors of a given number. Mathematically, it can be written as this:

// sum of divisor of any positive digit
template <int n>
struct SumOfDivisor
{
   enum { value = ForLoop<1, n, 1, Add, Add,
          DivisibleDigit>::value };
};

3.3. 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 Coprime of it. For example, phi (9) = 6 because 1, 2, 4, 5, 7, and 8 are CoPrimes of 9 and phi (11) = 10 because 11 is a prime number and it is the CoPrime of all the numbers less than itself. Mathematically, the Totient function be written as:

From the definition of the totient function, if "p" is prime number,

// totient function
template <int n>
struct Totient
{
   enum { value = ForLoop<1, n, 1, Add, Add, CoPrime>::value };
};

3.4. Totient Summatory Function

The totient Summatory function returns the sum of all the totient functions values less than or equal to the given number. Mathematically, it can be written as:

Or

You cannot simply pass the "Totient" structure in the "ForLoop" as a parameter because "ForLoop" accepts only those structures that take two parameters. You can solve this solution in two ways, either add one dummy parameter in the "Totient" structure just as you did for the "Value" structure or create a wrapper on the top of it with one extra parameter. Here, you 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 "Totient Summatory Function" is to demonstrate the nested for loop as well as show an example when the function takes only one parameter. You have to run two nested for loops to calculate the value of the "Totient Summatory Function".

3.5. Divisor Function

The divisor function is a generalized form ofthe sigma function; in other words, the sigma function is a special case of the divisor function. It is defined as the sum of xth power of the positive divisor of given number "n". Mathematically, it can be written as:

The divisor function is also different from other functions. In the case of Totient Sumaatory function, you came across one parameter structure, but here you need are suppose to pass three parameters. You cannot pass that function directly into the "ForLoop" structure because the "ForLoop" accepts a function object with only two parameters. You can solve this problem with the help of 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, you re-implemented all the number theory algorithms in an STL predicate way. Instead of one large header file, I divide the code into three header files containing mathematical functions, control structure, and the implementation of the number theory algorithm respectively for better organization.

4. References

  1. C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Beyond. David Abrahams and Aleksey Gurtovoy. Addison Wesley, 2004.
  2. Python in a NutShell. Alex Martelli. O'Reilly, 2003.
  3. Re-factoring- Improve The Design of Existing Code. Martin Flower. Addison Wesley, 1999
  4. Template Meta Programming and Number Theory.Zeeshan Amjad. http://www.codeproject.com/cpp/meta_programming.asp and http://www.codeguru.com/cpp/misc/misc/math/article.php/c14087/.


About the Author

Zeeshan Amjad

C++ Developer at Bechtel Corporation. zamjad.wordpress.com

Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Today's agile organizations pose operations teams with a tremendous challenge: to deploy new releases to production immediately after development and testing is completed. To ensure that applications are deployed successfully, an automatic and transparent process is required. We refer to this process as Zero Touch Deployment™. This white paper reviews two approaches to Zero Touch Deployment--a script-based solution and a release automation platform. The article discusses how each can solve the key …

  • Learn How A Global Entertainment Company Saw a 448% ROI Every business today uses software to manage systems, deliver products, and empower employees to do their jobs. But software inevitably breaks, and when it does, businesses lose money -- in the form of dissatisfied customers, missed SLAs or lost productivity. PagerDuty, an operations performance platform, solves this problem by helping operations engineers and developers more effectively manage and resolve incidents across a company's global operations. …

Most Popular Programming Stories

More for Developers

RSS Feeds