00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 namespace Gecode { namespace Support {
00037
00045 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00046 class LinearCongruentialGenerator {
00047 private:
00049 static const unsigned int max = 1UL<<31;
00051 unsigned int s;
00053 unsigned int next(void);
00054 public:
00056 void seed(unsigned int s);
00058 LinearCongruentialGenerator(unsigned int s = 1);
00060 unsigned int seed(void) const;
00062 unsigned int operator ()(unsigned int n);
00064 size_t size(void) const;
00065 };
00066
00067 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00068 forceinline unsigned int
00069 LinearCongruentialGenerator<m,a,q,r>::next(void) {
00070 s = a*(s%q) - r*(s/q);
00071 unsigned int res = s;
00072 if (s==0) s = 1;
00073 return res;
00074 }
00075 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00076 forceinline void
00077 LinearCongruentialGenerator<m,a,q,r>::seed(unsigned int _s) {
00078 s = _s % m;
00079 if (s == 0) s = 1;
00080 }
00081 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00082 forceinline
00083 LinearCongruentialGenerator<m,a,q,r>::
00084 LinearCongruentialGenerator(unsigned int _s) {
00085 seed(_s);
00086 }
00087 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00088 forceinline unsigned int
00089 LinearCongruentialGenerator<m,a,q,r>::seed(void) const {
00090 return s;
00091 }
00092 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00093 forceinline unsigned int
00094 LinearCongruentialGenerator<m,a,q,r>::operator ()(unsigned int n) {
00095 unsigned int x1 = next() & ((1<<16)-1);
00096 unsigned int x2 = next() & ((1<<16)-1);
00097 if (n < 2) return 0;
00098 double d = static_cast<double>(((x1<<16) | x2) % max) / max;
00099 unsigned int val = static_cast<unsigned int>(n * d);
00100 return (val < n) ? val : (n-1);
00101 }
00102 template<unsigned int m, unsigned int a, unsigned int q, unsigned int r>
00103 forceinline size_t
00104 LinearCongruentialGenerator<m,a,q,r>::size(void) const {
00105 return sizeof(LinearCongruentialGenerator<m,a,q,r>);
00106 }
00107
00108
00119 typedef LinearCongruentialGenerator<2147483647, 48271, 44488, 3399>
00120 RandomGenerator;
00121
00122 }}
00123
00124