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/utility/enable_if.hpp> // for boost::disable_if
23 #include <boost/type_traits/is_integral.hpp>
24
25 namespace boost { namespace algorithm {
26
27 template <typename T>
identity_operation(std::multiplies<T>)28 T identity_operation ( std::multiplies<T> ) { return T(1); }
29
30 template <typename T>
identity_operation(std::plus<T>)31 T identity_operation ( std::plus<T> ) { return T(0); }
32
33
34 /// \fn power ( T x, Integer n )
35 /// \return the value "x" raised to the power "n"
36 ///
37 /// \param x The value to be exponentiated
38 /// \param n The exponent (must be >= 0)
39 ///
40 // \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
41 // Seminumerical Algorithms, Section 4.6.3
42 template <typename T, typename Integer>
43 typename boost::enable_if<boost::is_integral<Integer>, T>::type
power(T x,Integer n)44 power (T x, Integer n) {
45 T y = 1; // Should be "T y{1};"
46 if (n == 0) return y;
47 while (true) {
48 if (n % 2 == 1) {
49 y = x * y;
50 if (n == 1)
51 return y;
52 }
53 n = n / 2;
54 x = x * x;
55 }
56 return y;
57 }
58
59 /// \fn power ( T x, Integer n, Operation op )
60 /// \return the value "x" raised to the power "n"
61 /// using the operation "op".
62 ///
63 /// \param x The value to be exponentiated
64 /// \param n The exponent (must be >= 0)
65 /// \param op The operation used
66 ///
67 // \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
68 // Seminumerical Algorithms, Section 4.6.3
69 template <typename T, typename Integer, typename Operation>
70 typename boost::enable_if<boost::is_integral<Integer>, T>::type
power(T x,Integer n,Operation op)71 power (T x, Integer n, Operation op) {
72 T y = identity_operation(op);
73 if (n == 0) return y;
74 while (true) {
75 if (n % 2 == 1) {
76 y = op(x, y);
77 if (n == 1)
78 return y;
79 }
80 n = n / 2;
81 x = op(x, x);
82 }
83 return y;
84 }
85
86 }}
87
88 #endif // BOOST_ALGORITHM_HPP
89