Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 2398 lines (2094 sloc) 64.633 kB
747f3cf @complexmath Changed Phobos to use the Boost license. Currently, all public domai…
complexmath authored
1 // Written in the D programming language.
8f79f3e @braddr phobos 2.003
braddr authored
2
99870f8 @braddr phobos 0.135
braddr authored
3 /**
28781bf @jmdavis Old deprecations which were not properly taken care of previously.
jmdavis authored
4 Facilities for random number generation.
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
5
6 The new-style generator objects hold their own state so they are
7 immune of threading issues. The generators feature a number of
8 well-known and well-documented methods of generating random
9 numbers. An overall fast and reliable means to generate random numbers
10 is the $(D_PARAM Mt19937) generator, which derives its name from
5a0134d @andralex Fixed 672 broken links
andralex authored
11 "$(LUCKY Mersenne Twister) with a period of 2 to the power of
12 19937". In memory-constrained situations, $(LUCKY linear congruential)
13 generators such as $(D MinstdRand0) and $(D MinstdRand) might be
14 useful. The standard library provides an alias $(D_PARAM Random) for
15 whichever generator it considers the most fit for the target
16 environment.
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
17
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
18 Example:
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
19
20 ----
f19d95a @andralex added randomSample.
andralex authored
21 // Generate a uniformly-distributed integer in the range [0, 14]
6663566 @andralex added uniformDistribution, fixed docs
andralex authored
22 auto i = uniform(0, 15);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
23 // Generate a uniformly-distributed real in the range [0, 100$(RPAREN)
6663566 @andralex added uniformDistribution, fixed docs
andralex authored
24 // using a specific random generator
25 Random gen;
26 auto r = uniform(0.0L, 100.0L, gen);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
27 ----
28
29 In addition to random number generators, this module features
30 distributions, which skew a generator's output statistical
31 distribution in various ways. So far the uniform distribution for
32 integers and real numbers have been implemented.
33
046e1b3 @WalterBright add source links
WalterBright authored
34 Source: $(PHOBOSSRC std/_random.d)
35
747f3cf @complexmath Changed Phobos to use the Boost license. Currently, all public domai…
complexmath authored
36 Macros:
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
37
747f3cf @complexmath Changed Phobos to use the Boost license. Currently, all public domai…
complexmath authored
38 WIKI = Phobos/StdRandom
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
39
40
34c7d2f @WebDrake Tweaks to authorship & comments.
WebDrake authored
41 Copyright: Copyright Andrei Alexandrescu 2008 - 2009, Joseph Rushton Wakeling 2012.
747f3cf @complexmath Changed Phobos to use the Boost license. Currently, all public domai…
complexmath authored
42 License: <a href="http://www.boost.org/LICENSE_1_0.txt">Boost License 1.0</a>.
43 Authors: $(WEB erdani.org, Andrei Alexandrescu)
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
44 Masahiro Nakagawa (Xorshift randome generator)
34c7d2f @WebDrake Tweaks to authorship & comments.
WebDrake authored
45 $(WEB braingam.es, Joseph Rushton Wakeling) (Algorithm D for random sampling)
747f3cf @complexmath Changed Phobos to use the Boost license. Currently, all public domai…
complexmath authored
46 Credits: The entire random number library architecture is derived from the
47 excellent $(WEB open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf, C++0X)
48 random number facility proposed by Jens Maurer and contributed to by
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
49 researchers at the Fermi laboratory(excluding Xorshift).
84477a5 @donc Move Boost copyright declaration from ddoc to normal comment. Fixes u…
donc authored
50 */
51 /*
747f3cf @complexmath Changed Phobos to use the Boost license. Currently, all public domai…
complexmath authored
52 Copyright Andrei Alexandrescu 2008 - 2009.
53 Distributed under the Boost Software License, Version 1.0.
54 (See accompanying file LICENSE_1_0.txt or copy at
55 http://www.boost.org/LICENSE_1_0.txt)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
56 */
35a12fe @braddr phobos 0.76
braddr authored
57 module std.random;
cf1172c @braddr phobos 0.19
braddr authored
58
4aded5d @braddr break std.random's dependency on std.datetime
braddr authored
59 import std.algorithm, std.c.time, std.conv, std.exception,
461c2f6 @jkrempus Added the ziggurat algorithm.
authored
60 std.math, std.numeric, std.range, std.traits, std.mathspecial,
61 std.typecons,
4aded5d @braddr break std.random's dependency on std.datetime
braddr authored
62 core.thread, core.time;
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
63 import std.string : format;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
64
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
65 version(unittest) import std.typetuple;
66
67
cf1172c @braddr phobos 0.19
braddr authored
68 // Segments of the code in this file Copyright (c) 1997 by Rick Booth
69 // From "Inner Loops" by Rick Booth, Addison-Wesley
70
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
71 // Work derived from:
72
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
73 /*
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
74 A C-program for MT19937, with initialization improved 2002/1/26.
75 Coded by Takuji Nishimura and Makoto Matsumoto.
76
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
77 Before using, initialize the state by using init_genrand(seed)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
78 or init_by_array(init_key, key_length).
79
80 Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
81 All rights reserved.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
82
83 Redistribution and use in source and binary forms, with or without
84 modification, are permitted provided that the following conditions
85 are met:
86
87 1. Redistributions of source code must retain the above copyright
88 notice, this list of conditions and the following disclaimer.
89
90 2. Redistributions in binary form must reproduce the above copyright
91 notice, this list of conditions and the following disclaimer in the
92 documentation and/or other materials provided with the distribution.
93
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
94 3. The names of its contributors may not be used to endorse or promote
95 products derived from this software without specific prior written
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
96 permission.
97
98 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
99 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
100 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
101 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
102 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
103 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
104 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
105 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
106 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
107 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
108 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
109
110
111 Any feedback is very welcome.
112 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
113 email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
114 */
115
c7ea30e @braddr phobos 0.65
braddr authored
116
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
117 /**
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
118 * Test if Rng is a random-number generator. The overload
119 * taking a ElementType also makes sure that the Rng generates
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
120 * values of that type.
121 *
122 * A random-number generator has at least the following features:
123 * $(UL
124 * $(LI it's an InputRange)
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
125 * $(LI it has a 'bool isUniformRandom' field readable in CTFE)
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
126 * )
127 */
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
128 template isUniformRNG(Rng, ElementType)
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
129 {
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
130 enum bool isUniformRNG = isInputRange!Rng &&
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
131 is(typeof(Rng.front) == ElementType) &&
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
132 is(typeof(
133 {
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
134 static assert(Rng.isUniformRandom); //tag
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
135 }));
136 }
137
138 /**
139 * ditto
140 */
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
141 template isUniformRNG(Rng)
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
142 {
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
143 enum bool isUniformRNG = isInputRange!Rng &&
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
144 is(typeof(
145 {
146 static assert(Rng.isUniformRandom); //tag
147 }));
148 }
149
150 /**
151 * Test if Rng is seedable. The overload
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
152 * taking a SeedType also makes sure that the Rng can be seeded with SeedType.
5892180 @jpf91 Fix isSeedable documentation
jpf91 authored
153 *
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
154 * A seedable random-number generator has the following additional features:
155 * $(UL
156 * $(LI it has a 'seed(ElementType)' function)
157 * )
158 */
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
159 template isSeedable(Rng, SeedType)
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
160 {
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
161 enum bool isSeedable = isUniformRNG!(Rng) &&
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
162 is(typeof(
163 {
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
164 Rng r = void; // can define a Rng object
165 r.seed(SeedType.init); // can seed a Rng
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
166 }));
167 }
168
169 ///ditto
170 template isSeedable(Rng)
171 {
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
172 enum bool isSeedable = isUniformRNG!Rng &&
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
173 is(typeof(
174 {
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
175 Rng r = void; // can define a Rng object
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
176 r.seed(typeof(r.front).init); // can seed a Rng
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
177 }));
178 }
179
180 unittest
181 {
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
182 struct NoRng
183 {
184 @property uint front() {return 0;}
185 @property bool empty() {return false;}
186 void popFront() {}
187 }
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
188 assert(!isUniformRNG!(NoRng, uint));
189 assert(!isUniformRNG!(NoRng));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
190 assert(!isSeedable!(NoRng, uint));
191 assert(!isSeedable!(NoRng));
cdd6a85 @jmdavis Remove unneeded C stuff and trailing whitespace from std.random.
jmdavis authored
192
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
193 struct NoRng2
194 {
195 @property uint front() {return 0;}
196 @property bool empty() {return false;}
197 void popFront() {}
cdd6a85 @jmdavis Remove unneeded C stuff and trailing whitespace from std.random.
jmdavis authored
198
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
199 enum isUniformRandom = false;
200 }
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
201 assert(!isUniformRNG!(NoRng2, uint));
202 assert(!isUniformRNG!(NoRng2));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
203 assert(!isSeedable!(NoRng2, uint));
204 assert(!isSeedable!(NoRng2));
cdd6a85 @jmdavis Remove unneeded C stuff and trailing whitespace from std.random.
jmdavis authored
205
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
206 struct NoRng3
207 {
208 @property bool empty() {return false;}
209 void popFront() {}
cdd6a85 @jmdavis Remove unneeded C stuff and trailing whitespace from std.random.
jmdavis authored
210
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
211 enum isUniformRandom = true;
212 }
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
213 assert(!isUniformRNG!(NoRng3, uint));
214 assert(!isUniformRNG!(NoRng3));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
215 assert(!isSeedable!(NoRng3, uint));
216 assert(!isSeedable!(NoRng3));
cdd6a85 @jmdavis Remove unneeded C stuff and trailing whitespace from std.random.
jmdavis authored
217
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
218 struct validRng
219 {
220 @property uint front() {return 0;}
221 @property bool empty() {return false;}
222 void popFront() {}
cdd6a85 @jmdavis Remove unneeded C stuff and trailing whitespace from std.random.
jmdavis authored
223
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
224 enum isUniformRandom = true;
225 }
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
226 assert(isUniformRNG!(validRng, uint));
227 assert(isUniformRNG!(validRng));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
228 assert(!isSeedable!(validRng, uint));
229 assert(!isSeedable!(validRng));
230
231 struct seedRng
232 {
233 @property uint front() {return 0;}
234 @property bool empty() {return false;}
235 void popFront() {}
236 void seed(uint val){}
237 enum isUniformRandom = true;
238 }
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
239 assert(isUniformRNG!(seedRng, uint));
240 assert(isUniformRNG!(seedRng));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
241 assert(isSeedable!(seedRng, uint));
242 assert(isSeedable!(seedRng));
324b541 @jpf91 Add isRandomNumberGenerator template
jpf91 authored
243 }
244
245 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
246 Linear Congruential generator.
247 */
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
248 struct LinearCongruentialEngine(UIntType, UIntType a, UIntType c, UIntType m)
76def7a @jmdavis Fix Issue# 8026.
jmdavis authored
249 if(isUnsigned!UIntType)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
250 {
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
251 ///Mark this as a Rng
252 enum bool isUniformRandom = true;
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
253 /// Does this generator have a fixed range? ($(D_PARAM true)).
254 enum bool hasFixedRange = true;
255 /// Lowest generated value ($(D 1) if $(D c == 0), $(D 0) otherwise).
256 enum UIntType min = ( c == 0 ? 1 : 0 );
257 /// Highest generated value ($(D modulus - 1)).
258 enum UIntType max = m - 1;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
259 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
260 The parameters of this distribution. The random number is $(D_PARAM x
261 = (x * multipler + increment) % modulus).
262 */
263 enum UIntType multiplier = a;
264 ///ditto
265 enum UIntType increment = c;
266 ///ditto
267 enum UIntType modulus = m;
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
268
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
269 static assert(isIntegral!(UIntType));
270 static assert(m == 0 || a < m);
271 static assert(m == 0 || c < m);
272 static assert(m == 0 ||
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
273 (cast(ulong)a * (m-1) + c) % m == (c < a ? c - a + m : c - a));
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
274
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
275 // Check for maximum range
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
276 private static ulong gcd(ulong a, ulong b)
277 {
278 while (b)
279 {
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
280 auto t = b;
281 b = a % b;
282 a = t;
283 }
284 return a;
285 }
286
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
287 private static ulong primeFactorsOnly(ulong n)
288 {
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
289 ulong result = 1;
290 ulong iter = 2;
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
291 for (; n >= iter * iter; iter += 2 - (iter == 2))
292 {
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
293 if (n % iter) continue;
294 result *= iter;
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
295 do
296 {
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
297 n /= iter;
298 } while (n % iter == 0);
299 }
300 return result * n;
301 }
ff54d86 @dsimcha bugzilla 2977: std.random.unpredictableSeed() should use thread ID s…
dsimcha authored
302
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
303 unittest
304 {
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
305 static assert(primeFactorsOnly(100) == 10);
306 //writeln(primeFactorsOnly(11));
307 static assert(primeFactorsOnly(11) == 11);
308 static assert(primeFactorsOnly(7 * 7 * 7 * 11 * 15 * 11) == 7 * 11 * 15);
309 static assert(primeFactorsOnly(129 * 2) == 129 * 2);
310 // enum x = primeFactorsOnly(7 * 7 * 7 * 11 * 15);
311 // static assert(x == 7 * 11 * 15);
312 }
ff54d86 @dsimcha bugzilla 2977: std.random.unpredictableSeed() should use thread ID s…
dsimcha authored
313
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
314 private static bool properLinearCongruentialParameters(ulong m,
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
315 ulong a, ulong c)
316 {
6902b79 @andralex Issue 3738 - MinstdRand0 and MinstdRand very poor performance
andralex authored
317 if (m == 0)
318 {
319 static if (is(UIntType == uint))
320 {
321 // Assume m is uint.max + 1
322 m = (1uL << 32);
323 }
324 else
325 {
326 return false;
327 }
328 }
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
329 // Bounds checking
6902b79 @andralex Issue 3738 - MinstdRand0 and MinstdRand very poor performance
andralex authored
330 if (a == 0 || a >= m || c >= m) return false;
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
331 // c and m are relatively prime
332 if (c > 0 && gcd(c, m) != 1) return false;
333 // a - 1 is divisible by all prime factors of m
334 if ((a - 1) % primeFactorsOnly(m)) return false;
335 // if a - 1 is multiple of 4, then m is a multiple of 4 too.
336 if ((a - 1) % 4 == 0 && m % 4) return false;
337 // Passed all tests
338 return true;
339 }
ff54d86 @dsimcha bugzilla 2977: std.random.unpredictableSeed() should use thread ID s…
dsimcha authored
340
6ecb612 @andralex Added static checks for the parameters of the linear congruential gen…
andralex authored
341 // check here
342 static assert(c == 0 || properLinearCongruentialParameters(m, a, c),
343 "Incorrect instantiation of LinearCongruentialEngine");
344
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
345 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
346 Constructs a $(D_PARAM LinearCongruentialEngine) generator seeded with
347 $(D x0).
348 */
349 this(UIntType x0)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
350 {
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
351 seed(x0);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
352 }
353
354 /**
355 (Re)seeds the generator.
356 */
357 void seed(UIntType x0 = 1)
358 {
359 static if (c == 0)
360 {
361 enforce(x0, "Invalid (zero) seed for "
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
362 ~ LinearCongruentialEngine.stringof);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
363 }
364 _x = modulus ? (x0 % modulus) : x0;
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
365 popFront();
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
366 }
367
368 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
369 Advances the random sequence.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
370 */
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
371 void popFront()
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
372 {
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
373 static if (m)
6902b79 @andralex Issue 3738 - MinstdRand0 and MinstdRand very poor performance
andralex authored
374 {
375 static if (is(UIntType == uint) && m == uint.max)
376 {
377 immutable ulong
378 x = (cast(ulong) a * _x + c),
379 v = x >> 32,
380 w = x & uint.max;
381 immutable y = cast(uint)(v + w);
382 _x = (y < v || y == uint.max) ? (y + 1) : y;
383 }
384 else static if (is(UIntType == uint) && m == int.max)
385 {
386 immutable ulong
387 x = (cast(ulong) a * _x + c),
388 v = x >> 31,
389 w = x & int.max;
390 immutable uint y = cast(uint)(v + w);
391 _x = (y >= int.max) ? (y - int.max) : y;
392 }
393 else
394 {
395 _x = cast(UIntType) ((cast(ulong) a * _x + c) % m);
396 }
397 }
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
398 else
6902b79 @andralex Issue 3738 - MinstdRand0 and MinstdRand very poor performance
andralex authored
399 {
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
400 _x = a * _x + c;
6902b79 @andralex Issue 3738 - MinstdRand0 and MinstdRand very poor performance
andralex authored
401 }
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
402 }
403
404 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
405 Returns the current number in the random sequence.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
406 */
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
407 @property UIntType front()
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
408 {
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
409 return _x;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
410 }
432e3fd @andralex Replaced std.contracts with std.exception throughout
andralex authored
411
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
412 ///
413 @property typeof(this) save()
414 {
415 return this;
416 }
417
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
418 /**
0c14299 @andralex See changelog - bunch of bug fixes and a couple additions for release…
andralex authored
419 Always $(D false) (random generators are infinite ranges).
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
420 */
421 enum bool empty = false;
ff54d86 @dsimcha bugzilla 2977: std.random.unpredictableSeed() should use thread ID s…
dsimcha authored
422
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
423 /**
424 Compares against $(D_PARAM rhs) for equality.
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
425 */
1b0d981 fix opEquals type
Walter Bright authored
426 bool opEquals(ref const LinearCongruentialEngine rhs) const
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
427 {
428 return _x == rhs._x;
429 }
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
430
6902b79 @andralex Issue 3738 - MinstdRand0 and MinstdRand very poor performance
andralex authored
431 private UIntType _x = m ? (a + c) % m : (a + c);
432 }
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
433
434 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
435 Define $(D_PARAM LinearCongruentialEngine) generators with well-chosen
436 parameters. $(D MinstdRand0) implements Park and Miller's "minimal
437 standard" $(WEB
438 wikipedia.org/wiki/Park%E2%80%93Miller_random_number_generator,
439 generator) that uses 16807 for the multiplier. $(D MinstdRand)
440 implements a variant that has slightly better spectral behavior by
441 using the multiplier 48271. Both generators are rather simplistic.
442
443 Example:
444
445 ----
446 // seed with a constant
447 auto rnd0 = MinstdRand0(1);
0c14299 @andralex See changelog - bunch of bug fixes and a couple additions for release…
andralex authored
448 auto n = rnd0.front; // same for each run
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
449 // Seed with an unpredictable value
450 rnd0.seed(unpredictableSeed);
0c14299 @andralex See changelog - bunch of bug fixes and a couple additions for release…
andralex authored
451 n = rnd0.front; // different across runs
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
452 ----
453 */
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
454 alias LinearCongruentialEngine!(uint, 16807, 0, 2147483647) MinstdRand0;
455 /// ditto
456 alias LinearCongruentialEngine!(uint, 48271, 0, 2147483647) MinstdRand;
457
458 unittest
459 {
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
460 assert(isForwardRange!MinstdRand);
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
461 assert(isUniformRNG!MinstdRand);
462 assert(isUniformRNG!MinstdRand0);
463 assert(isUniformRNG!(MinstdRand, uint));
464 assert(isUniformRNG!(MinstdRand0, uint));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
465 assert(isSeedable!MinstdRand);
466 assert(isSeedable!MinstdRand0);
467 assert(isSeedable!(MinstdRand, uint));
468 assert(isSeedable!(MinstdRand0, uint));
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
469
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
470 // The correct numbers are taken from The Database of Integer Sequences
471 // http://www.research.att.com/~njas/sequences/eisBTfry00128.txt
472 auto checking0 = [
473 16807UL,282475249,1622650073,984943658,1144108930,470211272,
474 101027544,1457850878,1458777923,2007237709,823564440,1115438165,
475 1784484492,74243042,114807987,1137522503,1441282327,16531729,
476 823378840,143542612 ];
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
477 //auto rnd0 = MinstdRand0(1);
478 MinstdRand0 rnd0;
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
479
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
480 foreach (e; checking0)
481 {
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
482 assert(rnd0.front == e);
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
483 rnd0.popFront();
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
484 }
485 // Test the 10000th invocation
486 // Correct value taken from:
487 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
488 rnd0.seed();
0c14299 @andralex See changelog - bunch of bug fixes and a couple additions for release…
andralex authored
489 popFrontN(rnd0, 9999);
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
490 assert(rnd0.front == 1043618065);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
491
492 // Test MinstdRand
493 auto checking = [48271UL,182605794,1291394886,1914720637,2078669041,
494 407355683];
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
495 //auto rnd = MinstdRand(1);
496 MinstdRand rnd;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
497 foreach (e; checking)
498 {
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
499 assert(rnd.front == e);
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
500 rnd.popFront();
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
501 }
502
503 // Test the 10000th invocation
504 // Correct value taken from:
505 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2461.pdf
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
506 rnd.seed();
0c14299 @andralex See changelog - bunch of bug fixes and a couple additions for release…
andralex authored
507 popFrontN(rnd, 9999);
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
508 assert(rnd.front == 399268537);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
509 }
510
511 /**
5a0134d @andralex Fixed 672 broken links
andralex authored
512 The $(LUCKY Mersenne Twister) generator.
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
513 */
76def7a @jmdavis Fix Issue# 8026.
jmdavis authored
514 struct MersenneTwisterEngine(UIntType, size_t w, size_t n, size_t m, size_t r,
515 UIntType a, size_t u, size_t s,
516 UIntType b, size_t t,
517 UIntType c, size_t l)
518 if(isUnsigned!UIntType)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
519 {
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
520 ///Mark this as a Rng
521 enum bool isUniformRandom = true;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
522 /**
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
523 Parameter for the generator.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
524 */
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
525 enum size_t wordSize = w;
526 enum size_t stateSize = n;
527 enum size_t shiftSize = m;
528 enum size_t maskBits = r;
529 enum UIntType xorMask = a;
530 enum UIntType temperingU = u;
531 enum size_t temperingS = s;
532 enum UIntType temperingB = b;
533 enum size_t temperingT = t;
534 enum UIntType temperingC = c;
535 enum size_t temperingL = l;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
536
537 /// Smallest generated value (0).
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
538 enum UIntType min = 0;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
539 /// Largest generated value.
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
540 enum UIntType max =
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
541 w == UIntType.sizeof * 8 ? UIntType.max : (1u << w) - 1;
542 /// The default seed value.
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
543 enum UIntType defaultSeed = 5489u;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
544
545 static assert(1 <= m && m <= n);
546 static assert(0 <= r && 0 <= u && 0 <= s && 0 <= t && 0 <= l);
547 static assert(r <= w && u <= w && s <= w && t <= w && l <= w);
548 static assert(0 <= a && 0 <= b && 0 <= c);
549 static assert(a <= max && b <= max && c <= max);
550
551 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
552 Constructs a MersenneTwisterEngine object.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
553 */
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
554 this(UIntType value)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
555 {
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
556 seed(value);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
557 }
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
558
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
559 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
560 Seeds a MersenneTwisterEngine object.
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
561 Note:
562 This seed function gives 2^32 starting points. To allow the RNG to be started in any one of its
563 internal states use the seed overload taking an InputRange.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
564 */
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
565 void seed()(UIntType value = defaultSeed)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
566 {
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
567 static if (w == UIntType.sizeof * 8)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
568 {
569 mt[0] = value;
570 }
571 else
572 {
573 static assert(max + 1 > 0);
574 mt[0] = value % (max + 1);
575 }
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
576 for (mti = 1; mti < n; ++mti)
577 {
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
578 mt[mti] =
29f3cc2 @andralex std.math: minor change in approxEqual.
andralex authored
579 cast(UIntType)
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
580 (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> (w - 2))) + mti);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
581 /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
582 /* In the previous versions, MSBs of the seed affect */
583 /* only MSBs of the array mt[]. */
584 /* 2002/01/09 modified by Makoto Matsumoto */
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
585 //mt[mti] &= ResultType.max;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
586 /* for >32 bit machines */
587 }
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
588 popFront();
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
589 }
590
591 /**
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
592 Seeds a MersenneTwisterEngine object using an InputRange.
593
594 Throws:
595 $(D Exception) if the InputRange didn't provide enough elements to seed the generator.
596 The number of elements required is the 'n' template parameter of the MersenneTwisterEngine struct.
597
598 Examples:
599 ----------------
600 Mt19937 gen;
601 gen.seed(map!((a) => unpredictableSeed)(repeat(0)));
602 ----------------
603 */
604 void seed(T)(T range) if(isInputRange!T && is(Unqual!(ElementType!T) == UIntType))
605 {
606 size_t j;
607 for(j = 0; j < n && !range.empty; ++j, range.popFront())
608 {
609 mt[j] = range.front;
610 }
611
612 mti = n;
613 if(range.empty && j < n)
614 {
615 throw new Exception(format("MersenneTwisterEngine.seed: Input range didn't provide enough"
616 " elements: Need %s elemnets.", n));
617 }
618
619 popFront();
620 }
621
622 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
623 Advances the generator.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
624 */
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
625 void popFront()
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
626 {
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
627 if (mti == size_t.max) seed();
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
628 enum UIntType
629 upperMask = ~((cast(UIntType) 1u <<
630 (UIntType.sizeof * 8 - (w - r))) - 1),
631 lowerMask = (cast(UIntType) 1u << r) - 1;
9b4dcc1 invariant => immutable
Walter Bright authored
632 static immutable UIntType mag01[2] = [0x0UL, a];
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
633
634 ulong y = void;
635
636 if (mti >= n)
637 {
638 /* generate N words at one time */
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
639
640 int kk = 0;
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
641 const limit1 = n - m;
642 for (; kk < limit1; ++kk)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
643 {
644 y = (mt[kk] & upperMask)|(mt[kk + 1] & lowerMask);
29f3cc2 @andralex std.math: minor change in approxEqual.
andralex authored
645 mt[kk] = cast(UIntType) (mt[kk + m] ^ (y >> 1)
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
646 ^ mag01[cast(UIntType) y & 0x1U]);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
647 }
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
648 const limit2 = n - 1;
649 for (; kk < limit2; ++kk)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
650 {
651 y = (mt[kk] & upperMask)|(mt[kk + 1] & lowerMask);
29f3cc2 @andralex std.math: minor change in approxEqual.
andralex authored
652 mt[kk] = cast(UIntType) (mt[kk + (m -n)] ^ (y >> 1)
653 ^ mag01[cast(UIntType) y & 0x1U]);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
654 }
655 y = (mt[n -1] & upperMask)|(mt[0] & lowerMask);
29f3cc2 @andralex std.math: minor change in approxEqual.
andralex authored
656 mt[n - 1] = cast(UIntType) (mt[m - 1] ^ (y >> 1)
657 ^ mag01[cast(UIntType) y & 0x1U]);
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
658
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
659 mti = 0;
660 }
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
661
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
662 y = mt[mti++];
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
663
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
664 /* Tempering */
665 y ^= (y >> temperingU);
666 y ^= (y << temperingS) & temperingB;
667 y ^= (y << temperingT) & temperingC;
668 y ^= (y >> temperingL);
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
669
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
670 _y = cast(UIntType) y;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
671 }
672
673 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
674 Returns the current random value.
675 */
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
676 @property UIntType front()
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
677 {
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
678 if (mti == size_t.max) seed();
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
679 return _y;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
680 }
681
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
682 ///
683 @property typeof(this) save()
684 {
685 return this;
686 }
687
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
688 /**
689 Always $(D false).
690 */
691 enum bool empty = false;
ff54d86 @dsimcha bugzilla 2977: std.random.unpredictableSeed() should use thread ID s…
dsimcha authored
692
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
693 private UIntType mt[n];
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
694 private size_t mti = size_t.max; /* means mt is not initialized */
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
695 UIntType _y = UIntType.max;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
696 }
697
698 /**
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
699 A $(D MersenneTwisterEngine) instantiated with the parameters of the
700 original engine $(WEB math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html,
701 MT19937), generating uniformly-distributed 32-bit numbers with a
702 period of 2 to the power of 19937. Recommended for random number
703 generation unless memory is severely restricted, in which case a $(D
704 LinearCongruentialEngine) would be the generator of choice.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
705
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
706 Example:
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
707
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
708 ----
709 // seed with a constant
710 Mt19937 gen;
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
711 auto n = gen.front; // same for each run
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
712 // Seed with an unpredictable value
713 gen.seed(unpredictableSeed);
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
714 n = gen.front; // different across runs
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
715 ----
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
716 */
717 alias MersenneTwisterEngine!(uint, 32, 624, 397, 31, 0x9908b0df, 11, 7,
718 0x9d2c5680, 15, 0xefc60000, 18)
719 Mt19937;
720
721 unittest
722 {
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
723 assert(isUniformRNG!Mt19937);
724 assert(isUniformRNG!(Mt19937, uint));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
725 assert(isSeedable!Mt19937);
726 assert(isSeedable!(Mt19937, uint));
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
727 assert(isSeedable!(Mt19937, typeof(map!((a) => unpredictableSeed)(repeat(0)))));
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
728 Mt19937 gen;
0c14299 @andralex See changelog - bunch of bug fixes and a couple additions for release…
andralex authored
729 popFrontN(gen, 9999);
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
730 assert(gen.front == 4123659995);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
731 }
732
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
733 unittest
734 {
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
735 Mt19937 gen;
736
737 assertThrown(gen.seed(map!((a) => unpredictableSeed)(repeat(0, 623))));
738
739 gen.seed(map!((a) => unpredictableSeed)(repeat(0, 624)));
740 //infinite Range
741 gen.seed(map!((a) => unpredictableSeed)(repeat(0)));
742 }
743
744 unittest
745 {
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
746 uint a, b;
747 {
748 Mt19937 gen;
749 a = gen.front;
750 }
751 {
752 Mt19937 gen;
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
753 gen.popFront();
0c14299 @andralex See changelog - bunch of bug fixes and a couple additions for release…
andralex authored
754 //popFrontN(gen, 1); // skip 1 element
8b87031 @andralex fixed unlisted bug in MersenneTwister.popFront
andralex authored
755 b = gen.front;
756 }
757 assert(a != b);
758 }
759
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
760
761 /**
762 * Xorshift generator using 32bit algorithm.
763 *
764 * Implemented according to $(WEB www.jstatsoft.org/v08/i14/paper, Xorshift RNGs).
765 *
766 * $(BOOKTABLE $(TEXTWITHCOMMAS Supporting bits are below, $(D bits) means second parameter of XorshiftEngine.),
767 * $(TR $(TH bits) $(TH period))
768 * $(TR $(TD 32) $(TD 2^32 - 1))
769 * $(TR $(TD 64) $(TD 2^64 - 1))
770 * $(TR $(TD 96) $(TD 2^96 - 1))
771 * $(TR $(TD 128) $(TD 2^128 - 1))
772 * $(TR $(TD 160) $(TD 2^160 - 1))
773 * $(TR $(TD 192) $(TD 2^192 - 2^32))
774 * )
775 */
776 struct XorshiftEngine(UIntType, UIntType bits, UIntType a, UIntType b, UIntType c)
76def7a @jmdavis Fix Issue# 8026.
jmdavis authored
777 if(isUnsigned!UIntType)
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
778 {
779 static assert(bits == 32 || bits == 64 || bits == 96 || bits == 128 || bits == 160 || bits == 192,
780 "Supporting bits are 32, 64, 96, 128, 160 and 192. " ~ to!string(bits) ~ " is not supported.");
781
782
783 public:
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
784 ///Mark this as a Rng
785 enum bool isUniformRandom = true;
2f7bcb8 @repeatedly Add max / min properties to Xorshift
repeatedly authored
786 /// Always $(D false) (random generators are infinite ranges).
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
787 enum empty = false;
2f7bcb8 @repeatedly Add max / min properties to Xorshift
repeatedly authored
788 /// Smallest generated value.
789 enum UIntType min = 0;
790 /// Largest generated value.
791 enum UIntType max = UIntType.max;
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
792
793
794 private:
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
795 enum size = bits / 32;
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
796
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
797 static if (bits == 32)
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
798 UIntType[size] seeds_ = [2463534242];
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
799 else static if (bits == 64)
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
800 UIntType[size] seeds_ = [123456789, 362436069];
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
801 else static if (bits == 96)
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
802 UIntType[size] seeds_ = [123456789, 362436069, 521288629];
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
803 else static if (bits == 128)
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
804 UIntType[size] seeds_ = [123456789, 362436069, 521288629, 88675123];
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
805 else static if (bits == 160)
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
806 UIntType[size] seeds_ = [123456789, 362436069, 521288629, 88675123, 5783321];
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
807 else
808 { // 192bits
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
809 UIntType[size] seeds_ = [123456789, 362436069, 521288629, 88675123, 5783321, 6615241];
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
810 UIntType value_;
811 }
812
813
814 public:
815 /**
816 * Constructs a $(D XorshiftEngine) generator seeded with $(D_PARAM x0).
817 */
818 @safe
819 this(UIntType x0)
820 {
821 seed(x0);
822 }
823
824
825 /**
826 * (Re)seeds the generator.
827 */
828 @safe
829 nothrow void seed(UIntType x0)
830 {
831 // Initialization routine from MersenneTwisterEngine.
832 foreach (i, e; seeds_)
833 seeds_[i] = x0 = cast(UIntType)(1812433253U * (x0 ^ (x0 >> 30)) + i + 1);
834
835 // All seeds must not be 0.
836 sanitizeSeeds(seeds_);
837
838 popFront();
839 }
840
841
842 /**
843 * Returns the current number in the random sequence.
844 */
845 @property @safe
846 nothrow UIntType front()
847 {
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
848 static if (bits == 192)
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
849 return value_;
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
850 else
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
851 return seeds_[size - 1];
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
852 }
853
854
855 /**
856 * Advances the random sequence.
857 */
858 @safe
859 nothrow void popFront()
860 {
861 UIntType temp;
862
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
863 static if (bits == 32)
864 {
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
865 temp = seeds_[0] ^ (seeds_[0] << a);
866 temp = temp >> b;
867 seeds_[0] = temp ^ (temp << c);
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
868 }
869 else static if (bits == 64)
870 {
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
871 temp = seeds_[0] ^ (seeds_[0] << a);
872 seeds_[0] = seeds_[1];
873 seeds_[1] = seeds_[1] ^ (seeds_[1] >> c) ^ temp ^ (temp >> b);
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
874 }
875 else static if (bits == 96)
876 {
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
877 temp = seeds_[0] ^ (seeds_[0] << a);
878 seeds_[0] = seeds_[1];
879 seeds_[1] = seeds_[2];
880 seeds_[2] = seeds_[2] ^ (seeds_[2] >> c) ^ temp ^ (temp >> b);
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
881 }
882 else static if (bits == 128)
883 {
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
884 temp = seeds_[0] ^ (seeds_[0] << a);
885 seeds_[0] = seeds_[1];
886 seeds_[1] = seeds_[2];
887 seeds_[2] = seeds_[3];
888 seeds_[3] = seeds_[3] ^ (seeds_[3] >> c) ^ temp ^ (temp >> b);
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
889 }
890 else static if (bits == 160)
891 {
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
892 temp = seeds_[0] ^ (seeds_[0] >> a);
893 seeds_[0] = seeds_[1];
894 seeds_[1] = seeds_[2];
895 seeds_[2] = seeds_[3];
896 seeds_[3] = seeds_[4];
897 seeds_[4] = seeds_[4] ^ (seeds_[4] >> c) ^ temp ^ (temp >> b);
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
898 }
899 else
900 { // 192bits
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
901 temp = seeds_[0] ^ (seeds_[0] >> a);
902 seeds_[0] = seeds_[1];
903 seeds_[1] = seeds_[2];
904 seeds_[2] = seeds_[3];
905 seeds_[3] = seeds_[4];
906 seeds_[4] = seeds_[4] ^ (seeds_[4] << c) ^ temp ^ (temp << b);
907 value_ = seeds_[4] + (seeds_[5] += 362437);
908 }
909 }
910
911
912 /**
913 * Captures a range state.
914 */
915 @property
916 typeof(this) save()
917 {
918 return this;
919 }
920
921
922 /**
923 * Compares against $(D_PARAM rhs) for equality.
924 */
925 @safe
926 nothrow bool opEquals(ref const XorshiftEngine rhs) const
927 {
928 return seeds_ == rhs.seeds_;
929 }
930
931
932 private:
933 @safe
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
934 static nothrow void sanitizeSeeds(ref UIntType[size] seeds)
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
935 {
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
936 for (uint i; i < seeds.length; i++)
937 {
b5058f6 @repeatedly Fix std.random.XorshiftEngine for 64bit environment
repeatedly authored
938 if (seeds[i] == 0)
939 seeds[i] = i + 1;
940 }
941 }
942
943
944 unittest
945 {
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
946 static if (size == 4) // Other bits too
b5058f6 @repeatedly Fix std.random.XorshiftEngine for 64bit environment
repeatedly authored
947 {
088a228 @jmdavis Fixed incorrectly named enum.
jmdavis authored
948 UIntType[size] seeds = [1, 0, 0, 4];
b5058f6 @repeatedly Fix std.random.XorshiftEngine for 64bit environment
repeatedly authored
949
950 sanitizeSeeds(seeds);
951
952 assert(seeds == [1, 2, 3, 4]);
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
953 }
954 }
955 }
956
957
958 /**
959 * Define $(D XorshiftEngine) generators with well-chosen parameters. See each bits examples of "Xorshift RNGs".
960 * $(D Xorshift) is a Xorshift128's alias because 128bits implementation is mostly used.
961 *
962 * Example:
963 * -----
964 * // Seed with a constant
965 * auto rnd = Xorshift(1);
966 * auto num = rnd.front; // same for each run
967 *
968 * // Seed with an unpredictable value
969 * rnd.seed(unpredictableSeed());
970 * num = rnd.front; // different across runs
971 * -----
972 */
973 alias XorshiftEngine!(uint, 32, 13, 17, 5) Xorshift32;
974 alias XorshiftEngine!(uint, 64, 10, 13, 10) Xorshift64; /// ditto
975 alias XorshiftEngine!(uint, 96, 10, 5, 26) Xorshift96; /// ditto
976 alias XorshiftEngine!(uint, 128, 11, 8, 19) Xorshift128; /// ditto
977 alias XorshiftEngine!(uint, 160, 2, 1, 4) Xorshift160; /// ditto
978 alias XorshiftEngine!(uint, 192, 2, 1, 4) Xorshift192; /// ditto
979 alias Xorshift128 Xorshift; /// ditto
980
981
982 unittest
983 {
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
984 assert(isForwardRange!Xorshift);
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
985 assert(isUniformRNG!Xorshift);
986 assert(isUniformRNG!(Xorshift, uint));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
987 assert(isSeedable!Xorshift);
988 assert(isSeedable!(Xorshift, uint));
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
989
990 // Result from reference implementation.
991 auto checking = [
992 [2463534242UL, 267649, 551450, 53765, 108832, 215250, 435468, 860211, 660133, 263375],
993 [362436069UL, 2113136921, 19051112, 3010520417, 951284840, 1213972223, 3173832558, 2611145638, 2515869689, 2245824891],
994 [521288629UL, 1950277231, 185954712, 1582725458, 3580567609, 2303633688, 2394948066, 4108622809, 1116800180, 3357585673],
995 [88675123UL, 3701687786, 458299110, 2500872618, 3633119408, 516391518, 2377269574, 2599949379, 717229868, 137866584],
996 [5783321UL, 93724048, 491642011, 136638118, 246438988, 238186808, 140181925, 533680092, 285770921, 462053907],
997 [0UL, 246875399, 3690007200, 1264581005, 3906711041, 1866187943, 2481925219, 2464530826, 1604040631, 3653403911]
998 ];
999
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
1000 foreach (I, Type; TypeTuple!(Xorshift32, Xorshift64, Xorshift96, Xorshift128, Xorshift160, Xorshift192))
1001 {
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
1002 Type rnd;
1003
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
1004 foreach (e; checking[I])
1005 {
951491f @repeatedly Added Xorshift to std.random
repeatedly authored
1006 assert(rnd.front == e);
1007 rnd.popFront();
1008 }
1009 }
1010 }
1011
1012
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1013 /**
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1014 A "good" seed for initializing random number engines. Initializing
1015 with $(D_PARAM unpredictableSeed) makes engines generate different
1016 random number sequences every run.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1017
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1018 Example:
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1019
1020 ----
1021 auto rnd = Random(unpredictableSeed);
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
1022 auto n = rnd.front;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1023 ...
edb5c50 @complexmath This commit includes all the changes necessary for Phobos to run agai…
complexmath authored
1024 ----
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1025 */
1026
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
1027 @property uint unpredictableSeed()
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1028 {
c433c36 @andralex Fixed predictability in unpredictableSeed.
andralex authored
1029 static bool seeded;
1030 static MinstdRand0 rand;
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
1031 if (!seeded)
1032 {
ff54d86 @dsimcha bugzilla 2977: std.random.unpredictableSeed() should use thread ID s…
dsimcha authored
1033 uint threadID = cast(uint) cast(void*) Thread.getThis();
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
1034 rand.seed((getpid() + threadID) ^ cast(uint) TickDuration.currSystemTick().length);
f2fa28e @andralex Fixed fix in unpredictableSeed.
andralex authored
1035 seeded = true;
c433c36 @andralex Fixed predictability in unpredictableSeed.
andralex authored
1036 }
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
1037 rand.popFront();
4aded5d @braddr break std.random's dependency on std.datetime
braddr authored
1038 return cast(uint) (TickDuration.currSystemTick().length ^ rand.front);
a9c935e @andralex * Made unpredictableSeed return different numbers every call (except …
andralex authored
1039 }
1040
1041 unittest
1042 {
1043 // not much to test here
1044 auto a = unpredictableSeed;
1045 static assert(is(typeof(a) == uint));
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1046 }
1047
1048 /**
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
1049 The "default", "favorite", "suggested" random number generator type on
1050 the current platform. It is an alias for one of the previously-defined
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1051 generators. You may want to use it if (1) you need to generate some
1052 nice random numbers, and (2) you don't care for the minutiae of the
1053 method being used.
1054 */
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1055
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1056 alias Mt19937 Random;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1057
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
1058 unittest
1059 {
d99c33c @jpf91 Rename isRandomNumberGenerator to isUniformRNG
jpf91 authored
1060 assert(isUniformRNG!Random);
1061 assert(isUniformRNG!(Random, uint));
1c07d0a @jpf91 Reimplement isRandomNumberGenerator
jpf91 authored
1062 assert(isSeedable!Random);
1063 assert(isSeedable!(Random, uint));
1064 }
1065
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1066 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1067 Global random number generator used by various functions in this
1068 module whenever no generator is specified. It is allocated per-thread
1069 and initialized to an unpredictable value for each thread.
1070 */
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
1071 @property ref Random rndGen()
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1072 {
1073 static Random result;
1074 static bool initialized;
1075 if (!initialized)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1076 {
c0be641 @jpf91 Add seed(InputRange) overload to MersenneTwisterEngine
jpf91 authored
1077 static if(isSeedable!(Random, typeof(map!((a) => unpredictableSeed)(repeat(0)))))
1078 result.seed(map!((a) => unpredictableSeed)(repeat(0)));
1079 else
1080 result = Random(unpredictableSeed);
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1081 initialized = true;
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1082 }
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1083 return result;
1084 }
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1085
1086 /**
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1087 Generates a number between $(D a) and $(D b). The $(D boundaries)
1088 parameter controls the shape of the interval (open vs. closed on
1089 either side). Valid values for $(D boundaries) are $(D "[]"), $(D
1090 "$(LPAREN)]"), $(D "[$(RPAREN)"), and $(D "()"). The default interval
017c1e8 @andralex bugzilla 3785 + improvements
andralex authored
1091 is closed to the left and open to the right. The version that does not
1092 take $(D urng) uses the default generator $(D rndGen).
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1093
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1094 Example:
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1095
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1096 ----
1097 Random gen(unpredictableSeed);
1098 // Generate an integer in [0, 1023]
1099 auto a = uniform(0, 1024, gen);
1100 // Generate a float in [0, 1$(RPAREN)
1101 auto a = uniform(0.0f, 1.0f, gen);
1102 ----
1103 */
017c1e8 @andralex bugzilla 3785 + improvements
andralex authored
1104 auto uniform(string boundaries = "[)", T1, T2)
1105 (T1 a, T2 b) if (!is(CommonType!(T1, T2) == void))
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1106 {
c64411a @andralex added template constraint to uniform()
andralex authored
1107 return uniform!(boundaries, T1, T2, Random)(a, b, rndGen);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1108 }
1109
1110 unittest
1111 {
1112 MinstdRand0 gen;
1113 foreach (i; 0 .. 20)
1114 {
735c2ad @jmdavis Changes required for issue# 6277.
jmdavis authored
1115 auto x = uniform(0.0, 15.0, gen);
935c1ac @andralex fix for bug 2921
andralex authored
1116 assert(0 <= x && x < 15);
1117 }
1118 foreach (i; 0 .. 20)
1119 {
1120 auto x = uniform!"[]"('a', 'z', gen);
1121 assert('a' <= x && x <= 'z');
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1122 }
432e3fd @andralex Replaced std.contracts with std.exception throughout
andralex authored
1123
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
1124 foreach (i; 0 .. 20)
791ee04 @dsimcha Bug 4171: std.random.uniform does not work for a range of characters
dsimcha authored
1125 {
1126 auto x = uniform('a', 'z', gen);
1127 assert('a' <= x && x < 'z');
1128 }
432e3fd @andralex Replaced std.contracts with std.exception throughout
andralex authored
1129
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
1130 foreach(i; 0 .. 20)
1131 {
1132 immutable ubyte a = 0;
1133 immutable ubyte b = 15;
1134 auto x = uniform(a, b, gen);
1135 assert(a <= x && x < b);
1136 }
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1137 }
1138
017c1e8 @andralex bugzilla 3785 + improvements
andralex authored
1139 // Implementation of uniform for floating-point types
852aa7d @kennytm Remove the DDoc specialization for std.random.uniform.
kennytm authored
1140 /// ditto
017c1e8 @andralex bugzilla 3785 + improvements
andralex authored
1141 auto uniform(string boundaries = "[)",
1142 T1, T2, UniformRandomNumberGenerator)
1143 (T1 a, T2 b, ref UniformRandomNumberGenerator urng)
1144 if (isFloatingPoint!(CommonType!(T1, T2)))
1145 {
1146 alias Unqual!(CommonType!(T1, T2)) NumberType;
1147 static if (boundaries[0] == '(')
1148 {
1149 NumberType _a = nextafter(cast(NumberType) a, NumberType.infinity);
1150 }
1151 else
1152 {
1153 NumberType _a = a;
1154 }
1155 static if (boundaries[1] == ')')
1156 {
1157 NumberType _b = nextafter(cast(NumberType) b, -NumberType.infinity);
1158 }
1159 else
1160 {
1161 NumberType _b = b;
1162 }
1163 enforce(_a <= _b,
1164 text("std.random.uniform(): invalid bounding interval ",
1165 boundaries[0], a, ", ", b, boundaries[1]));
1166 NumberType result =
1167 _a + (_b - _a) * cast(NumberType) (urng.front - urng.min)
1168 / (urng.max - urng.min);
1169 urng.popFront();
1170 return result;
1171 }
1172
1173 // Implementation of uniform for integral types
1174 auto uniform(string boundaries = "[)",
1175 T1, T2, UniformRandomNumberGenerator)
1176 (T1 a, T2 b, ref UniformRandomNumberGenerator urng)
1177 if (isIntegral!(CommonType!(T1, T2)) || isSomeChar!(CommonType!(T1, T2)))
1178 {
1179 alias Unqual!(CommonType!(T1, T2)) ResultType;
1180 // We handle the case "[)' as the common case, and we adjust all
1181 // other cases to fit it.
1182 static if (boundaries[0] == '(')
1183 {
1184 enforce(cast(ResultType) a < ResultType.max,
1185 text("std.random.uniform(): invalid left bound ", a));
1186 ResultType min = cast(ResultType) a + 1;
1187 }
1188 else
1189 {
1190 ResultType min = a;
1191 }
1192 static if (boundaries[1] == ']')
1193 {
1194 enforce(min <= cast(ResultType) b,
1195 text("std.random.uniform(): invalid bounding interval ",
1196 boundaries[0], a, ", ", b, boundaries[1]));
1197 if (b == ResultType.max && min == ResultType.min)
1198 {
1199 // Special case - all bits are occupied
1200 return .uniform!ResultType(urng);
1201 }
1202 auto count = unsigned(b - min) + 1u;
1203 static assert(count.min == 0);
1204 }
1205 else
1206 {
1207 enforce(min < cast(ResultType) b,
1208 text("std.random.uniform(): invalid bounding interval ",
1209 boundaries[0], a, ", ", b, boundaries[1]));
1210 auto count = unsigned(b - min);
1211 static assert(count.min == 0);
1212 }
1213 assert(count != 0);
1214 if (count == 1) return min;
1215 alias typeof(count) CountType;
1216 static assert(CountType.min == 0);
1217 auto bucketSize = 1u + (CountType.max - count + 1) / count;
1218 CountType r;
1219 do
1220 {
1221 r = cast(CountType) (uniform!CountType(urng) / bucketSize);
1222 }
1223 while (r >= count);
1224 return cast(typeof(return)) (min + r);
1225 }
1226
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1227 unittest
1228 {
1229 auto gen = Mt19937(unpredictableSeed);
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
1230 static assert(isForwardRange!(typeof(gen)));
1231
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1232 auto a = uniform(0, 1024, gen);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1233 assert(0 <= a && a <= 1024);
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1234 auto b = uniform(0.0f, 1.0f, gen);
1235 assert(0 <= b && b < 1, to!string(b));
1236 auto c = uniform(0.0, 1.0);
1237 assert(0 <= c && c < 1);
ab43002 @MartinNowak add unittests for std.random.uniform
MartinNowak authored
1238
1239 foreach(T; TypeTuple!(char, wchar, dchar, byte, ubyte, short, ushort,
1240 int, uint, long, ulong, float, double, real))
1241 {
1242 T lo = 0, hi = 100;
1243 T init = uniform(lo, hi);
1244 size_t i = 50;
1245 while (--i && uniform(lo, hi) == init) {}
1246 assert(i > 0);
1247 }
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1248 }
1249
1250 /**
017c1e8 @andralex bugzilla 3785 + improvements
andralex authored
1251 Generates a uniformly-distributed number in the range $(D [T.min,
1252 T.max]) for any integral type $(D T). If no random number generator is
1253 passed, uses the default $(D rndGen).
1254 */
1255 auto uniform(T, UniformRandomNumberGenerator)
1256 (ref UniformRandomNumberGenerator urng)
1257 if (isIntegral!T || isSomeChar!T)
1258 {
1259 auto r = urng.front;
1260 urng.popFront();
1261 static if (T.sizeof <= r.sizeof)
1262 {
1263 return cast(T) r;
1264 }
1265 else
1266 {
1267 static assert(T.sizeof == 8 && r.sizeof == 4);
8e96ae8 @MartinNowak fix shift overflow
MartinNowak authored
1268 T r1 = urng.front | (cast(T)r << 32);
017c1e8 @andralex bugzilla 3785 + improvements
andralex authored
1269 urng.popFront();
1270 return r1;
1271 }
1272 }
1273
1274 /// Ditto
1275 auto uniform(T)()
1276 if (isIntegral!T || isSomeChar!T)
1277 {
1278 return uniform!T(rndGen);
1279 }
1280
1281 unittest
1282 {
ab43002 @MartinNowak add unittests for std.random.uniform
MartinNowak authored
1283 foreach(T; TypeTuple!(char, wchar, dchar, byte, ubyte, short, ushort,
1284 int, uint, long, ulong))
1285 {
1286 T init = uniform!T();
1287 size_t i = 50;
1288 while (--i && uniform!T() == init) {}
1289 assert(i > 0);
1290 }
017c1e8 @andralex bugzilla 3785 + improvements
andralex authored
1291 }
1292
1293 /**
6663566 @andralex added uniformDistribution, fixed docs
andralex authored
1294 Generates a uniform probability distribution of size $(D n), i.e., an
1295 array of size $(D n) of positive numbers of type $(D F) that sum to
1296 $(D 1). If $(D useThis) is provided, it is used as storage.
1297 */
1298 F[] uniformDistribution(F = double)(size_t n, F[] useThis = null)
76def7a @jmdavis Fix Issue# 8026.
jmdavis authored
1299 if(isFloatingPoint!F)
6663566 @andralex added uniformDistribution, fixed docs
andralex authored
1300 {
1301 useThis.length = n;
1302 foreach (ref e; useThis)
1303 {
1304 e = uniform(0.0, 1);
1305 }
1306 normalize(useThis);
1307 return useThis;
1308 }
1309
1310 unittest
1311 {
1312 static assert(is(CommonType!(double, int) == double));
1313 auto a = uniformDistribution(5);
1314 enforce(a.length == 5);
1315 enforce(approxEqual(reduce!"a + b"(a), 1));
1316 a = uniformDistribution(10, a);
1317 enforce(a.length == 10);
1318 enforce(approxEqual(reduce!"a + b"(a), 1));
1319 }
1320
1321 /**
fba8c66 @Aatch Fixes typo in randomShuffle documentation
Aatch authored
1322 Shuffles elements of $(D r) using $(D gen) as a shuffler. $(D r) must be
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1323 a random-access range with length.
1324 */
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1325
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1326 void randomShuffle(Range, RandomGen = Random)(Range r,
76def7a @jmdavis Fix Issue# 8026.
jmdavis authored
1327 ref RandomGen gen = rndGen)
1328 if(isRandomAccessRange!Range && isUniformRNG!RandomGen)
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1329 {
f2c17d9 @dsimcha Add std.random.partialShuffle.
dsimcha authored
1330 return partialShuffle!(Range, RandomGen)(r, r.length, gen);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1331 }
1332
1333 unittest
1334 {
f2c17d9 @dsimcha Add std.random.partialShuffle.
dsimcha authored
1335 // Also tests partialShuffle indirectly.
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1336 auto a = ([ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]).dup;
1337 auto b = a.dup;
1338 Mt19937 gen;
1339 randomShuffle(a, gen);
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1340 assert(a.sort == b.sort);
1341 randomShuffle(a);
09916d3 @braddr Initial merge of candidate to trunk for r459:513
braddr authored
1342 assert(a.sort == b.sort);
1343 }
1344
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1345 /**
f2c17d9 @dsimcha Add std.random.partialShuffle.
dsimcha authored
1346 Partially shuffles the elements of $(D r) such that upon returning $(D r[0..n])
1347 is a random subset of $(D r) and is randomly ordered. $(D r[n..r.length])
1348 will contain the elements not in $(D r[0..n]). These will be in an undefined
1349 order, but will not be random in the sense that their order after
1350 $(D partialShuffle) returns will not be independent of their order before
1351 $(D partialShuffle) was called.
1352
1353 $(D r) must be a random-access range with length. $(D n) must be less than
1354 or equal to $(D r.length).
1355 */
1356 void partialShuffle(Range, RandomGen = Random)(Range r, size_t n,
1357 ref RandomGen gen = rndGen)
1358 if(isRandomAccessRange!Range && isUniformRNG!RandomGen)
1359 {
1360 enforce(n <= r.length, "n must be <= r.length for partialShuffle.");
1361 foreach (i; 0 .. n)
1362 {
1363 swapAt(r, i, i + uniform(0, r.length - i, gen));
1364 }
1365 }
1366
1367 /**
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
1368 Rolls a dice with relative probabilities stored in $(D
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1369 proportions). Returns the index in $(D proportions) that was chosen.
1370
1371 Example:
1372
1373 ----
1374 auto x = dice(0.5, 0.5); // x is 0 or 1 in equal proportions
1375 auto y = dice(50, 50); // y is 0 or 1 in equal proportions
41c4d79 @bluepeppers Fixed typo in documentation for dice function in std.random
bluepeppers authored
1376 auto z = dice(70, 20, 10); // z is 0 70% of the time, 1 20% of the time,
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1377 // and 2 10% of the time
1378 ----
1379 */
1083bd4 @andralex One pass through std.range and friends
andralex authored
1380 size_t dice(Rng, Num)(ref Rng rnd, Num[] proportions...)
1381 if (isNumeric!Num && isForwardRange!Rng)
1382 {
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1383 return diceImpl(rnd, proportions);
1384 }
1385
1386 /// Ditto
1387 size_t dice(R, Range)(ref R rnd, Range proportions)
1083bd4 @andralex One pass through std.range and friends
andralex authored
1388 if (isForwardRange!Range && isNumeric!(ElementType!Range) && !isArray!Range)
1389 {
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1390 return diceImpl(rnd, proportions);
1391 }
1392
1393 /// Ditto
1083bd4 @andralex One pass through std.range and friends
andralex authored
1394 size_t dice(Range)(Range proportions)
1395 if (isForwardRange!Range && isNumeric!(ElementType!Range) && !isArray!Range)
1396 {
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
1397 return diceImpl(rndGen, proportions);
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1398 }
1399
1400 /// Ditto
1083bd4 @andralex One pass through std.range and friends
andralex authored
1401 size_t dice(Num)(Num[] proportions...)
1402 if (isNumeric!Num)
1403 {
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
1404 return diceImpl(rndGen, proportions);
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1405 }
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1406
1083bd4 @andralex One pass through std.range and friends
andralex authored
1407 private size_t diceImpl(Rng, Range)(ref Rng rng, Range proportions)
1408 if (isForwardRange!Range && isNumeric!(ElementType!Range) && isForwardRange!Rng)
1409 {
1410 double sum = reduce!("(assert(b >= 0), a + b)")(0.0, proportions.save);
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1411 enforce(sum > 0, "Proportions in a dice cannot sum to zero");
1083bd4 @andralex One pass through std.range and friends
andralex authored
1412 immutable point = uniform(0.0, sum, rng);
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1413 assert(point < sum);
1414 auto mass = 0.0;
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1415
1416 size_t i = 0;
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
1417 foreach (e; proportions)
1418 {
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1419 mass += e;
1420 if (point < mass) return i;
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1421 i++;
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1422 }
1423 // this point should not be reached
1424 assert(false);
1425 }
1426
1b14818 @jmdavis Fixed incorrect braces in std.random.
jmdavis authored
1427 unittest
1428 {
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1429 auto rnd = Random(unpredictableSeed);
0082bfa @donc Fix to allow random to compile with -cov.
donc authored
1430 auto i = dice(rnd, 0.0, 100.0);
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1431 assert(i == 1);
0082bfa @donc Fix to allow random to compile with -cov.
donc authored
1432 i = dice(rnd, 100.0, 0.0);
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1433 assert(i == 0);
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1434
1083bd4 @andralex One pass through std.range and friends
andralex authored
1435 i = dice(100U, 0U);
75de983 @dsimcha Bug 2951: std.random.dice() should be templated on proportions.
dsimcha authored
1436 assert(i == 0);
1ae5300 @andralex * std.algorithm: Changed the map() function so that it deduces the re…
andralex authored
1437 }
1438
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1439 /**
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
1440 Covers a given range $(D r) in a random manner, i.e. goes through each
1441 element of $(D r) once and only once, just in a random order. $(D r)
79af282 @andralex doc fix
andralex authored
1442 must be a random-access range with length.
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1443
1444 Example:
1445 ----
1446 int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ];
1447 auto rnd = Random(unpredictableSeed);
1448 foreach (e; randomCover(a, rnd))
1449 {
1450 writeln(e);
1451 }
1452 ----
1453 */
76def7a @jmdavis Fix Issue# 8026.
jmdavis authored
1454 struct RandomCover(Range, Random)
1455 if(isRandomAccessRange!Range && isUniformRNG!Random)
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1456 {
1457 private Range _input;
1458 private Random _rnd;
1459 private bool[] _chosen;
1460 private uint _current;
1461 private uint _alreadyChosen;
1462
1463 this(Range input, Random rnd)
1464 {
1465 _input = input;
1466 _rnd = rnd;
1467 _chosen.length = _input.length;
e312f98 @klickverbot Strict @property syntax compliance.
klickverbot authored
1468 popFront();
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1469 }
1470
f19d95a @andralex added randomSample.
andralex authored
1471 static if (hasLength!Range)
a288172 @repeatedly Add @property to length method.
repeatedly authored
1472 @property size_t length()
f19d95a @andralex added randomSample.
andralex authored
1473 {
1474 return (1 + _input.length) - _alreadyChosen;
1475 }
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
1476
ebed756 @dsimcha Range cleanup for std.random.
dsimcha authored
1477 @property auto ref front()
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1478 {
1479 return _input[_current];
1480 }
1481
dfef2a7 @andralex Replaced next, retreat, head, and toe with (respectively) popFront, p…
andralex authored
1482 void popFront()
0cb5ab4 @andralex * Added RandomCover that covers a given range in a random manner
andralex authored
1483 {
1484 if (_alreadyChosen >= _input.length)
1485