COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/random.h @ 2230:67af33b34394

Last change on this file since 2230:67af33b34394 was 2230:67af33b34394, checked in by Balazs Dezso, 18 years ago

Some doc fix

File size: 14.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_RANDOM_H
20#define LEMON_RANDOM_H
21
22#include <algorithm>
23
24#include <ctime>
25#include <cmath>
26#include <cmath>
27
28///\ingroup misc
29///\file
30///\brief Mersenne Twister random number generator
31///
32///\author Balazs Dezso
33
34namespace lemon {
35
36#if WORD_BIT == 32
37
38  /// \ingroup misc
39  ///
40  /// \brief Mersenne Twister random number generator
41  ///
42  /// The Mersenne Twister is a twisted generalized feedback
43  /// shift-register generator of Matsumoto and Nishimura. The period of
44  /// this generator is \f$ 2^{19937} - 1 \f$ and it is equi-distributed in
45  /// 623 dimensions. The time performance of this generator is comparable
46  /// to the commonly used generators.
47  ///
48  /// \author Balazs Dezso
49  class Random {
50
51    static const int length = 624;
52    static const int shift = 397;
53
54  public:
55
56    static const unsigned long min = 0ul;
57    static const unsigned long max = ~0ul;
58 
59    /// \brief Constructor
60    ///
61    /// Constructor with time dependent seeding.
62    Random() { initState(std::time(0)); }
63
64    /// \brief Constructor
65    ///
66    /// Constructor
67    Random(unsigned long seed) { initState(seed); }
68
69    /// \brief Copy constructor
70    ///
71    /// Copy constructor. The generated sequence will be identical to
72    /// the other sequence.
73    Random(const Random& other) {
74      std::copy(other.state, other.state + length, state);
75      current = state + (other.current - other.state);
76    }
77
78    /// \brief Assign operator
79    ///
80    /// Assign operator. The generated sequence will be identical to
81    /// the other sequence.
82    Random& operator=(const Random& other) {
83      if (&other != this) {
84        std::copy(other.state, other.state + length, state);
85        current = state + (other.current - other.state);
86      }
87      return *this;
88    }
89
90    /// \brief Returns an unsigned random number
91    ///
92    /// It returns an unsigned integer random number from the range
93    /// \f$ \{0, 1, \dots, 2^{32} - 1\} \f$.
94    unsigned long getUnsigned() {
95      if (current == state) fillState();
96      --current;
97      unsigned long rnd = *current;
98      rnd ^= (rnd >> 11);
99      rnd ^= (rnd << 7) & 0x9D2C5680ul;
100      rnd ^= (rnd << 15) & 0xEFC60000ul;
101      rnd ^= (rnd >> 18);
102      return rnd;
103    }
104
105    /// \brief Returns a random number
106    ///
107    /// It returns an integer random number from the range
108    /// \f$ \{-2^{31}, \dots, 2^{31} - 1\} \f$.
109    long getInt() {
110      return (long)getUnsigned();
111    }
112   
113    /// \brief Returns an unsigned integer random number
114    ///
115    /// It returns an unsigned integer random number from the range
116    /// \f$ \{0, 1, \dots, 2^{31} - 1\} \f$.
117    long getNatural() {
118      return (long)(getUnsigned() >> 1);
119    }
120
121    /// \brief Returns a random bool
122    ///
123    /// It returns a random bool.
124    bool getBool() {
125      return (bool)(getUnsigned() & 1);
126    }
127
128    /// \brief Returns a real random number
129    ///
130    /// It returns a real random number from the range
131    /// \f$ [0, 1) \f$. The double will have 32 significant bits.
132    double getReal() {
133      return std::ldexp((double)getUnsigned(), -32);
134    }
135
136    /// \brief Returns a real random number
137    ///
138    /// It returns a real random number from the range
139    /// \f$ [0, 1) \f$. The double will have 53 significant bits,
140    /// but it is slower than the \c getReal().
141    double getPrecReal() {
142      return std::ldexp((double)(getUnsigned() >> 5), -27) +
143        std::ldexp((double)(getUnsigned() >> 6), -53);
144    }
145
146    /// \brief Returns an unsigned random number from a given range
147    ///
148    /// It returns an unsigned integer random number from the range
149    /// \f$ \{0, 1, \dots, n - 1\} \f$.
150    unsigned long getUnsigned(unsigned long n) {
151      unsigned long mask = n - 1, rnd;
152      mask |= mask >> 1;
153      mask |= mask >> 2;
154      mask |= mask >> 4;
155      mask |= mask >> 8;
156      mask |= mask >> 16;
157      do rnd = getUnsigned() & mask; while (rnd >= n);
158      return rnd;
159    }
160
161    /// \brief Returns a random number from a given range
162    ///
163    /// It returns an unsigned integer random number from the range
164    /// \f$ \{0, 1, \dots, n - 1\} \f$.
165    long getInt(long n) {
166      long mask = n - 1, rnd;
167      mask |= mask >> 1;
168      mask |= mask >> 2;
169      mask |= mask >> 4;
170      mask |= mask >> 8;
171      mask |= mask >> 16;
172      do rnd = getUnsigned() & mask; while (rnd >= n);
173      return rnd;
174    }
175
176  private:
177
178    void initState(unsigned long seed) {
179      static const unsigned long mul = 0x6c078965ul;
180
181      current = state;
182
183      unsigned long *curr = state + length - 1;
184      curr[0] = seed; --curr;
185      for (int i = 1; i < length; ++i) {
186        curr[0] = (mul * ( curr[1] ^ (curr[1] >> 30) ) + i);
187        --curr;
188      }
189    }
190 
191    void fillState() {
192      static const unsigned long mask[2] = { 0x0ul, 0x9908B0DFul };
193      static const unsigned long loMask = (1ul << 31) - 1;
194      static const unsigned long hiMask = ~loMask;
195
196      current = state + length;
197
198      register unsigned long *curr = state + length - 1;
199      register long num;
200     
201      num = length - shift;
202      while (num--) {
203        curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
204          curr[- shift] ^ mask[curr[-1] & 1ul];
205        --curr;
206      }
207      num = shift - 1;
208      while (num--) {
209        curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
210          curr[length - shift] ^ mask[curr[-1] & 1ul];
211        --curr;
212      }
213      curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
214        curr[length - shift] ^ mask[curr[length - 1] & 1ul];
215
216    }
217 
218    unsigned long *current;
219    unsigned long state[length];
220   
221  };
222
223#elif WORD_BIT == 64
224
225  /// \ingroup misc
226  ///
227  /// \brief Mersenne Twister random number generator
228  ///
229  /// The Mersenne Twister is a twisted generalized feedback
230  /// shift-register generator of Matsumoto and Nishimura. The period of
231  /// this generator is \f$ 2^{19937} - 1 \f$ and it is equi-distributed in
232  /// 311 dimensions. The time performance of this generator is comparable
233  /// to the commonly used generators.
234  class Random {
235
236    static const int length = 312;
237    static const int shift = 156;
238
239  public:
240
241    static const unsigned long min = 0ul;
242    static const unsigned long max = ~0ul;
243 
244    /// \brief Constructor
245    ///
246    /// Constructor with time dependent seeding.
247    Random() { initState(std::time(0)); }
248
249    /// \brief Constructor
250    ///
251    /// Constructor
252    Random(unsigned long seed) { initState(seed); }
253
254    /// \brief Copy constructor
255    ///
256    /// Copy constructor. The generated sequence will be identical to
257    /// the other sequence.
258    Random(const Random& other) {
259      std::copy(other.state, other.state + length, state);
260      current = state + (other.current - other.state);
261    }
262
263    /// \brief Assign operator
264    ///
265    /// Assign operator. The generated sequence will be identical to
266    /// the other sequence.
267    Random& operator=(const Random& other) {
268      if (&other != this) {
269        std::copy(other.state, other.state + length, state);
270        current = state + (other.current - other.state);
271      }
272      return *this;
273    }
274
275    /// \brief Returns an unsigned random number
276    ///
277    /// It returns an unsigned integer random number from the range
278    /// \f$ \{0, 1, \dots, 2^{64} - 1\} \f$.
279    unsigned long getUnsigned() {
280      if (current == state) fillState();
281      --current;
282      unsigned long rnd = *current;
283      rnd ^= (rnd >> 29) & 0x5555555555555555ul;
284      rnd ^= (rnd << 17) & 0x71D67FFFEDA60000ul;
285      rnd ^= (rnd << 37) & 0xFFF7EEE000000000ul;
286      rnd ^= (rnd >> 43);
287      return rnd;
288    }
289
290    /// \brief Returns a random number
291    ///
292    /// It returns an integer random number from the range
293    /// \f$ \{-2^{63}, \dots, 2^{63} - 1\} \f$.
294    long getInt() {
295      return (long)getUnsigned();
296    }
297   
298    /// \brief Returns an unsigned integer random number
299    ///
300    /// It returns an unsigned integer random number from the range
301    /// \f$ \{0, 1, \dots, 2^{63} - 1\} \f$.
302    long getNatural() {
303      return (long)(getUnsigned() >> 1);
304    }
305
306    /// \brief Returns a random bool
307    ///
308    /// It returns a random bool.
309    bool getBool() {
310      return (bool)(getUnsigned() & 1);
311    }
312
313    /// \brief Returns a real random number
314    ///
315    /// It returns a real random number from the range
316    /// \f$ [0, 1) \f$.
317    double getReal() {
318      return std::ldexp((double)(getUnsigned() >> 11), -53);
319    }
320
321    /// \brief Returns a real random number
322    ///
323    /// It returns a real random number from the range
324    /// \f$ [0, 1) \f$. This function is identical to the \c getReal().
325    double getPrecReal() {
326      return getReal();
327    }
328
329    /// \brief Returns an unsigned random number from a given range
330    ///
331    /// It returns an unsigned integer random number from the range
332    /// \f$ \{0, 1, \dots, n - 1\} \f$.
333    unsigned long getUnsigned(unsigned long n) {
334      unsigned long mask = n - 1, rnd;
335      mask |= mask >> 1;
336      mask |= mask >> 2;
337      mask |= mask >> 4;
338      mask |= mask >> 8;
339      mask |= mask >> 16;
340      mask |= mask >> 32;
341      do rnd = getUnsigned() & mask; while (rnd >= n);
342      return rnd;
343    }
344
345    /// \brief Returns a random number from a given range
346    ///
347    /// It returns an unsigned integer random number from the range
348    /// \f$ \{0, 1, \dots, n - 1\} \f$.
349    long getInt(long n) {
350      long mask = n - 1, rnd;
351      mask |= mask >> 1;
352      mask |= mask >> 2;
353      mask |= mask >> 4;
354      mask |= mask >> 8;
355      mask |= mask >> 16;
356      mask |= mask >> 32;
357      do rnd = getUnsigned() & mask; while (rnd >= n);
358      return rnd;
359    }
360
361  private:
362
363    void initState(unsigned long seed) {
364
365      static const unsigned long mul = 0x5851F42D4C957F2Dul;
366
367      current = state;
368
369      unsigned long *curr = state + length - 1;
370      curr[0] = seed; --curr;
371      for (int i = 1; i < length; ++i) {
372        curr[0] = (mul * ( curr[1] ^ (curr[1] >> 62) ) + i);
373        --curr;
374      }
375    }
376 
377    void fillState() {
378      static const unsigned long mask[2] = { 0x0ul, 0xB5026F5AA96619E9ul };
379      static const unsigned long loMask = (1ul << 31) - 1;
380      static const unsigned long hiMask = ~loMask;
381
382      current = state + length;
383
384      register unsigned long *curr = state + length - 1;
385      register int num;
386     
387      num = length - shift;
388      while (num--) {
389        curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
390          curr[- shift] ^ mask[curr[-1] & 1ul];
391        --curr;
392      }
393      num = shift - 1;
394      while (num--) {
395        curr[0] = (((curr[0] & hiMask) | (curr[-1] & loMask)) >> 1) ^
396          curr[length - shift] ^ mask[curr[-1] & 1ul];
397        --curr;
398      }
399      curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
400        curr[length - shift] ^ mask[curr[length - 1] & 1ul];
401
402    }
403 
404    unsigned long *current;
405    unsigned long state[length];
406   
407  };
408
409#else
410
411  /// \ingroup misc
412  ///
413  /// \brief Mersenne Twister random number generator
414  ///
415  /// The Mersenne Twister is a twisted generalized feedback
416  /// shift-register generator of Matsumoto and Nishimura. There is
417  /// two different implementation in the Lemon library, one for
418  /// 32-bit processors and one for 64-bit processors. The period of
419  /// the generated sequence is \f$ 2^{19937} - 1 \f$, the generated
420  /// sequence of 32-bit random numbers is equi-distributed in 623
421  /// dimensions. The time performance of this generator is comparable
422  /// to the commonly used generators.
423  class Random {
424  public:
425
426    static const unsigned long min = 0ul;
427    static const unsigned long max = ~0ul;
428 
429    /// \brief Constructor
430    ///
431    /// Constructor with time dependent seeding.
432    Random() {}
433
434    /// \brief Constructor
435    ///
436    /// Constructor
437    Random(unsigned long seed) {}
438
439    /// \brief Copy constructor
440    ///
441    /// Copy constructor. The generated sequence will be identical to
442    /// the other sequence.
443    Random(const Random& other) {}
444
445    /// \brief Assign operator
446    ///
447    /// Assign operator. The generated sequence will be identical to
448    /// the other sequence.
449    Random& operator=(const Random& other) { return *this; }
450
451    /// \brief Returns an unsigned random number
452    ///
453    /// It returns an unsigned integer random number from the range
454    /// \f$ \{0, 1, \dots, 2^{64} - 1\} \f$ for 64-bit processors and from
455    /// \f$ \{0, 1, \dots, 2^{32} - 1\} \f$ for 32-bit processors.
456    unsigned long getUnsigned() { return 0ul; }
457
458    /// \brief Returns a random number
459    ///
460    /// It returns an integer random number from the range
461    /// \f$ \{-2^{63}, \dots, 2^{63} - 1\} \f$ for 64-bit processors and from
462    /// \f$ \{-2^{31}, \dots, 2^{31} - 1\} \f$ for 32-bit processors.
463    long getInt() { return 0l; }
464   
465    /// \brief Returns an unsigned integer random number
466    ///
467    /// It returns an unsigned integer random number from the range
468    /// \f$ \{0, 1, \dots, 2^{63} - 1\} \f$ for 64-bit processors and
469    /// from \f$ \{0, 1, \dots, 2^{31} - 1\} \f$ for 32-bit processors.
470    long getNatural() { return 0l; }
471
472    /// \brief Returns a random bool
473    ///
474    /// It returns a random bool.
475    bool getBool() { return false; }
476
477    /// \brief Returns a real random number
478    ///
479    /// It returns a real random number from the range
480    /// \f$ [0, 1) \f$. For 32-bit processors the generated random
481    /// number will just have 32 significant bits.
482    double getReal() { return 0.0; }
483
484    /// \brief Returns a real random number
485    ///
486    /// It returns a real random number from the range
487    /// \f$ [0, 1) \f$. This function returns random numbers with 53
488    /// significant bits for 32-bit processors. For 64-bit processors
489    /// it is identical to the \c getReal().
490    double getPrecReal() { return 0.0; }
491
492    /// \brief Returns an unsigned random number from a given range
493    ///
494    /// It returns an unsigned integer random number from the range
495    /// \f$ \{0, 1, \dots, n - 1\} \f$.
496    unsigned long getUnsigned(unsigned long n) { return 0; }
497
498    /// \brief Returns a random number from a given range
499    ///
500    /// It returns an unsigned integer random number from the range
501    /// \f$ \{0, 1, \dots, n - 1\} \f$.
502    long getInt(long n) { return 0; }
503
504  };
505
506#endif
507
508  /// \brief Global random number generator instance
509  ///
510  /// A global mersenne twister random number generator instance
511  extern Random rnd;
512
513}
514
515#endif
Note: See TracBrowser for help on using the repository browser.