this repo has no description
dekker.one
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
34namespace Gecode { namespace Int { namespace Arithmetic {
35
36 forceinline
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
61 PowOps::pow(IntType x) const {
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
188 SqrOps::pow(IntType x) const {
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