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 | |
26 | namespace boost { namespace algorithm { |
27 | |
28 | template <typename T> |
29 | BOOST_CXX14_CONSTEXPR T identity_operation ( std::multiplies<T> ) { return T(1); } |
30 | |
31 | template <typename 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 |
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 |
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 | |