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