Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
pow-ops.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2012
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Int { namespace Arithmetic {
35 
37  PowOps::PowOps(int n0) : n(n0) {}
38 
39  forceinline bool
40  PowOps::even(int m) {
41  return (m & 1) == 0;
42  }
43 
44  forceinline bool
45  PowOps::even(void) const {
46  return even(n);
47  }
48 
49  forceinline int
50  PowOps::exp(void) const {
51  return n;
52  }
53 
54  forceinline void
55  PowOps::exp(int m) {
56  n=m;
57  }
58 
59  template<class IntType>
60  inline IntType
62  int m = n;
63  IntType p = 1;
64  do {
65  if (even(m)) {
66  x *= x; m >>= 1;
67  } else {
68  p *= x; m--;
69  }
70  } while (m > 0);
71  return p;
72  }
73 
74  inline int
75  PowOps::tpow(int _x) const {
76  int m = n;
77  long long int p = 1;
78  long long int x = _x;
79  do {
80  if (even(m)) {
81  x *= x; m >>= 1;
82  } else {
83  p *= x; m--;
84  }
85  if (p > Limits::max)
86  return Limits::max+1;
87  if (p < Limits::min)
88  return Limits::min-1;
89  } while (m > 0);
90  return static_cast<int>(p);
91  }
92 
93  forceinline bool
94  PowOps::powgr(long long int r, int x) const {
95  assert(r >= 0);
96  int m = n;
97  long long int y = r;
98  long long int p = 1;
99  do {
100  if (even(m)) {
101  y *= y; m >>= 1;
102  if (y > x)
103  return true;
104  } else {
105  p *= y; m--;
106  if (p > x)
107  return true;
108  }
109  } while (m > 0);
110  assert(y <= x);
111  return false;
112  }
113 
114  inline int
115  PowOps::fnroot(int x) const {
116  if (x < 2)
117  return x;
118  /*
119  * We look for l such that: l^n <= x < (l+1)^n
120  */
121  long long int l = 1;
122  long long int u = x;
123  do {
124  long long int m = (l + u) >> 1;
125  if (powgr(m,x)) u=m; else l=m;
126  } while (l+1 < u);
127  assert((pow(l) <= x) && (x < pow(l+1)));
128  return static_cast<int>(l);
129  }
130 
131  forceinline bool
132  PowOps::powle(long long int r, int x) const {
133  assert(r >= 0);
134  int m = n;
135  long long int y = r;
136  long long int p = 1;
137  do {
138  if (even(m)) {
139  y *= y; m >>= 1;
140  if (y >= x)
141  return false;
142  } else {
143  p *= y; m--;
144  if (p >= x)
145  return false;
146  }
147  } while (m > 0);
148  assert(y < x);
149  return true;
150  }
151 
152  inline int
153  PowOps::cnroot(int x) const {
154  if (x < 2)
155  return x;
156  /*
157  * We look for u such that: (u-1)^n < x <= u^n
158  */
159  long long int l = 1;
160  long long int u = x;
161  do {
162  long long int m = (l + u) >> 1;
163  if (powle(m,x)) l=m; else u=m;
164  } while (l+1 < u);
165  assert((pow(u-1) < x) && (x <= pow(u)));
166  return static_cast<int>(u);
167  }
168 
169 
170 
171  forceinline bool
172  SqrOps::even(void) const {
173  return true;
174  }
175 
176  forceinline int
177  SqrOps::exp(void) const {
178  return 2;
179  }
180 
181  forceinline void
182  SqrOps::exp(int) {
183  GECODE_NEVER;
184  }
185 
186  template<class IntType>
187  inline IntType
189  return x * x;
190  }
191 
192  inline int
193  SqrOps::tpow(int _x) const {
194  long long int x = _x;
195  if (x*x > Limits::max)
196  return Limits::max+1;
197  if (x*x < Limits::min)
198  return Limits::min-1;
199  return static_cast<int>(x*x);
200  }
201 
202  inline int
203  SqrOps::fnroot(int x) const {
204  if (x < 2)
205  return x;
206  /*
207  * We look for l such that: l^2 <= x < (l+1)^2
208  */
209  long long int l = 1;
210  long long int u = x;
211  do {
212  long long int m = (l + u) >> 1;
213  if (m*m > x) u=m; else l=m;
214  } while (l+1 < u);
215  assert((pow(l) <= x) && (x < pow(l+1)));
216  return static_cast<int>(l);
217  }
218 
219  inline int
220  SqrOps::cnroot(int x) const {
221  if (x < 2)
222  return x;
223  /*
224  * We look for u such that: (u-1)^n < x <= u^n
225  */
226  long long int l = 1;
227  long long int u = x;
228  do {
229  long long int m = (l + u) >> 1;
230  if (m*m < x) l=m; else u=m;
231  } while (l+1 < u);
232  assert((pow(u-1) < x) && (x <= pow(u)));
233  return static_cast<int>(u);
234  }
235 
236 }}}
237 
238 // STATISTICS: int-other
239 
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int fnroot(int x) const
Return where x must be non-negative and .
Definition: pow-ops.hpp:115
#define forceinline
Definition: config.hpp:185
const int max
Largest allowed integer value.
Definition: int.hh:116
bool powgr(long long int r, int x) const
Test whether .
Definition: pow-ops.hpp:94
const int min
Smallest allowed integer value.
Definition: int.hh:118
bool even(void) const
Return whether exponent is even.
Definition: pow-ops.hpp:172
int cnroot(int x) const
Return where x must be non-negative and .
Definition: pow-ops.hpp:153
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
PowOps(int n)
Initialize with exponent n.
Definition: pow-ops.hpp:37
bool powle(long long int r, int x) const
Test whether .
Definition: pow-ops.hpp:132
int tpow(int x) const
Return truncated to integer limits.
Definition: pow-ops.hpp:193
int n
The exponent and root index.
Definition: arithmetic.hh:330
IntType pow(IntType x) const
Return where .
Definition: pow-ops.hpp:61
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
int fnroot(int x) const
Return where x must be non-negative and .
Definition: pow-ops.hpp:203
Post propagator for SetVar x
Definition: set.hh:767
int cnroot(int x) const
Return where x must be non-negative and .
Definition: pow-ops.hpp:220
int tpow(int x) const
Return where truncated to integer limits.
Definition: pow-ops.hpp:75
Gecode toplevel namespace
bool even(void) const
Return whether exponent is even.
Definition: pow-ops.hpp:45
IntType pow(IntType x) const
Return .
Definition: pow-ops.hpp:188
IntType
Description of integer types.
Definition: int-type.hpp:39
int exp(void) const
Return exponent.
Definition: pow-ops.hpp:177
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
int exp(void) const
Return exponent.
Definition: pow-ops.hpp:50