main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:31 for Gecode by
doxygen
1.8.4
gecode
support
random.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
* Mikael Lagerkvist <lagerkvist@gecode.org>
6
*
7
* Copyright:
8
* Christian Schulte, 2005
9
* Mikael Lagerkvist, 2005
10
*
11
* Last modified:
12
* $Date: 2012-09-07 11:29:57 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
13
* $Revision: 13061 $
14
*
15
* This file is part of Gecode, the generic constraint
16
* development environment:
17
* http://www.gecode.org
18
*
19
* Permission is hereby granted, free of charge, to any person obtaining
20
* a copy of this software and associated documentation files (the
21
* "Software"), to deal in the Software without restriction, including
22
* without limitation the rights to use, copy, modify, merge, publish,
23
* distribute, sublicense, and/or sell copies of the Software, and to
24
* permit persons to whom the Software is furnished to do so, subject to
25
* the following conditions:
26
*
27
* The above copyright notice and this permission notice shall be
28
* included in all copies or substantial portions of the Software.
29
*
30
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37
*
38
*/
39
40
namespace
Gecode {
namespace
Support {
41
49
template
<
unsigned
int
m,
unsigned
int
a,
unsigned
int
q,
unsigned
int
r>
50
class
LinearCongruentialGenerator
{
51
private
:
53
static
const
unsigned
int
max = 1UL<<31;
55
unsigned
int
s;
57
unsigned
int
next(
void
);
58
public
:
60
void
seed
(
unsigned
int
s);
62
LinearCongruentialGenerator
(
unsigned
int
s = 1);
64
unsigned
int
seed
(
void
)
const
;
66
unsigned
int
operator ()
(
unsigned
int
n
);
68
size_t
size
(
void
)
const
;
69
};
70
71
template
<
unsigned
int
m,
unsigned
int
a,
unsigned
int
q,
unsigned
int
r>
72
forceinline
unsigned
int
73
LinearCongruentialGenerator<m,a,q,r>::next
(
void
) {
74
s =
a
*(s%q) -
r
*(s/q);
75
unsigned
int
res = s;
76
if
(s==0) s = 1;
77
return
res;
78
}
79
template
<
unsigned
int
m,
unsigned
int
a,
unsigned
int
q,
unsigned
int
r>
80
forceinline
void
81
LinearCongruentialGenerator<m,a,q,r>::seed
(
unsigned
int
_s) {
82
s = _s % m;
83
if
(s == 0) s = 1;
84
}
85
template
<
unsigned
int
m,
unsigned
int
a,
unsigned
int
q,
unsigned
int
r>
86
forceinline
87
LinearCongruentialGenerator<m,a,q,r>::
88
LinearCongruentialGenerator
(
unsigned
int
_s) {
89
seed(_s);
90
}
91
template
<
unsigned
int
m,
unsigned
int
a,
unsigned
int
q,
unsigned
int
r>
92
forceinline
unsigned
int
93
LinearCongruentialGenerator<m,a,q,r>::seed
(
void
)
const
{
94
return
s;
95
}
96
template
<
unsigned
int
m,
unsigned
int
a,
unsigned
int
q,
unsigned
int
r>
97
forceinline
unsigned
int
98
LinearCongruentialGenerator<m,a,q,r>::operator ()
(
unsigned
int
n
) {
99
unsigned
int
x1 = next() & ((1<<16)-1);
100
unsigned
int
x2 = next() & ((1<<16)-1);
101
if
(n < 2)
return
0;
102
double
d
=
static_cast<
double
>
(((x1<<16) | x2) %
max
) /
max
;
103
unsigned
int
val =
static_cast<
unsigned
int
>
(n *
d
);
104
return
(val < n) ? val : (n-1);
105
}
106
template
<
unsigned
int
m,
unsigned
int
a,
unsigned
int
q,
unsigned
int
r>
107
forceinline
size_t
108
LinearCongruentialGenerator<m,a,q,r>::size
(
void
)
const
{
109
return
sizeof
(
LinearCongruentialGenerator<m,a,q,r>
);
110
}
111
112
123
typedef
LinearCongruentialGenerator<2147483647, 48271, 44488, 3399>
124
RandomGenerator
;
125
126
}}
127
128
// STATISTICS: support-any