Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C++
Article

Template Meta Programming and Number Theory

Rate me:
Please Sign up or sign in to vote.
4.86/5 (27 votes)
13 Aug 2007CPOL15 min read 81.2K   410   48   8
In this article I try to implement some basic number theory function with the help of C++ template meta programming

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.

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

  1. Reflexive: i.e. x | x.
  2. Transitive: i.e. x | y and y | z then x | z
  3. Multiplication: i.e. x | y means cx | cy.
  4. Cancellation: i.e. cx | cy means x | y such that c is not equal to zero.
  5. If a | b and a | c then a | (a + b)
  6. If a | b and a | c then a | (a – b)
  7. If a | b and a | c then a | (a * b)
  8. If (b * c) | a then b | a and c | a
  9. 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.

C++
// 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 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.

C++
// 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); }
};

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.

C++
// 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 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) 
// 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 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. Screenshot - CoPrime01.gif

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 
// 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 other than 1. In other words if GCD of two numbers are 1 then those numbers are called Co Prime.

C++
// 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 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.

Screenshot - CoPrime02.gif

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"

C++
// check the given number is prime or not
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.

Screenshot - Equation01.gif

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.

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

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.

C++
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

Screenshot - Equation02.gif

C++
// 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

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

Screenshot - Equation03.gif

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.

C++
// 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 a very large number then the value of pi function is roughly equal to that number divided by its natural log.

Screenshot - Equation04.gif

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

C++
// pi function
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

Screenshot - Equation05.gif

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

Screenshot - Equation06.gif

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.

Screenshot - Equation07.gif

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

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

Screenshot - Equation08.gif

Screenshot - Equation09.gif

Screenshot - Equation10.gif

Therefore

Screenshot - Equation11.gif

Screenshot - Equation12.gif

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

Screenshot - Equation13.gif

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 Byond
    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 – 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Team Leader American Institute for Research
United States United States
Working as a Team leader in American Institute for Research

Comments and Discussions

 
GeneralMotivation Pin
Parchandri20-Aug-07 22:02
Parchandri20-Aug-07 22:02 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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