Template Meta Programming and Number Theory

1. Introduction

Meta-programming means writing a program that can generate other programs. This technique is used in different ways in different languages. It can also be said to be partial evaluation, a method of transforming one program into another or, in other words, automating programming [11]. A typical example of meta-programming is compiler construction tools such as Lex and YACC, which generate programs as an output. Compilers can also be put in this category, but usually they have a different host language than domain language [3]. They usually take grammar as an input and C, C++, or Java program as an output.

In C++, you can use templates and macros to create code for you. In fact, this is more or less abuse of the compiler, rather than a carefully designed feature [12]. A C++ compiler generates the code at the time of instantiation of the template and similarly the preprocessor, probably the oldest way to do meta-programming, expands the macros and generates the code. In a C++ Meta program, the language of the host program and domain language both are C++; this means the C++ compiler generates the C++ code at the time of instantiation of the template. In other words, a template Meta program is executed at compile time, not at run time; therefore, C++ is also considered as a two-level language [6][12][15].

There is a question about why one should use meta-programming. The most appropriate answer might be compile time optimization [7]. This technique can be applied in different areas, such as calculating the trigonometric functions such as sin, cos, and so forth, exponential and logarithm in advance at compile time in scientific and graphical applications and store it in memory to reduce runtime overhead. Meta-programming can be applied in other fields too, such as static data structure [16], algorithms [3], design patterns [10][13], reflection [15], expression templates [2][5], and so forth. One more reason is because in C++, the host language and domain language are the same; therefore, one does not have to learn the new syntax of any other language to write the program [3].

Number theory is one such field where you can take advantage of meta-programming to perform some interesting stuff. Number theory is study the properties of integers—in other words, whole numbers [4]. This is perhaps the oldest branch of mathematics and is also called Queen of Mathematics. An integer is denoted by Z, basically Zahlen in the German language.

As De Morgan once said, that the progress of algebra and geometry has been increased, when you start studying it together rather than separately. The same is true in the case of number theory. The earlier mathematicians divided the numbers in different categories on the basis of shapes created by them, such as a triangular number, square number, pentagonal number, and so on. They also knew the Pythagorean triangle and corresponding triple of numbers called Pythagorean triple. This is one of the many examples of the link of geometry with algebra, also known as Pythagorean Theorem. The study of number theory is not limited to the geometric and algebraic points of view, but it can be divided into several sub fields such as probabilistic study, combinatorial study, analytical study, and the like. Here are few sub fields of Number theory; they currently are very popular.

  1. Elementary Number Theory
  2. Algebraic Number Theory
  3. Geometric Number Theory
  4. Probabilistic Number Theory
  5. Combinatorial Number Theory
  6. Analytic Number Theory
  7. Computational Number Theory
  8. Combinatorial Number Theory
  9. Arithmetic Number Theory
  10. Additive Number Theory
  11. Multiplicative Number Theory
  12. Applied Number Theory

The whole study of number theory is the proof of different problems beautifully, and solves more complex problems on the basis of existing proofs. It is interesting to note that, if any conjecture or assumption is not proved in number theory, it still may have applications in real life. For example, the well-known cryptography algorithm RSA is based on this assumption that it is not easy to find the prime factor of a very large number if it is a multiple of two or more huge primes. If there is any method to easily find the factors of large integer, RSA-based systems can be easily broken [1][8].

2. Elementary Functions

2.1. Divisibility

An integer "a" is said to be divisible by another integer "b", which is not 0, if the ratio of "a / b" is also an integer; "b" is called a divisor or factor of "a". In other words, there is also a third integer such as

a = b * c

If "a" and "b" are positive, c must be positive. You can write "b | a" if "a" is divisible by "b" such as 20 | 100 means 100 is divisible by 20.

For example, 100 has the following positive divisors:

1, 2, 4, 5, 10, 20, 25, 50, 100

Divisor of any number is called a trivial divisor if it is either 1 or that number itself. In the exampleabove, 1 and 100 are trivial divisors of 100.

Divisibility has some very interesting properties. Here are some of the properties of divisibility.

  1. Reflexive: x | x.
  2. Transitive: If x | y and y | z, x | z
  3. Multiplication: x | y means cx | cy.
  4. Cancellation: cx | cy means x | y such that c is not equal to zero.
  5. If a | b and a | c, a | (a + b)
  6. If a | b and a | c, a | (a bo?=. b)
  7. If a | b and a | c, a | (a * b)
  8. If (b * c) | a, b | a and c | a
  9. 1 | n (every integer is divided by 1)

You can implement this concept easily with the help of a C++ template class, as shown in the following example.

// check divisibility
template <int u, int v>
struct Divisible
{
   enum { value = u % v == 0 ? 1 : 0 };
};

// check divide by zero condition
template <int u>
struct Divisible<u, 0>
{
   enum { value = -1 };
};

If u is divisible by v, it will return 1; otherwise, zero. There is one special case: division by zero handle by partial specialization of template. If the second parameter of this class is zero—try to divide any number by zero—the output will be -1, which means an error in this context. There will not be any problem with a negative number due to this error -1 error number because this class will only have two output 0 or 1—the number is divisible or not.

2.2. Ceiling and Floor Functions

By definition, a ceiling value is the least integer greater than or equal to the given number. Similarly, by definition, a floor value is the greatest integer greater than or equal to the given number. The input of these functions is a real number, but the output is an integer.

// to calculate the celing value
template <typename T>
struct Ceil
{
   static inline int value (T a)
   { return (a > 0 ? a + 1 : a ); }
};

// to calculate the floor value
template <typename T>
struct Floor
{
   static inline int value (T a)
   { return (a > 0 ? a : a - 1); }
};

Template Meta Programming and Number Theory

2.3. Parity

Perhaps the simplest classifications of numbers are even and odd; in other words, parity. By definition. every number that is divisible by 2 is even and those that are not divisible by 2 are odd. For example 2, 4, 100, 5000 are examples of even numbers and 1, 3, 51, 277 are examples of odd numbers. Even and odd numbers have one interesting property when converted into equivalent binary form. The least significant digit of every even number is zero and the odd number is one when converted into the binary form. Therefore, you can easily check the number whether it is even or odd if it will be represented in binary form.

 4 = 1002
 9 = 10012
20 = 101002
23 = 101112

Two integers have the same parity if both are even or odd. However, they have opposite parity.

Here is the code to check the parity of a number.

// check number is even or not
template <int u>
struct IsEven
{
   enum { value = Divisible<u, 2>::value };
};

// check number is odd or not
template <int u>
struct IsOdd
{
   enum { value = Divisible<u, 2>::value == 0 ? 1 : 0 };
};

This simple property of numbers, also known as parity, is used in communication to check the error during the transmission. Before sending data to the other end, you have to select the parity, even or odd, and leave one bit from the byte for this. If the class of number of bits and parity is same, put one in parity bit; otherwise, put zero. For example, if you select even parity and the number of bits in the data are even, the parity bit will be on; otherwise, it will be off. This will be exactly reversed in the case of odd parity.

If, due to any reason, during or after the transmission, one bit of data becomes corrupted, it can be checked on the receiving end with the help of the parity bit. This simple method can only detect the error but could not correct it. This method can detect an error if an odd number of bits corrupted; however, if an even number of bits is corrupted, this method does not report an error.

2.4. Calculate GCD

Greatest common division, or simply GCD, "d" of two integers "a", and "b" is the greatest integer that divides both "a" and "b" assuming that both "a" and "b" are not zero. The Greatest Common Divisor is also known as the "Highest Common Factor," or simply HCF. It can be represented as

k = gcd(u, v)

or

gcd(u, v) = max { k | k \ u and k \ v}

Where k \ u means u is divisible by k and k \ v means v is divisible by k.

By convention, you use

gcd(u, 0) = u

and gcd(0, 0) is undefined [4].

Euclid's algorithm is the oldest algorithm to calculate the GCD of two numbers. And perhaps, it is one of the oldest algorithms that still calculates results without errors. This algorithm assumes both numbers are positive integers—greater than zero.

For any non negative integer u and v, you can calculate the GCD recursively

gcd(u, v) = gcd(v, u mod v)
// calculate gcd
template <int u, int v>
struct gcd
{
   enum { value = gcd<v, u % v>::value };
};

template <int u>
struct gcd<u, 0>
{
   enum { value = u };
};

template <>
struct gcd<0, 0>
{
   enum { value = -1 };
};

If you put one number at the x-axis and another number at x-axis and draw a line from that point to the origin, the closest lattice point represents the GCD. It shows the point on lattice that can be achieved when both numbers are divided by the GCD.

2.5. Calculate LCM

The LCM (Least Common Multiple) is the smallest number (not zero) that is a multiple of both numbers. This is also known as "Lowest Common Denominator."

Mathematically, LCM can be defined as

lcm(u, v) = min { k | k > 0, u \ k and v \ k}

Where u \ k means k is divisible by u and v \ k means k is divisible by v

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) have a very close relationship with each other.

gcd(u, v) * lcm(u, v) = u * v
// calculate lcm
template <int u, int v>
struct lcm
{
   enum { value = u * v / gcd<u, v>::value };
};

2.6. CoPrime

In Mathematics, two numbers are said to be Co Prime, as well as relatively prime, to each other if they don't have any other common factor besides 1. In other words, if the GCD of two numbers is 1, those numbers are called Co Prime.

// check if numbers are coprime (relative prime) or not
template <int u, int v>
struct CoPrime
{
   enum { value = gcd<u, v>::value == 1 ? 1 : 0 };
};

Geometrically, it means if two numbers are Co Prime and you consider that number as a order pair—one number at x-axis and other at y-axis—and draw a line from that point to origin, this line does not intersect any other lattice point. If two numbers are not Co Prime to each other, geometrically GCD is a lattice point closest to the origin.

2.7. Prime

Any natural number that has exactly two divisors, 1 and that number itself, is called a prime number; 2, 3, 5, 7, and 11 are examples of the first five prime numbers. If a number has more than two divisors such as 4, 6, and 9, it is called a composite number. However, the number "1" is considered neither primer nor composite because it has only one divisor.

Every number can be a factor as a product of a prime number. It is important to note that every number is a product of exactly one way prime number set. In other words, every number can be decomposed into only one set of prime factors. For example:

100 = 2 * 2 * 5 * 5
4235 = 5*7*11*11

This is known as the "Fundamental theorem of arithmetic."

// check the given number is prime or not
template <int n>
struct IsPrime
{
   enum { value = NoOfDivisor<n>::value == 2 ? 1 : 0 };
};

The number of the divisor function is defined in section 3.1.

Template Meta Programming and Number Theory

3. Some Number Theory Functions

3.1. Numbers of Factors

Every positive integer has some 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 the number of factors of n where n is a positive integer. Mathematically, you can write it like this:

You can use the partial template specialization to emulate the loop in meta-programming to calculate the total number of factors of a given number.

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

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

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

Try to apply your existing routines to solve one interesting problem. Here is a problem 7.6.1 from "Programming Challenges" [14], also available online at [9].

There is man named "mabu" for switching on-off light in our University. He switches on-off the lights in a corridor. Every bulb has its own toggle switch. That is, if it is pressed then the bulb turns on. Another press will turn it off. To save power consumption (or may be he is mad or something else) he does a peculiar thing. If in a corridor there are 'n' bulbs, he walks along the corridor back and forth 'n' times and in i'th walk he toggles only the switches whose serial is divisable by i. He does not press any switch when coming back to his initial position. A i'th walk is defined as going down the corridor (while doing the peculiar thing) and coming back again.

Now, you have to determine the final condition of the last bulb? Is it on or off? One solution of this problem might be to traverse the bulbs n times, where n is total number of bulbs. This solution works, but it takes too much time and will slow down as the number of bulbs increases. After a little bit analysis of the problem, you may find that you can press the button if and only if it is multiple of "i", where "i" is the "ith" pass. If you see the problem on the other side, any arbitrary button k is pressed if and only if "i" is factor of k. Such as, press button 6 only on the 1st, 2nd, 3rd and 6th pass and all of these are factors of 6. Initially, each bulb is off, so if the number of factors of any number is odd, it will be on; otherwise, it will be off. You can calculate the state of any bulb without going through any other bulb and it's not very difficult to program it.

   cout << IsOdd< NoOfDivisor <3>::value>::value  << endl;
   cout << IsOdd< NoOfDivisor <25>::value>::value << endl;
   cout << IsOdd< NoOfDivisor <47>::value>::value << endl;

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, yoou sum all the factors of a given number. Mathematically, it can be written as this:

// 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 };
};

3.3. Divisor Function

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

If the value of x is 1 it is a Sigma function. If it is zero, it calculates the number of the divisor of a given number.

// to calculate the power
template <nt a, int b>
struct Power
{
   enum { value = a*Power<a, b-1>::value };
};

template <int a>
struct Power<a, 0>
{
   enum { value = 1 };
};

// 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 };
};

// to calculate divisor function
template <int n, int x>
struct Divisor
{
   enum { value = DivisorLoop<1, n, x>::value };
};

3.4. Pi Function

This function is also known as the prime counting function. This function counts the number of primes less than or equal to a given number. One of the most important theorems of number theory, "Prime number theorem," is related to the Pi function. This theorem states that, if N is very large number, the value of the Pi function is roughly equal to that number divided by its natural log.

In other words, it means that if you select any arbitrary large number, its probability to be a prime number is 1 / ln(n).

// pi function
template <int n>
struct PiFunc
{
   enum { value = IsPrime<n>::value + PiFunc<n-1>::value };
};

template <>
struct PiFunc<2>
{
   enum { value = 1 };
};

Template Meta Programming and Number Theory

3.5. Totient Function

The Totient function, also known as the Phi function and Euler's Totient function, is defined as the number of a positive integer less than equal to the given number and Co prime of it. For example, phi (9) = 6 because 1, 2, 4, 5, 7, and 8 are Co Primes of 9 and phi (11) = 10 because 11 is a prime number and it is CoPrime of all the number less than itself. Mathematically, the Totient function be written as:

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

This is because every number is a Coprime to the prime number. The Totient function has a strong relation with prime numbers, too; in fact, it can be written as product of the prime too.

// 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 function
template <int n>
struct Totient
{
   enum { value = TotientLoop<1, n>::value };
};

template <>
struct Totient<1>
{
   enum { value = 1 };
};

template <>
struct Totient<0>
{
   enum { value = 1 };
};

The Totient function is a very important function in cryptography and it is used in the RSA public key cryptography algorithm [1][8]. The RSA algorithm is based on the following properties of the Totient function. If p and q are two prime numbers and n is a product of p and q,



Therefore


And Euler's Totient theorem that stated, if two number "a" and "n" are co-prime to each others,

4. References

  1. A Method for Obtaining Digital Signatures and Public Key Cryptosystems. R.L Rivest, A. Shamir, L. Adleman. Communication of the ACM, February 1978.
  2. C++ Templates: The Complete Guide. David Vandevoorde, Nicolai Josuttis. Addison Wesley, 2002.
  3. C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Beyond. David Abrahams, Aleksey Gurtovoy. Addison Wesley, 2004.
  4. Concrete Mathematics 2nd edition. Ronald L. Garam, Donald E Knuth, Oren Patashnik. Addison Wesley, 1994.
  5. "Expression Templates." Veldhuizen, T. L. C++ Report, 1995.
  6. Generative Programming bo?=. Methods, Tools and Applications. K. Czamecki, U.W. Eisenacker. Addison Wesley, 2000.
  7. "Impact of Economics on Compiler Optimization." Arch D. Robison. Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande
  8. Introduction to Algorithms, Second edition. Thomas H. Cormen, Charles E. Lieserson, Ronald L. Rivest, Clifford Stein. MIT Press, 2001.
  9. Light, more Light. http://online-judge.uva.es/p/v101/10110.html
  10. "Making Patterns Explicit with Meta-programming." Daniel von Dincklage. Proceedings of the second international conference on Generative programming and component engineering, 2003.
  11. "Meta-programming and Free Availability of Sources." François-René Rideau. http://fare.tunes.org/articles/ll99/mpfas.html
  12. "Meta-Programming in C++." Johannes Koskinen, 2004. http://www.cs.tut.fi/~kk/webstuff/MetaprogrammingCpp.pdf
  13. Modern C++ Design: Generic Programming and Design Patterns Applied. Alexandrescu, Andrew. Addison Wesley, 2001.
  14. Programming Challenges: The Programming Contest Training Manual. Steven S. Skiena, Miguel A. Revilla. Springer Science+Business, 2003.
  15. "Reflection Support by means of template Meta-programming." Guiseppe Attardi, Antonio Cisternino. http://lcgapp.cern.ch/project/architecture/ReflectionPaper.pdf
  16. "Static Data Structure: Reconciling Template Meta-programming and Generic Programming." Michael C. Burton, William G. Griswold, Andrew D. McCulloch, Gray A. Huber. http://www.cs.ucsd.edu/~wgg/Statements/mburton-ifip-gw-07-2002.pdf


About the Author

Zeeshan Amjad

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

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: August 20, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT When you look at natural user interfaces as a developer, it isn't just fun and games. There are some very serious, real-world usage models of how things can help make the world a better place – things like Intel® RealSense™ technology. Check out this upcoming eSeminar and join the panel of experts, both from inside and outside of Intel, as they discuss how natural user interfaces will likely be getting adopted in a wide variety …

  • Event Date: April 15, 2014 The ability to effectively set sales goals, assign quotas and territories, bring new people on board and quickly make adjustments to the sales force is often crucial to success--and to the field experience! But for sales operations leaders, managing the administrative processes, systems, data and various departments to get it all right can often be difficult, inefficient and manually intensive. Register for this webinar and learn how you can: Align sales goals, quotas and …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds