jmmcg::LIBJMMCG_VER_NAMESPACE::binary_right_to_left Namespace Reference

An implementation of the binary-right-to-left method of exponentiation for raising a number to positive, integer power. More...

Namespaces
namespace	dyn
	For types for which operator*() cannot be computed at compile-time, this variant unrolls the exponentiation at compile-time.
namespace	mpl
	For types for which operator*() can be computed at compile-time, this variant computes the entire exponentiation at compile-time.

Detailed Description

An implementation of the binary-right-to-left method of exponentiation for raising a number to positive, integer power.

This is an implementation of the binary-right-to-left exponentiation algorithm from "The Art of Computer Programming, Vol 2, Seminumerical Algorithms", Knuth. The runtime-algorithmic complexity of this function is O(M), where M is the algorithmic complexity of multiplication on the type V. The compile-time algorithmic complexity of this function is O(lg(power)+v(power)), where v(power) is the number of 1s in the binary representation of power.