power.hpp File Reference

Generic compile-time unrolling of the fast exponentiation algorithm. More...

Go to the source code of this file.

Classes
struct	HPCombi::power_helper::Monoid< T >
	Algebraic monoid structure used by default for type T by the pow function and prod function. More...

Namespaces
namespace	HPCombi
namespace	HPCombi::power_helper

Functions
template<typename T, typename M = power_helper::Monoid<T>>
const T	HPCombi::square (const T x)
	A generic compile time squaring function.
template<unsigned exp, typename T, typename M = power_helper::Monoid<T>>
const T	HPCombi::pow (const T x)
	A generic compile time exponentiation function.

Detailed Description

Generic compile-time unrolling of the fast exponentiation algorithm.

Allows to write expressions such as

• pow<23>(2.5) : entirely computed at compile time
• pow<n>(x) expanded at compile time to a O(log n) long sequence of multiplications.

Such expressions work for numbers but also for any type where there is a neutral element and an associative (non necessarily commutative) product, ie what mathematicians call monoids. These include for example strings where the neutral element is the empty string and the product is the concatenation.

See HPCombi::power_helper::Monoid<std::string>

The algorithm used here is based on the base-2 representation of n, it is a 2-approximation of the optimum number of multiplications. The general problem is called addition chain and one can sometimes do better, eg on fibonaci numbers, use rather the fibonacci recurrence relation to choose which products to compute.