]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
28 | T identity_operation ( std::multiplies<T> ) { return T(1); } | |
29 | ||
30 | template <typename 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 | |
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 | |
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 |