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/utility/enable_if.hpp> // for boost::disable_if
24 #include <boost/type_traits/is_integral.hpp>
25
26 namespace boost { namespace algorithm {
27
28 template <typename T>
identity_operation(std::multiplies<T>)29 BOOST_CXX14_CONSTEXPR T identity_operation ( std::multiplies<T> ) { return T(1); }
30
31 template <typename T>
identity_operation(std::plus<T>)32 BOOST_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
43 template <typename T, typename Integer>
44 BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
power(T x,Integer n)45 power (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
70 template <typename T, typename Integer, typename Operation>
71 BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
power(T x,Integer n,Operation op)72 power (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