libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
integer_power.hpp
Go to the documentation of this file.
1 /******************************************************************************
2 ** Copyright © 2004 by J.M.McGuiness, coder@hussar.me.uk
3 **
4 ** This library is free software; you can redistribute it and/or
5 ** modify it under the terms of the GNU Lesser General Public
6 ** License as published by the Free Software Foundation; either
7 ** version 2.1 of the License, or (at your option) any later version.
8 **
9 ** This library is distributed in the hope that it will be useful,
10 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
11 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 ** Lesser General Public License for more details.
13 **
14 ** You should have received a copy of the GNU Lesser General Public
15 ** License along with this library; if not, write to the Free Software
16 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18 
19 #include "config.h"
20 #include "debug_defines.hpp"
21 
22 #include <boost/static_assert.hpp>
23 
24 #include <functional>
25 
26 #ifdef _MSC_VER
27 # pragma warning(push)
28 # pragma warning(disable:4127) ///< Conditional expression is constant.
29 #endif
30 
31 namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
32 
33  /// The result is true if the value V is positive, otherwise false.
34  template<
35  long V ///< The value to test.
36  >
37  struct sign {
38  static constexpr long result=(V>=0);
39  };
40 
41  /// The result is the modulus of the value, V.
42  template<
43  long V ///< The value to test.
44  >
45  struct modulus {
46  static constexpr long result=(sign<V>::result ? V : -V);
47  };
48 
49  /// Invert the value V if the boolean A is false.
50  template<
51  typename V, ///< The value to potentially invert.
52  bool A ///< Condition upon which to invert.
53  >
54  struct invert_if : std::unary_function<V, V> {
55  typedef typename std::unary_function<V, V>::result_type result_type;
56  typedef typename std::unary_function<V, V>::argument_type argument_type;
57 
58  static constexpr result_type __fastcall FORCE_INLINE result(argument_type a) noexcept(true) {
59  return a;
60  }
61  };
62  template<typename V>
63  struct invert_if<V, false> : std::unary_function<V, V> {
64  typedef typename std::unary_function<V, V>::result_type result_type;
65  typedef typename std::unary_function<V, V>::argument_type argument_type;
66 
67  static constexpr result_type __fastcall FORCE_INLINE result(argument_type a) noexcept(true) {
68  return result_type(1/a);
69  }
70  };
71 
72  /// An implementation of the binary-right-to-left method of exponentiation for raising a number to positive, integer power.
73  /**
74  This is an implementation of the binary-right-to-left exponentiation algorithm from
75  "The Art of Computer Programming, Vol 2, Seminumerical Algorithms", Knuth.
76  The runtime-algorithmic complexity of this function is O(M), where M is the algorithmic complexity of multiplication on the type V.
77  The compile-time algorithmic complexity of this function is O(lg(power)+v(power)), where v(power) is the number of 1s in the binary representation of power.
78  */
79  namespace binary_right_to_left {
80 
81  /// For types for which operator*() cannot be computed at compile-time, this variant unrolls the exponentiation at compile-time.
82  namespace dyn {
83 
84  template<
85  typename V, ///< The type of the value to exponentiate.
86  long P ///< The power to which it should be raised. This should be positive.
87  >
88  struct pow;
89 
90  template<
91  typename V ///< The type of the value to exponentiate.
92  >
93  struct pow<V, 0> : public std::binary_function<V, long, V> {
94  typedef typename std::binary_function<V, long, V>::result_type result_type;
95  typedef typename std::binary_function<V, long, V>::first_argument_type first_argument_type;
96 
97  static constexpr result_type __fastcall FORCE_INLINE result(first_argument_type res, const first_argument_type) noexcept(true) {
98  return result_type(res);
99  }
100  static constexpr result_type __fastcall FORCE_INLINE result(const first_argument_type) noexcept(true) {
101  return result_type(1);
102  }
103  };
104 
105  template<
106  typename V ///< The type of the value to exponentiate.
107  >
108  struct pow<V, 1> : public std::binary_function<V, long, V> {
109  typedef typename std::binary_function<V, long, V>::result_type result_type;
110  typedef typename std::binary_function<V, long, V>::first_argument_type first_argument_type;
111 
112  static constexpr result_type __fastcall FORCE_INLINE result(first_argument_type res, const first_argument_type a) noexcept(true) {
113  return result_type(res*a);
114  }
115  static constexpr result_type __fastcall FORCE_INLINE result(const first_argument_type a) noexcept(true) {
116  return result_type(a);
117  }
118  };
119 
120  template<
121  typename V, ///< The type of the value to exponentiate.
122  long P ///< The power to which it should be raised. This should be positive.
123  >
124  struct pow : public std::binary_function<V, long, V> {
125  typedef typename std::binary_function<V, long, V>::result_type result_type;
126  typedef typename std::binary_function<V, long, V>::first_argument_type first_argument_type;
127 
128  static constexpr long power=P; ///< The positive power to which the value should be raised.
129 
130  static const result_type __fastcall FORCE_INLINE result(first_argument_type res, const first_argument_type z) noexcept(true) {
131  BOOST_STATIC_ASSERT(power>=0);
132  if (power&1) {
133  res*=z;
134  }
135  return pow<result_type, (power>>1)>::result(res, z*z);
136  }
137  /**
138  The runtime-algorithmic complexity of this function is O(M), where M is the algorithmic complexity of multiplication on the type V.
139  The compile-time algorithmic complexity of this function is O(lg(power)+v(power)), where v(power) is the number of 1s in the binary representation of power.
140  */
141  static const result_type __fastcall FORCE_INLINE result(const first_argument_type a) noexcept(true) {
142  BOOST_STATIC_ASSERT(power>=0);
143  return pow<result_type, power>::result(1, a);
144  }
145  };
146 
147  }
148 
149  /// For types for which operator*() can be computed at compile-time, this variant computes the entire exponentiation at compile-time.
150  namespace mpl {
151 
152  namespace private_ {
153 
154  template<
155  unsigned long P,
156  long Res,
157  long V
158  >
159  struct pow;
160 
161  template<
162  long Res,
163  long Z
164  >
165  struct pow<0, Res, Z> {
166  enum {
167  result=Res
168  };
169  };
170  template<
171  unsigned long P,
172  long Res,
173  long Z
174  >
175  struct pow {
176  static constexpr unsigned long result=pow<(P>>1), ((P&1) ? Res*Z : Res), Z*Z>::result;
177  };
178 
179  }
180 
181  template<
182  long V, ///< The value to exponentiate.
183  long P ///< The power to which the value should be raised. Negative powers are computed as 1/V^|P|.
184  >
185  struct pow;
186 
187  template<
188  long V ///< The value to exponentiate.
189  >
190  struct pow<V, 0> : public std::binary_function<long, long, long> {
191  static constexpr long power=0; ///< The power to which the value should be raised. Negative powers are computed as 1/V^|P|.
192  static constexpr long value=V; ///< The value to exponentiate.
193  static constexpr long result=1;
194  };
195  template<
196  long V ///< The value to exponentiate.
197  >
198  struct pow<V, 1> : public std::binary_function<long, long, long> {
199  static constexpr long power=1; ///< The power to which the value should be raised. Negative powers are computed as 1/V^|P|.
200  static constexpr long value=V; ///< The value to exponentiate.
201  static constexpr long result=value;
202  };
203 
204  /// The class to compute the result of raising a value V to an integer power P, at compile-time.
205  /**
206  The runtime algorithmic-complexity of this function is O(1).
207  The compile-time algorithmic complexity of this function is O(lg(power)+v(power)), where v(power) is the number of 1s in the binary representation of power.
208  */
209  template<
210  long V, ///< The value to exponentiate.
211  long P ///< The power to which the value should be raised. Negative powers are computed as 1/V^|P|.
212  >
213  struct pow : public std::binary_function<long, long, long> {
214  static constexpr long power=P; ///< The power to which the value should be raised.
215  static constexpr long value=V; ///< The value to exponentiate. Negative powers are computed as 1/V^|P|.
216 
217  private:
218  static constexpr long mod_power=modulus<power>::result;
219  static constexpr long int_result=private_::pow<(mod_power>>1), ((mod_power&1) ? value : 1), value*value>::result;
220 
221  public:
222  static constexpr long result=(sign<power>::result ? int_result : 1/int_result);
223  };
224 
225  }
226 
227  }
228 
229  /// At compile-time, using the binary-right-to-left method, unroll the exponentiation of raising the value V to the integer power of P.
230  /**
231  The runtime-algorithmic complexity of this function is O(M), where M is the algorithmic complexity of multiplication on the type V.
232  The compile-time algorithmic complexity of this function is O(lg(power)+v(power)), where v(power) is the number of 1s in the binary representation of power.
233 
234  \param v The value to be exponentiated.
235  */
236  template<
237  long P, ///< The integer power. Negative powers are computed as 1/V^|P|.
238  typename V ///< The type of the value to be exponentiated.
239  > inline __attribute__((const)) const V __fastcall FORCE_INLINE
240  pow(const V v) {
241  return invert_if<V, sign<P>::result>::result(binary_right_to_left::dyn::pow<V, modulus<P>::result>::result(v));
242  }
243 
244 } }
245 
246 #ifdef _MSC_VER
247 # pragma warning(pop)
248 #endif