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

  • Live Event Date: December 11, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT Market pressures to move more quickly and develop innovative applications are forcing organizations to rethink how they develop and release applications. The combination of public clouds and physical back-end infrastructures are a means to get applications out faster. However, these hybrid solutions complicate DevOps adoption, with application delivery pipelines that span across complex hybrid cloud and non-cloud environments. Check out this …

  • With the average hard drive now averaging one terabyte in size, the fallout from the explosion of user-created data has become an overwhelming volume of potential evidence that law-enforcement and corporate investigators spend countless hours examining. Join Us and SANS' Rob Lee for our 45-minute webinar, A Triage and Collection Strategy for Time-Sensitive Investigations, will demonstrate how to: Identify the folders and files that often contain key insights Reduce the time spent sifting through content by …

Most Popular Programming Stories

More for Developers

RSS Feeds