main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Feb 8 2021 00:00:00 for Gecode by
doxygen
1.8.20
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
* 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
34
namespace
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
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:767
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:767
Gecode::Int::Arithmetic::SqrOps::exp
int exp(void) const
Return exponent.
Definition:
pow-ops.hpp:177
Gecode::Int::Arithmetic::PowOps::fnroot
int fnroot(int x) const
Return where x must be non-negative and .
Definition:
pow-ops.hpp:115
Gecode::Int::Arithmetic::PowOps::exp
int exp(void) const
Return exponent.
Definition:
pow-ops.hpp:50
Gecode::Int::Arithmetic::PowOps::powle
bool powle(long long int r, int x) const
Test whether .
Definition:
pow-ops.hpp:132
Gecode::Int::Arithmetic::SqrOps::fnroot
int fnroot(int x) const
Return where x must be non-negative and .
Definition:
pow-ops.hpp:203
Gecode::Int::Arithmetic::PowOps::pow
IntType pow(IntType x) const
Return where .
Definition:
pow-ops.hpp:61
Gecode
Gecode toplevel namespace
u
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Gecode::Int::Arithmetic::SqrOps::pow
IntType pow(IntType x) const
Return .
Definition:
pow-ops.hpp:188
Gecode::Int::Arithmetic::SqrOps::tpow
int tpow(int x) const
Return truncated to integer limits.
Definition:
pow-ops.hpp:193
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::Int::Arithmetic::PowOps::even
bool even(void) const
Return whether exponent is even.
Definition:
pow-ops.hpp:45
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition:
int.hh:116
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition:
macros.hpp:56
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:240
Gecode::Int::Arithmetic::SqrOps::cnroot
int cnroot(int x) const
Return where x must be non-negative and .
Definition:
pow-ops.hpp:220
Gecode::Support::IntType
IntType
Description of integer types.
Definition:
int-type.hpp:39
Gecode::Int::Arithmetic::PowOps::tpow
int tpow(int x) const
Return where truncated to integer limits.
Definition:
pow-ops.hpp:75
Gecode::Int::Arithmetic::PowOps::cnroot
int cnroot(int x) const
Return where x must be non-negative and .
Definition:
pow-ops.hpp:153
Gecode::Int::Arithmetic::PowOps::PowOps
PowOps(int n)
Initialize with exponent n.
Definition:
pow-ops.hpp:37
Gecode::Int::Limits::min
const int min
Smallest allowed integer value.
Definition:
int.hh:118
forceinline
#define forceinline
Definition:
config.hpp:192
Gecode::Int::Arithmetic::SqrOps::even
bool even(void) const
Return whether exponent is even.
Definition:
pow-ops.hpp:172
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::Int::Arithmetic::PowOps::n
int n
The exponent and root index.
Definition:
arithmetic.hh:330
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
Gecode::Int::Arithmetic::PowOps::powgr
bool powgr(long long int r, int x) const
Test whether .
Definition:
pow-ops.hpp:94