Persistent notes

There is one very famous task to design an algorithm which calculates 2 in power N.

Obvious solution will require N operations so it is not something we are thinking about.

If you look at the example: 2^6 = 2*2*2*2*2*2 you will notice that it can be done faster: 2^6 = (2^3)*(2^3).

in other words:

long compute2N(long n)
{
	if (n==0) return 1;
	else if (n<=1) return 2;
	else if (n % 2){
		//odd
		return 2 * compute2N(n-1);
	}
	else
	{//even
		long tmp = compute2N(n/2);
		return tmp * tmp;
	}
}

So it can be done much more efficiently than just multiplying N times by 2.

On the other hand, everyone knows that 2 or any other base in power N can be computed with the help of templates and C++ preprocessor.
For example, see templated recursion.

So what about writing a 2^N better algorithm which uses nothing but templates?

Here is my try:

#include <iostream>
using namespace std; 

template <int N, int remainder> struct POWOF2R{}; 

template <int N> struct POWOF2R<N, 0>{
	enum {
		tempo = POWOF2R<N/2, (N/2) %2>::value,
		value = tempo * tempo
	};
};

template<int N>
struct POWOF2R<N, 1>{
	enum {
		value = 2 * POWOF2R<N-1, (N-1)%2>::value
	};
};

template<>
struct POWOF2R<2,0>{
	enum {
		value = 4
	};
};

template<>
struct POWOF2R<0,0>{
	enum {
		value = 1
	};
};

template<int N>
struct POWER2
{
	enum {
		value = POWOF2R<N, N%2>::value
	};
};

int main(){
	std::cout << "2 in power of 2: = " << POWER2<2>::value << std::endl;
	std::cout << "2 in power of 3: = " << POWER2<3>::value << std::endl;
	std::cout << "2 in power of 4: = " << POWER2<4>::value << std::endl;
	std::cout << "2 in power of 5: = " << POWER2<5>::value << std::endl;
	std::cout << "2 in power of 10: = " << POWER2<10>::value << std::endl;
	return 0;
}

Yes, this is completely useless, I agree.

But little C++ fetish is always fun :)