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 * Mikael Lagerkvist <lagerkvist@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2005
9 * Mikael Lagerkvist, 2005
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#include <algorithm>
37
38namespace Gecode { namespace Support {
39
40 /** \brief Template for linear congruential generators
41 *
42 * This class template defines a simple class for linear
43 * congruential generators.
44 *
45 * \ingroup FuncSupport
46 */
47 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
48 class LinearCongruentialGenerator {
49 private:
50 /// The maximum size of random numbers generated.
51 static const unsigned int max = 1UL<<31;
52 /// Current seed value
53 unsigned int s;
54 /// Returns a random integer from the interval \f$[0\ldots n)\f$
55 unsigned int u(unsigned int n);
56 /// Returns a random integer from the interval \f$[0\ldots n)\f$
57 unsigned long long int ull(unsigned long long int n);
58 public:
59 /// Set the current seed to \a s
60 void seed(unsigned int s);
61 /// Construct the generator instance with seed \a s
62 LinearCongruentialGenerator(unsigned int s = 1);
63 /// Return current seed
64 unsigned int seed(void) const;
65 /// Generate next number in series
66 unsigned int next(void);
67 /// Returns a random integer from the interval \f$[0\ldots n)\f$
68 template<class Type>
69 Type operator ()(Type n);
70 /// Returns a random integer from the interval \f$[0\ldots n)\f$
71 int operator ()(int n);
72 /// Returns a random integer from the interval \f$[0\ldots n)\f$
73 unsigned int operator ()(unsigned int n);
74 /// Returns a random integer from the interval \f$[0\ldots n)\f$
75 long long int operator ()(long long int n);
76 /// Report size occupied
77 size_t size(void) const;
78 };
79
80 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
81 forceinline unsigned int
82 LinearCongruentialGenerator<m,a,q,r>::next(void) {
83 s = a*(s%q) - r*(s/q);
84 unsigned int res = s;
85 if (s==0) s = 1;
86 return res;
87 }
88 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
89 forceinline void
90 LinearCongruentialGenerator<m,a,q,r>::seed(unsigned int _s) {
91 s = _s % m;
92 if (s == 0) s = 1;
93 }
94 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
95 forceinline
96 LinearCongruentialGenerator<m,a,q,r>::
97 LinearCongruentialGenerator(unsigned int _s) {
98 seed(_s);
99 }
100 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
101 forceinline unsigned int
102 LinearCongruentialGenerator<m,a,q,r>::seed(void) const {
103 return s;
104 }
105
106 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
107 forceinline unsigned int
108 LinearCongruentialGenerator<m,a,q,r>::u(unsigned int n) {
109 unsigned int x1 = next() & ((1U<<16)-1U);
110 unsigned int x2 = next() & ((1U<<16)-1U);
111 if (n < 2)
112 return 0;
113 double d = static_cast<double>(((x1<<16) | x2) % max) / max;
114 unsigned int val = static_cast<unsigned int>(n * d);
115 return (val < n) ? val : (n-1);
116 }
117 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
118 forceinline unsigned long long int
119 LinearCongruentialGenerator<m,a,q,r>::ull(unsigned long long int n) {
120 if (n <= UINT_MAX)
121 return u(static_cast<unsigned int>(n));
122 unsigned long long int x1 = next() & ((1LLU<<16)-1LLU);
123 unsigned long long int x2 = next() & ((1LLU<<16)-1LLU);
124 unsigned long long int x3 = next() & ((1LLU<<16)-1LLU);
125 unsigned long long int x4 = next() & ((1LLU<<16)-1LLU);
126 if (n < 2)
127 return 0;
128 return ((x1 << 48) | (x2 << 32) | (x3 << 16) | x4) % n;
129 }
130
131 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
132 template<class Type>
133 forceinline Type
134 LinearCongruentialGenerator<m,a,q,r>::operator ()(Type n) {
135 return static_cast<Type>(ull(static_cast<unsigned long long int>(n)));
136 }
137 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
138 forceinline unsigned int
139 LinearCongruentialGenerator<m,a,q,r>::operator ()(unsigned int n) {
140 return u(n);
141 }
142 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
143 forceinline int
144 LinearCongruentialGenerator<m,a,q,r>::operator ()(int n) {
145 return (n < 0) ? 0 :
146 static_cast<int>(u(static_cast<unsigned int>(n)));
147 }
148 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
149 forceinline long long int
150 LinearCongruentialGenerator<m,a,q,r>::operator ()(long long int n) {
151 return (n < 0) ? 0 :
152 static_cast<long long int>
153 (ull(static_cast<unsigned long long int>(n)));
154 }
155 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
156 forceinline size_t
157 LinearCongruentialGenerator<m,a,q,r>::size(void) const {
158 return sizeof(LinearCongruentialGenerator<m,a,q,r>);
159 }
160
161
162 /** \brief Default values for linear congruential generator
163 *
164 * While this pseudo-random number generator is not a good source of
165 * randomness, it is still an acceptable choice for many
166 * applications. The choice of values is taken from D. E. Knuth,
167 * The Art of Computer Programming, Vol 2, Seminumerical Algorithms,
168 * 3rd edition.
169 *
170 * \ingroup FuncSupport
171 */
172 typedef LinearCongruentialGenerator<2147483647, 48271, 44488, 3399>
173 RandomGenerator;
174
175}}
176
177// STATISTICS: support-any