Introduction
Meta-programming means: writing a program which can generate other program. This technique is used in different ways in different languages. It can also be called partial evaluation; a method of transforming one program into another (or in other words automate programming [11]). A typical example of meta-programming are compiler construction tools such as Lex and YACC, which generate a program as an output. A compiler can also be put in this category, but usually they have a different host language than a domain language [3]. This is because they usually take grammar as an input and C, C++ or Java program as an output.
In C++ we can use templates and macros to create code for us. In fact, this is more or less abusing the compiler rather than being a carefully designed feature [12]. A compiler of C++ generates the code at the time of instantiation of the template. Similarly, 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 are both C++; this means the C++ compiler generates the C++ code at the time of the 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 a two level language [6][12][15].
So why should one use meta-programming? The most appropriate answer might be compile time optimization [7]. This technique can be applied in different areas, such as calculating trigonometric functions i.e. sin, cos etc, exponential and logarithm (in advance of 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 template [2][5] etc. One more reason is because in C++ the host language and domain language are both 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 we can take the advantage of meta-programming to perform some interesting stuff. Number theory is the study of properties of integers or, in other words, whole numbers [4]. This is perhaps the oldest branch of mathematics and also called the Queen of Mathematics. Integer is denoted by Z, basically Zahlen in German language.
As De Morgan once said, the progress of algebra and geometry has been increased, when we started study it together rather than separately. The same is true in the case of number theory. The earlier mathematician divided the numbers in different categories on the basis of the shapes created by them, such as triangular number, square number, pentagonal number etc. 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 point of view, but it can be divided into several sub fields such as probabilistic study, combinatorial study, analytical study etc. Here are few sub fields of Number theory, which are very popular currently.
- Elementary Number Theory
- Algebraic Number Theory
- Geometric Number Theory
- Probabilistic Number Theory
- Combinatorial Number Theory
- Analytic Number Theory
- Computational Number Theory
- Combinatorial Number Theory
- Arithmetic Number Theory
- Additive Number Theory
- Multiplicative Number Theory
- 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 then 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, then RSA based systems can be easily broken [1][8].
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, then c must be positive. We 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 trivial divisor if it is either 1 or that number itself. Such as in above example 1 and 100 are trivial divisor of 100.
Divisibility has some very interesting properties. Here are some of the properties of divisibility.
- Reflexive: i.e. x | x.
- Transitive: i.e. x | y and y | z then x | z
- Multiplication: i.e. x | y means cx | cy.
- Cancellation: i.e. cx | cy means x | y such that c is not equal to zero.
- If a | b and a | c then a | (a + b)
- If a | b and a | c then a | (a – b)
- If a | b and a | c then a | (a * b)
- If (b * c) | a then b | a and c | a
- 1 | n (every integer is divided by 1)
We can implement this concept easily with the help of C++ template class as shown in the following example.
template <int u, int v>
struct Divisible
{
enum { value = u % v == 0 ? 1 : 0 };
};
template <int u>
struct Divisible<u, 0>
{
enum { value = -1 };
};
If u is divisible by v then it will return 1, otherwise zero. There is one special case divide by zero handle by partial specialization of template. If second parameter of this class is zero, i.e. try to divide any number by zero then output will be -1, which means 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 i.e. number is divisible or not.
2.2. Ceiling and Floor Functions
By definition, ceiling value is the least integer greater than or equal to the given number. Similarly by definition floor value is the greatest integer greater than or equal to the given number. Input of these functions is real number but the output is integer.
template <typename T>
struct Ceil
{
static inline int value (T a)
{ return (a > 0 ? a + 1 : a ); }
};
template <typename T>
struct Floor
{
static inline int value (T a)
{ return (a > 0 ? a : a - 1); }
};
2.3. Parity
Perhaps the simplest classifications of numbers are even and odd, in other words, parity. By definition every number which is divisible by 2 is even and which is not divisible by 2 is odd. For example 2, 4, 100, 5000 are example 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 odd number is one when converted into the binary form. Therefore we can easily check the number weather it is even or odd if it will be represented in binary form.
4 = 100<sub>2</sub>
9 = 1001<sub>2</sub>
20 = 10100<sub>2</sub>
23 = 10111<sub>2</sub>
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.
template <int u>
struct IsEven
{
enum { value = Divisible<u, 2>::value };
};
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 we have to select the parity, even or odd, and are left one bit from the byte for this. If the class of number of bits and parity is the same then put one in the parity bit, and otherwise put zero. For example, if we select even parity and no of bits in the data are even, then parity bit will be on, otherwise it will be off. Odd parity will be the exact reverse.
If, due to any reason, during or after the transmission, one bit of data becomes corrupted, then it can be checked on the receiving end with the help of parity bit. This simple method can only detect the error but could not correct it. This method can detect an error if odd numbers of bits are corrupted, however, if even number of bits are corrupted then this method does not report any error.
2.4. Calculate GCD
Greatest common division, or simply gcd, "d" of two integers "a", and "b" is the greatest integer which divide both "a" and "b" assume both "a" and "b" are not zero. Greatest Common Divisor is also known as "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 we use:
gcd(u, 0) = u
and gcd(0, 0) is undefined [4].
Euclid's algorithm is the oldest algorithm to calculate 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 integer i.e. greater than zero.
For any non negative integer u and v, we can calculate the gcd recursively
gcd(u, v) = gcd(v, u mod v)
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 we put one number at x-axis and other number at x-axis and draw a line from that point to the origin then the closest lattice point represents the GCD, it shows the point on lattice that can be achieved when both numbers are divided by GCD. 
2.5. Calculate LCM
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
Greatest Common Divisor (GCD) and Least Common Multiple (LCM) have very close relationship with each other.
gcd(u, v) * lcm(u, v) = u * v
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 other than 1. In other words if GCD of two numbers are 1 then those numbers are called Co Prime.
template <int u, int v>
struct CoPrime
{
enum { value = gcd<u, v>::value == 1 ? 1 : 0 };
};
Geometrically it means if two numbers are Coprime and we consider that number as a order pair i.e. one number at x-axis and other at y-axis and draw a line from that point to origin then this line does not intersect any other lattice point. If two numbers are not CoPrime to each other then geometrically GCD is a lattice point closest to the origin.
2.7. Prime
Any natural number which has exactly two divisors, 1 and that number itself, is called prime number such as 2, 3, 5, 7, 11, are example of first five prime numbers. If a number has more than two divisors such as 4, 6, 9 then it is called composite number. However, number "1" is neither considered primer nor composite, because it has only one divisor.
Every number can be factored 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 "Fundamental theorem of arithmetic"
template <int n>
struct IsPrime
{
enum { value = NoOfDivisor<n>::value == 2 ? 1 : 0 };
};
Number of divisor function is defined in section 3.1
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. We can define an arithmetic function t(n) such as number of factors of n where n is a positive integer. Mathematically we can write it.
We can use the partial template specialization to emulate the loop in meta-programming to calculate the total number of factors of a given number.
template <int Start, int End>
struct NumDivisorsLoop
{
enum { value = Divisible<End, Start>::value +
NumDivisorsLoop<Start + 1, End>::value };
};
template <int End>
struct NumDivisorsLoop<End, End>
{
enum { value = 1 };
};
template <int n>
struct NoOfDivisor
{
enum { value = NumDivisorsLoop<1, n>::value };
};
Let's try to apply our 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 what is the final condition of the last bulb? Is it on or off? One solution of this problem might be to traverse bulbs n times, where n is the total number of bulbs. Although this solution works, it takes too much time and will slow down as number of bulbs increases. After a little analysis of the problem, we may find that we can press the button if and only if it is a multiple of "i", where "i" is "ith" pass. If we see the problem on the other side then any arbitrary button k is pressed if and only if "i" is factor of k. Such as button 6 press only 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 then it will be on, otherwise it will be off. So we can calculate the state of any bulb without even 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)
Simga function is similar to the number of the divisor 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 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
Divisor function is a generalized form of Sigma function, in other words, sigma function is a special case of 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
If the value of x is one then it is sigma function. If zero then it calculates the number of divisor of a given number.
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 };
};
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 };
};
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 a very large number then the value of pi function is roughly equal to that number divided by its natural log.
In other words it means that if we select any arbitrary large number then its probability to be a prime number is 1 / ln(n).
template <int n>
struct PiFunc
{
enum { value = IsPrime<n>::value + PiFunc<n-1>::value };
};
template <>
struct PiFunc<2>
{
enum { value = 1 };
};
3.5. Totient Function
Totient function, also known as phi function and Euler's Totient function, is defined as number of positive integer less than equal to given number and Coprime of it. For example, phi (9) = 6 because 1, 2, 4, 5, 7 and 8 are CoPrime 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 totient function, if "p" is prime number then
This is because every number is a co-primer to the prime number. The Totient function has a strong relation with prime numbers too, in fact, it can be written as a product of prime.
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 n>
struct Totient
{
enum { value = TotientLoop<1, n>::value };
};
template <>
struct Totient<1>
{
enum { value = 1 };
};
template <>
struct Totient<0>
{
enum { value = 1 };
};
Totient function is a very important function in cryptography and it is used in RSA public key cryptography algorithm [1][8]. RSA algorithm is based on the following properties of totient function. If p and q are two prime numbers and n is a product of p and q then
Therefore
And Euler's Totient theorem that stated, if two numbers, "a" and "n" are co-prime to each other then
4. References
- A Method for Obtaining Digital Signatures and Public Key Cryptosystems
R.L Rivest, A. Shamir, L. Adleman
Communication of the ACM, February 1978 - C++ Templates: The Complete Guide
David Vandevoorde, Nicolai Josuttis
Addison Wesley, 2002 - C++ Template Metaprogramming: Concepts, Tools and Techniques from Boost and Byond
David Abrahams, Aleksey Gurtovoy
Addison Wesley, 2004 - Concrete Mathematics 2nd edition
Ronald L. Garam, Donald E Knuth, Oren Patashnik
Addison Wesley, 1994 - Expression Templates
Veldhuizen, T. L
C++ Report 1995 - Generative Programming – Methods, Tools and Applications
K. Czamecki, U.W. Eisenacker
Addison Wesley, 2000 - Impact of Economics on Compiler Optimization
Arch D. Robison
Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande - Introduction to Algorithms, Second edition
Thomas H. Cormen, Charles E. Lieserson, Ronald L. Rivest, Clifford Stein
MIT Press (2001) - Light, more Light
http://online-judge.uva.es/p/v101/10110.html - Making Patterns Explicit with Meta-programming
Daniel von Dincklage
Proceedings of the second international conference on Generative programming and component engineering (2003) - Meta-programming and Free Availability of Sources
François-René Rideau
http://fare.tunes.org/articles/ll99/mpfas.html - Meta-Programming in C++
Johannes Koskinen (2004)
http://www.cs.tut.fi/~kk/webstuff/MetaprogrammingCpp.pdf - Modern C++ Design: Generic Programming and Design Patterns Applied
Alexandrescu, Andrew
Addison Wesley, 2001 - Programming Challenges: The Programming Contest Training Manual
Steven S. Skiena, Miguel A. Revilla
Springer Science+Business, 2003 - Reflection Support by means of template Meta-programming
Guiseppe Attardi, Antonio Cisternino
http://lcgapp.cern.ch/project/architecture/ReflectionPaper.pdf - 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
