Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

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
code.zip
// Name:		NLUMP.h
// Author: 		Zeeshan Amjad
// Description: 	Numbter theory Library Using Meta Programming

#ifndef __NLUMP_H
#define __NLUMP_H

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

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

// check if one number is divide by other
template <int u, int v>
class DivisibleDigit
{
public:
	enum { value = u % v == 0 ? v : 0 };
};

// check divide by zero condition
template <int u>
class DivisibleDigit<u, 0>
{
public:
	enum { value = -1 };
};

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

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

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

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

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

// loop for sum of divisor
template <int Start, int End>
class SumOfDivisorLoop
{
public:
	enum { value = DivisibleDigit<End, Start>::value + SumOfDivisorLoop<Start + 1, End>::value };
};

template <int End>
class SumOfDivisorLoop<End, End>
{
public:
	enum { value = DivisibleDigit<End, End>::value };
};

// check no is perfect or not
template <int n>
class IsPerfect
{
public:
	enum { value = SumOfDivisor<n>::value - n == n ? 1 : 0 };
};

// calculate gcd
template <int u, int v>
class gcd
{
public:
	enum { value = gcd<v, u % v>::value };
};

template <int u>
class gcd<u, 0>
{
public:
	enum { value = u };
};

template <>
class gcd<0, 0>
{
public:
	enum { value = -1 };
};

// calculate lcm
template <int u, int v>
class lcm
{
public:
	enum { value = u * v / gcd<u, v>::value };
};

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

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

template <int a>
class Power<a, 0>
{
public:
	enum { value = 1 };
};

// to calculate Permutations
template <int n, int r>
class Permutations
{
public:
	enum { value = Factorial<n>::value / Factorial<n-r>::value };
};

// to calculate Combination
template <int n, int r>
class Combination
{
public:
	enum { value = Factorial<n>::value / Factorial<r>::value * Factorial<n-r>::value };
};

// helper template loop for calculate totient function
template <int Start, int End>
class TotientLoop
{
public:
	enum { value = CoPrime<Start, End>::value + TotientLoop<Start + 1, End>::value };
};

template <int End>
class TotientLoop<End, End>
{
public:
	enum { value = 0 };
};

// totient function
template <int n>
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 <int Start, int End, int x>
class DivisorLoop
{
public:
	enum { value = (Divisible<End, Start>::value == 1 ? Power<Start, x>::value : 0) + 
		DivisorLoop<Start+1, End, x>::value };
};

template <int End, int x>
class DivisorLoop<End, End, x>
{
public:
	enum { value = Power<End, x>::value };
};

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

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

// calculate the number of prime less than given number
// pi function
template <int n>
class PiFunc
{
public:
	enum { value = IsPrime<n>::value + PiFunc<n-1>::value };
};

template <>
class PiFunc<2>
{
public:
	enum { value = 1 };
};

// totient summatory function loop
template <int Start, int End>
class TotientSummatoryLoop
{
public:
	enum { value = Totient<Start>::value + TotientSummatoryLoop<Start + 1, End>::value };
};

template <int End>
class TotientSummatoryLoop<End, End>
{
public:
	enum { value = Totient<End>::value };
};

// totient summatory function
template <int n>
class TotientSummatory
{
public:
	enum { value = TotientSummatoryLoop<1, n>::value };
};

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

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

#endif

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

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.

License

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

Share

About the Author

Zeeshan Amjad
Software Developer (Senior) Bloomberg LP
United States United States
Working as a Sr C++ Developer at Bloomberg LP

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141216.1 | Last Updated 13 Aug 2007
Article Copyright 2007 by Zeeshan Amjad
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid