Generated on Sat May 25 2013 18:00:35 for Gecode by doxygen 1.8.3.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-02-08 16:47:00 +0100 (Fri, 08 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13278 $
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  } while (m > 0);
92  return static_cast<int>(p);
93  }
94 
95  forceinline bool
96  PowOps::powgr(long long int r, int x) const {
97  assert(r >= 0);
98  int m = n;
99  long long int y = r;
100  long long int p = 1;
101  do {
102  if (even(m)) {
103  y *= y; m >>= 1;
104  if (y > x)
105  return true;
106  } else {
107  p *= y; m--;
108  if (p > x)
109  return true;
110  }
111  } while (m > 0);
112  assert(y <= x);
113  return false;
114  }
115 
116  inline int
117  PowOps::fnroot(int x) const {
118  if (x < 2)
119  return x;
120  /*
121  * We look for l such that: l^n <= x < (l+1)^n
122  */
123  long long int l = 1;
124  long long int u = x;
125  do {
126  long long int m = (l + u) >> 1;
127  if (powgr(m,x)) u=m; else l=m;
128  } while (l+1 < u);
129  assert((pow(l) <= x) && (x < pow(l+1)));
130  return static_cast<int>(l);
131  }
132 
133  forceinline bool
134  PowOps::powle(long long int r, int x) const {
135  assert(r >= 0);
136  int m = n;
137  long long int y = r;
138  long long int p = 1;
139  do {
140  if (even(m)) {
141  y *= y; m >>= 1;
142  if (y >= x)
143  return false;
144  } else {
145  p *= y; m--;
146  if (p >= x)
147  return false;
148  }
149  } while (m > 0);
150  assert(y < x);
151  return true;
152  }
153 
154  inline int
155  PowOps::cnroot(int x) const {
156  if (x < 2)
157  return x;
158  /*
159  * We look for u such that: (u-1)^n < x <= u^n
160  */
161  long long int l = 1;
162  long long int u = x;
163  do {
164  long long int m = (l + u) >> 1;
165  if (powle(m,x)) l=m; else u=m;
166  } while (l+1 < u);
167  assert((pow(u-1) < x) && (x <= pow(u)));
168  return static_cast<int>(u);
169  }
170 
171 
172 
173  forceinline bool
174  SqrOps::even(void) const {
175  return true;
176  }
177 
178  forceinline int
179  SqrOps::exp(void) const {
180  return 2;
181  }
182 
183  forceinline void
184  SqrOps::exp(int) {
185  GECODE_NEVER;
186  }
187 
188  template<class IntType>
189  inline IntType
191  return x * x;
192  }
193 
194  inline int
195  SqrOps::tpow(int _x) const {
196  long long int x = _x;
197  if (x*x > Limits::max)
198  return Limits::max+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