12,626,813 members (33,592 online)

6.2K views
46 bookmarked
Posted

# Template Meta Programming and Number Theory

, 13 Aug 2007 CPOL
In this article I try to implement some basic number theory function with the help of C++ template meta programming
 ```// Name: NLUMP.h // Author: Zeeshan Amjad // Description: Numbter theory Library Using Meta Programming #ifndef __NLUMP_H #define __NLUMP_H // check divisibility template class Divisible { public: enum { value = u % v == 0 ? 1 : 0 }; }; // check divide by zero condition template class Divisible { public: enum { value = -1 }; }; // check if one number is divide by other template class DivisibleDigit { public: enum { value = u % v == 0 ? v : 0 }; }; // check divide by zero condition template class DivisibleDigit { public: enum { value = -1 }; }; // check number is even or not template class IsEven { public: enum { value = Divisible::value }; }; // check number is odd or not template class IsOdd { public: enum { value = Divisible::value == 0 ? 1 : 0 }; }; // loop for total no of divisors template class NumDivisorsLoop { public: enum { value = Divisible::value + NumDivisorsLoop::value }; }; // partial specialization to terminate loop template class NumDivisorsLoop { public: enum { value = 1 }; }; // number of divisor of any digit template class NoOfDivisor { public: enum { value = NumDivisorsLoop<1, n>::value }; }; // loop for sum of divisor template class SumOfDivisorLoop { public: enum { value = DivisibleDigit::value + SumOfDivisorLoop::value }; }; template class SumOfDivisorLoop { public: enum { value = DivisibleDigit::value }; }; // check no is perfect or not template class IsPerfect { public: enum { value = SumOfDivisor::value - n == n ? 1 : 0 }; }; // calculate gcd template class gcd { public: enum { value = gcd::value }; }; template class gcd { public: enum { value = u }; }; template <> class gcd<0, 0> { public: enum { value = -1 }; }; // calculate lcm template class lcm { public: enum { value = u * v / gcd::value }; }; // check if numbers are coprime (relative prime) or not template class CoPrime { public: enum { value = gcd::value == 1 ? 1 : 0 }; }; // to calculate the power template class Power { public: enum { value = a*Power::value }; }; template class Power { public: enum { value = 1 }; }; // to calculate Permutations template class Permutations { public: enum { value = Factorial::value / Factorial::value }; }; // to calculate Combination template class Combination { public: enum { value = Factorial::value / Factorial::value * Factorial::value }; }; // helper template loop for calculate totient function template class TotientLoop { public: enum { value = CoPrime::value + TotientLoop::value }; }; template class TotientLoop { public: enum { value = 0 }; }; // totient function template class Totient { public: enum { value = TotientLoop<1, n>::value }; }; template <> class Totient<1> { public: enum { value = 1 }; }; template <> class Totient<0> { public: enum { value = 1 }; }; // loop for divisor function template class DivisorLoop { public: enum { value = (Divisible::value == 1 ? Power::value : 0) + DivisorLoop::value }; }; template class DivisorLoop { public: enum { value = Power::value }; }; // to calculate divisor function template class Divisor { public: enum { value = DivisorLoop<1, n, x>::value }; }; // check the given number is prime or not template class IsPrime { public: enum { value = NoOfDivisor::value == 2 ? 1 : 0 }; }; // calculate the number of prime less than given number // pi function template class PiFunc { public: enum { value = IsPrime::value + PiFunc::value }; }; template <> class PiFunc<2> { public: enum { value = 1 }; }; // totient summatory function loop template class TotientSummatoryLoop { public: enum { value = Totient::value + TotientSummatoryLoop::value }; }; template class TotientSummatoryLoop { public: enum { value = Totient::value }; }; // totient summatory function template class TotientSummatory { public: enum { value = TotientSummatoryLoop<1, n>::value }; }; // to calculate the celing value template class Ceil { public: static inline int value (T a) { return (a > 0 ? a + 1 : a ); } }; // to calculate the floor value template class Floor { public: static inline int value (T a) { return (a > 0 ? a : a - 1); } }; #endif ```

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.