source: Project Repository/src/random.h @ 2

Revision 2, 6.8 KB checked in by pchapin, 8 years ago (diff)

Reformatted the comments in the existing source files.

Line 
1/****************************************************************************
2FILE      : random.h
3SUBJECT   : Interface to random number abstract class.
4PROGRAMMER: (C) Copyright 2012 by Peter C. Chapin
5
6This file contains the interface to a random number generating class. For brevity it also
7contains the definitions of two implementation classes (it would be more typical for each
8implementation class to have a header of its own).
9
10****************************************************************************/
11
12#ifndef RANDOM_H
13#define RANDOM_H
14
15#include <cstdlib>
16
17//! Namespace that contains the contents of the Random Library.
18namespace rnd {
19
20  //! Abstract base class for random number generators.
21  /*!
22   * This class is intended to provide an abstract interface to all random number generator
23   * objects that return natural numbers in the range 0 to some maximum value.
24   *
25   * \todo It might make sense to use a type such as uint32_t for the random numbers rather than
26   * unsigned int as is currently the case. This would promote portability to 16 bit (or
27   * smaller) platforms.
28   */
29  class random {
30  public:
31
32    virtual ~random() { }
33
34    //! Extract the next random number from the object.
35    virtual unsigned next() = 0;
36
37    //! Returns the maximum possible value returned by next().
38    virtual unsigned max() = 0;
39
40    //! Returns a random number in the range [L .. H] from the object.
41    /*!
42     * This method uses the underlying generator to compute a random natural number in the given
43     * range. Each call on this method invokes exactly one call to the underlying next() method.
44     * This method for convenience.
45     *
46     * \param L The lower limit of the output range.
47     * \param H The upper limit of the output range.
48     * \return A number in the specified range. H and L are included in the range.
49     */
50    unsigned next(unsigned L, unsigned H)
51      { return (next() % (H - L + 1)) + L; }
52  };
53
54
55  //! Random bit generator wrapper class (scanner).
56  /*!
57   * This class is a wrapper around class random that returns individual bits. It works by
58   * scanning down the numbers returned by the underlying generator and returning the bits it
59   * finds there, one at a time.
60   *
61   * \warning If the underlying generator has a maximum value that is not a power of two, the
62   * output of this generator will have bias. This is because the most significant bit of the
63   * output of the underlying generator will not be occuring with frequency 0.5.
64   */
65  class bit_random : public random {
66  private:
67    random &generator;
68    unsigned current;
69    unsigned mask;
70
71  public:
72    /*!
73     * \param g A reference to a random number generator that is used as the source of random
74     * natural numbers.
75     */
76    bit_random(random &g) : generator(g) { mask = 0; }
77   ~bit_random() { }
78
79    virtual unsigned next();
80    virtual unsigned max()
81      { return 1; }
82  };
83
84  //! Random bit generator wrapper class (LSB).
85  /*!
86   * This class is a wrapper around class random that returns individual bits. It works by
87   * returning the least significant bit of each number returned by the underlying generator.
88   *
89   * \warning Many PRNGs are not good at randomizing the least significant bits of each output
90   * number.
91   */
92  class lsbbit_random : public random {
93  private:
94    random &generator;
95
96  public:
97    /*!
98     * \param g A reference to a random number generator that is used as the source of random
99     * natural numbers.
100     */
101    lsbbit_random(random &g) : generator(g) { }
102   ~lsbbit_random() { }
103
104    virtual unsigned next()
105      { return generator.next() & 0x1; }
106
107    virtual unsigned max()
108      { return 1; }
109  };
110
111
112  //! Abstract base class for seeded random number generators.
113  class seeded_random : public random {
114  public:
115
116    //! Provide a seed value to the random number generator.
117    /*!
118     * Random number generators that require a seed value include all PRNGs. The seed is used as
119     * the starting point of the pseudo random sequence. A particular sequence can be repeated
120     * by providing the same seed.
121     *
122     * \param s The seed value. This value is usually required to be in the same range as the
123     * generator's output, but that does not need to be the case in general.
124     *
125     * \warning If an attacker can guess the seed value used, the attacker can compute the
126     * pseudo random sequence generated. Thus in security sensitive applications, seed values
127     * must be choosen in an unguessable way.
128     */
129    virtual void seed(unsigned s) = 0;
130
131    //! Uses the current time of day to generate a seed.
132    /*!
133     * \warning Be careful creating too many objects that are seeded this way. If you seed them
134     * all quickly enough they may get the same seed. Even if you seed them slowly, there may be
135     * resonances between your program and the system clock.
136     *
137     * \warning The current time is too guessable for use in security sensitive applications.
138     */
139    void time_seed();
140  };
141
142
143  //! Wrapper around the standard C library's PRNG.
144  /*!
145   * \warning Because the standard random number generator keeps its seed in a static object in
146   * the library, all objects of type standard_random are interrelated. Be careful using this
147   * class!
148   */
149  class standard_random : public seeded_random {
150  public:
151    virtual ~standard_random() { }
152
153    virtual unsigned next()
154      { return static_cast<unsigned>(std::rand()); }
155
156    virtual unsigned max()
157      { return static_cast<unsigned>(RAND_MAX); }
158
159    virtual void seed(unsigned s)
160      { std::srand(s); }
161  };
162
163
164  //! Linear congruential PRNG.
165  /*!
166   * This generator has a period of 1771875 states. All objects from this class are independent
167   * and have different internal states.
168   *
169   * \warning Like all linear congruential generators, this generator is not suitable for use in
170   * security sensitive applications.
171   *
172   * \todo Generalize this class so that the user can provide the constants used in the linear
173   * congruential computations. It might also be nice to provide several "defaults" (selectable
174   * with a method call perhaps) so that users can use the generator without much fuss.
175   */
176  class linear_congruential : public seeded_random {
177  private:
178    unsigned long X;    // The "current value" of the generator.
179
180  public:
181    virtual ~linear_congruential() { }
182
183    // The constants below ensure maximum period and their values take advantage of the range
184    // on a 32 bit unsigned quantity.
185    //
186    virtual unsigned next()
187      { return X = ((2416UL * X) + 374441UL) % 1771875UL; }
188
189    virtual unsigned max()
190      { return 1771874; }
191 
192    virtual void seed(unsigned s)
193      { X = s; }
194  };
195
196}
197
198#endif
Note: See TracBrowser for help on using the repository browser.