main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:27 for Gecode by
doxygen
1.8.4
gecode
int
arithmetic
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
40
forceinline
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
65
PowOps::pow
(
IntType
x
)
const
{
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
192
SqrOps::pow
(
IntType
x
)
const
{
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