libjmmcg  build_2783
A C++ library containing an eclectic mix of useful, advanced components.
jmmcg::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

 dyn
 For types for which operator*() cannot be computed at compile-time, this variant unrolls the exponentiation at compile-time.
 
 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.