1 /* Copyright Jukka Jyl�nki
2
3    Licensed under the Apache License, Version 2.0 (the "License");
4    you may not use this file except in compliance with the License.
5    You may obtain a copy of the License at
6
7        http://www.apache.org/licenses/LICENSE-2.0
8
9    Unless required by applicable law or agreed to in writing, software
10    distributed under the License is distributed on an "AS IS" BASIS,
11    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12    See the License for the specific language governing permissions and
13    limitations under the License. */
14
15 /** @file LCG.h
16         @author Jukka Jyl�nki
17         @brief A linear congruential random number generator. */
18 #pragma once
19
20 #include "../../MathBuildConfig.h"
21 #include "../../Math/MathNamespace.h"
22
23 #include "../../Math/MathTypes.h"
24
25 /** @brief A linear congruential random number generator.
26
27         Uses D.H. Lehmer's Linear Congruential Method (1949) for generating random numbers.
28         Supports both Multiplicative Congruential Method (increment==0) and
29         Mixed Congruential Method (increment!=0)
30         It is perhaps the simplest and fastest method to generate pseudo-random numbers on
31         a computer. Per default uses the values for Minimal Standard LCG.
32         http://en.wikipedia.org/wiki/Linear_congruential_generator
33         http://www.math.rutgers.edu/~greenfie/currentcourses/sem090/pdfstuff/jp.pdf
34
35         Pros:
36         <ul>
37             <li> Easy to implement.
38             <li> Fast.
39         </ul>
40
41         Cons:
42         <ul>
43             <li> NOT safe for cryptography because of the easily calculatable sequential
44                 correlation between successive calls. A case study:
45                 http://www.cigital.com/papers/download/developer_gambling.php
46
47             <li> Tends to have less random low-order bits (compared to the high-order bits)
48                  Thus, NEVER do something like this:
49
50                    u32 numBetween1And10 = 1 + LCGRand.Int() % 10;
51
52                  Instead, take into account EVERY bit of the generated number, like this:
53
54                    u32 numBetween1And10 = 1 + (int)(10.0 * (double)LCGRand.Int()
55                                                               /(LCGRand.Max()+1.0));
56                  or simply
57         
58                    u32 numBetween1And10 = LCGRand.Float(1.f, 10.f);
59         </ul> */
60
61 MATH_BEGIN_NAMESPACE
62
63 class LCG
64 {
65 public:
66         /// Initializes the generator from the current system clock.
67         LCG();
68         /// Initializes the generator using a custom seed.
69         LCG(u32 seed, u32 multiplier = 69621,
70                 u32 increment = 0, u32 modulus = 0x7FFFFFFF /* 2^31 - 1 */)
71         {
72                 Seed(seed, multiplier, increment, modulus);
73         }
74
75         /// Reinitializes the generator to the new settings.
76         void Seed(u32 seed, u32 multiplier = 69621, u32 increment = 0, u32 modulus = 0x7FFFFFFF);
77
78         /// Returns a random integer picked uniformly in the range [0, MaxInt()]
79         u32 Int();
80
81         /// Returns the biggest number the generator can yield. (Which is always modulus-1)
82         u32 MaxInt() const { return modulus - 1; }
83
84         /// Returns a random integer picked uniformly in the range [0, 2^32-1].
85         /// @note The configurable modulus and increment are not used by this function, but are always increment == 0, modulus=2^32.
86         u32 IntFast();
87
88         /// Returns a random integer picked uniformly in the range [a, b]
89         /** @param a Lower bound, inclusive.
90             @param b Upper bound, inclusive.
91             @return A random integer picked uniformly in the range [a, b] */
92         int Int(int a, int b);
93
94         /// Returns a random float picked uniformly in the range [0, 1[.
95         float Float();
96
97         /// Returns a random float picked uniformly in the range [0, 1].
98         /// @note This is much slower than Float()! Prefer that function instead if possible.
99         float Float01Incl();
100
101         /// Returns a random float picked uniformly in the range ]-1, 1[.
102         /// @note This function has one more bit of randomness compared to Float(), but has a theoretical bias
103         /// towards 0.0, since floating point has two representations for 0 (+0 and -0).
104         float FloatNeg1_1();
105
106         /// Returns a random float picked uniformly in the range [a, b[.
107         /** @param a Lower bound, inclusive.
108             @param b Upper bound, exclusive.
109             @return A random float picked uniformly in the range [a, b[
110             @Note This function is slower than LCG::FloatIncl(). If you do not care about the open/closed interval, prefer calling FloatIncl() instead.
111             @see Float(), FloatIncl(). */
112         float Float(float a, float b);
113
114         /// Returns a random float picked uniformly in the range [a, b].
115         /** @param a Lower bound, inclusive.
116             @param b Upper bound, inclusive.
117             @return A random float picked uniformly in the range [a, b] */
118         float FloatIncl(float a, float b);
119
120         u32 multiplier;
121         u32 increment;
122         u32 modulus;
123
124         u32 lastNumber;
125 };
126
127 #ifdef MATH_QT_INTEROP
128 Q_DECLARE_METATYPE(LCG)
129 Q_DECLARE_METATYPE(LCG*)
130 #endif
131
132 MATH_END_NAMESPACE