1/*
2 Copyright (c) Marshall Clow 2014.
3
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7 Revision history:
8 2 Dec 2014 mtc First version; power
9
10*/
11
12/// \file algorithm.hpp
13/// \brief Misc Algorithms
14/// \author Marshall Clow
15///
16
17#ifndef BOOST_ALGORITHM_HPP
18#define BOOST_ALGORITHM_HPP
19
20#include <functional> // for plus and multiplies
21
22#include <boost/config.hpp>
23#include <boost/core/enable_if.hpp> // for boost::disable_if
24#include <boost/type_traits/is_integral.hpp>
25
26namespace boost { namespace algorithm {
27
28template <typename T>
29BOOST_CXX14_CONSTEXPR T identity_operation ( std::multiplies<T> ) { return T(1); }
30
31template <typename T>
32BOOST_CXX14_CONSTEXPR T identity_operation ( std::plus<T> ) { return T(0); }
33
34
35/// \fn power ( T x, Integer n )
36/// \return the value "x" raised to the power "n"
37///
38/// \param x The value to be exponentiated
39/// \param n The exponent (must be >= 0)
40///
41// \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
42// Seminumerical Algorithms, Section 4.6.3
43template <typename T, typename Integer>
44BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
45power (T x, Integer n) {
46 T y = 1; // Should be "T y{1};"
47 if (n == 0) return y;
48 while (true) {
49 if (n % 2 == 1) {
50 y = x * y;
51 if (n == 1)
52 return y;
53 }
54 n = n / 2;
55 x = x * x;
56 }
57 return y;
58 }
59
60/// \fn power ( T x, Integer n, Operation op )
61/// \return the value "x" raised to the power "n"
62/// using the operation "op".
63///
64/// \param x The value to be exponentiated
65/// \param n The exponent (must be >= 0)
66/// \param op The operation used
67///
68// \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
69// Seminumerical Algorithms, Section 4.6.3
70template <typename T, typename Integer, typename Operation>
71BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
72power (T x, Integer n, Operation op) {
73 T y = identity_operation(op);
74 if (n == 0) return y;
75 while (true) {
76 if (n % 2 == 1) {
77 y = op(x, y);
78 if (n == 1)
79 return y;
80 }
81 n = n / 2;
82 x = op(x, x);
83 }
84 return y;
85 }
86
87}}
88
89#endif // BOOST_ALGORITHM_HPP
90

source code of boost/libs/algorithm/include/boost/algorithm/algorithm.hpp