main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:35 for Gecode by
doxygen
1.8.3.1
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-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
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
}
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
190
SqrOps::pow
(
IntType
x
)
const
{
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