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

More by Author

Must Read