 |
Changeset 3963
- Timestamp:
- 10/04/08 15:09:31
(2 months ago)
- Author:
- kris
- Message:
removed tabs
-
Files:
-
Legend:
- Unmodified
- Added
- Removed
- Modified
- Copied
- Moved
| r3962 |
r3963 |
|
| 17 | 17 | /******************************************************************************* |
|---|
| 18 | 18 | |
|---|
| 19 | | Wrapper for the Mersenne twister. |
|---|
| 20 | | |
|---|
| 21 | | The Mersenne twister is a pseudorandom number generator linked to |
|---|
| | 19 | Wrapper for the Mersenne twister. |
|---|
| | 20 | |
|---|
| | 21 | The Mersenne twister is a pseudorandom number generator linked to |
|---|
| 22 | 22 | CR developed in 1997 by Makoto Matsumoto and Takuji Nishimura that |
|---|
| 23 | 23 | is based on a matrix linear recurrence over a finite binary field |
|---|
| 24 | 24 | F2. It provides for fast generation of very high quality pseudorandom |
|---|
| 25 | 25 | numbers, having been designed specifically to rectify many of the |
|---|
| 26 | | flaws found in older algorithms. |
|---|
| 27 | | |
|---|
| 28 | | Mersenne Twister has the following desirable properties: |
|---|
| | 26 | flaws found in older algorithms. |
|---|
| | 27 | |
|---|
| | 28 | Mersenne Twister has the following desirable properties: |
|---|
| 29 | 29 | --- |
|---|
| 30 | 30 | 1. It was designed to have a period of 2^19937 - 1 (the creators |
|---|
| … | … | |
| 32 | 32 | |
|---|
| 33 | 33 | 2. It has a very high order of dimensional equidistribution. |
|---|
| 34 | | This implies that there is negligible serial correlation between |
|---|
| | 34 | This implies that there is negligible serial correlation between |
|---|
| 35 | 35 | successive values in the output sequence. |
|---|
| 36 | 36 | |
|---|
| 37 | | 3. It passes numerous tests for statistical randomness, including |
|---|
| | 37 | 3. It passes numerous tests for statistical randomness, including |
|---|
| 38 | 38 | the stringent Diehard tests. |
|---|
| 39 | 39 | |
|---|
| 40 | | 4. It is fast. |
|---|
| | 40 | 4. It is fast. |
|---|
| 41 | 41 | --- |
|---|
| 42 | 42 | |
|---|
| … | … | |
| 49 | 49 | N = 624, |
|---|
| 50 | 50 | M = 397, |
|---|
| 51 | | MATRIX_A = 0x9908b0df, // constant vector a |
|---|
| 52 | | UPPER_MASK = 0x80000000, // most significant w-r bits |
|---|
| 53 | | LOWER_MASK = 0x7fffffff, // least significant r bits |
|---|
| | 51 | MATRIX_A = 0x9908b0df, // constant vector a |
|---|
| | 52 | UPPER_MASK = 0x80000000, // most significant w-r bits |
|---|
| | 53 | LOWER_MASK = 0x7fffffff, // least significant r bits |
|---|
| 54 | 54 | } |
|---|
| 55 | 55 | |
|---|
| 56 | 56 | private uint[N] mt; // the array for the state vector |
|---|
| 57 | | private uint mti=mt.length+1; // mti==mt.length+1 means mt[] is not initialized |
|---|
| 58 | | private uint vLastRand; // The most recent random uint returned. |
|---|
| | 57 | private uint mti=mt.length+1; // mti==mt.length+1 means mt[] is not initialized |
|---|
| | 58 | private uint vLastRand; // The most recent random uint returned. |
|---|
| 59 | 59 | |
|---|
| 60 | 60 | /********************************************************************** |
|---|
| … | … | |
| 89 | 89 | **********************************************************************/ |
|---|
| 90 | 90 | |
|---|
| 91 | | uint toInt (uint max) |
|---|
| 92 | | { |
|---|
| 93 | | return toInt % max; |
|---|
| 94 | | } |
|---|
| 95 | | |
|---|
| | 91 | uint toInt (uint max) |
|---|
| | 92 | { |
|---|
| | 93 | return toInt % max; |
|---|
| | 94 | } |
|---|
| | 95 | |
|---|
| 96 | 96 | /********************************************************************** |
|---|
| 97 | 97 | |
|---|
| … | … | |
| 100 | 100 | **********************************************************************/ |
|---|
| 101 | 101 | |
|---|
| 102 | | uint toInt (uint min, uint max) |
|---|
| | 102 | uint toInt (uint min, uint max) |
|---|
| 103 | 103 | { |
|---|
| 104 | 104 | return (toInt % (max-min)) + min; |
|---|
| 105 | | } |
|---|
| | 105 | } |
|---|
| 106 | 106 | |
|---|
| 107 | 107 | /********************************************************************** |
|---|
| … | … | |
| 111 | 111 | **********************************************************************/ |
|---|
| 112 | 112 | |
|---|
| 113 | | uint toInt (bool pAddEntropy = false) |
|---|
| 114 | | { |
|---|
| 115 | | uint y; |
|---|
| 116 | | static uint mag01[2] =[0, MATRIX_A]; |
|---|
| 117 | | |
|---|
| 118 | | if (mti >= mt.length) { |
|---|
| 119 | | int kk; |
|---|
| 120 | | |
|---|
| 121 | | if (pAddEntropy || mti > mt.length) |
|---|
| 122 | | { |
|---|
| 123 | | seed (5489UL, pAddEntropy); |
|---|
| 124 | | } |
|---|
| 125 | | |
|---|
| 126 | | for (kk=0;kk<mt.length-M;kk++) |
|---|
| 127 | | { |
|---|
| 128 | | y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); |
|---|
| 129 | | mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 1UL]; |
|---|
| 130 | | } |
|---|
| 131 | | for (;kk<mt.length-1;kk++) { |
|---|
| 132 | | y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); |
|---|
| 133 | | mt[kk] = mt[kk+(M-mt.length)] ^ (y >> 1) ^ mag01[y & 1UL]; |
|---|
| 134 | | } |
|---|
| 135 | | y = (mt[mt.length-1]&UPPER_MASK)|(mt[0]&LOWER_MASK); |
|---|
| 136 | | mt[mt.length-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 1UL]; |
|---|
| 137 | | |
|---|
| 138 | | mti = 0; |
|---|
| 139 | | } |
|---|
| 140 | | |
|---|
| 141 | | y = mt[mti++]; |
|---|
| 142 | | |
|---|
| 143 | | y ^= (y >> 11); |
|---|
| 144 | | y ^= (y << 7) & 0x9d2c5680UL; |
|---|
| 145 | | y ^= (y << 15) & 0xefc60000UL; |
|---|
| 146 | | y ^= (y >> 18); |
|---|
| 147 | | |
|---|
| 148 | | vLastRand = y; |
|---|
| 149 | | return y; |
|---|
| 150 | | } |
|---|
| | 113 | uint toInt (bool pAddEntropy = false) |
|---|
| | 114 | { |
|---|
| | 115 | uint y; |
|---|
| | 116 | static uint mag01[2] =[0, MATRIX_A]; |
|---|
| | 117 | |
|---|
| | 118 | if (mti >= mt.length) { |
|---|
| | 119 | int kk; |
|---|
| | 120 | |
|---|
| | 121 | if (pAddEntropy || mti > mt.length) |
|---|
| | 122 | { |
|---|
| | 123 | seed (5489UL, pAddEntropy); |
|---|
| | 124 | } |
|---|
| | 125 | |
|---|
| | 126 | for (kk=0;kk<mt.length-M;kk++) |
|---|
| | 127 | { |
|---|
| | 128 | y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); |
|---|
| | 129 | mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 1UL]; |
|---|
| | 130 | } |
|---|
| | 131 | for (;kk<mt.length-1;kk++) { |
|---|
| | 132 | y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK); |
|---|
| | 133 | mt[kk] = mt[kk+(M-mt.length)] ^ (y >> 1) ^ mag01[y & 1UL]; |
|---|
| | 134 | } |
|---|
| | 135 | y = (mt[mt.length-1]&UPPER_MASK)|(mt[0]&LOWER_MASK); |
|---|
| | 136 | mt[mt.length-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 1UL]; |
|---|
| | 137 | |
|---|
| | 138 | mti = 0; |
|---|
| | 139 | } |
|---|
| | 140 | |
|---|
| | 141 | y = mt[mti++]; |
|---|
| | 142 | |
|---|
| | 143 | y ^= (y >> 11); |
|---|
| | 144 | y ^= (y << 7) & 0x9d2c5680UL; |
|---|
| | 145 | y ^= (y << 15) & 0xefc60000UL; |
|---|
| | 146 | y ^= (y >> 18); |
|---|
| | 147 | |
|---|
| | 148 | vLastRand = y; |
|---|
| | 149 | return y; |
|---|
| | 150 | } |
|---|
| 151 | 151 | |
|---|
| 152 | 152 | /********************************************************************** |
|---|
| … | … | |
| 156 | 156 | **********************************************************************/ |
|---|
| 157 | 157 | |
|---|
| 158 | | double toReal () |
|---|
| 159 | | { |
|---|
| 160 | | return toInt*(1.0/cast(double)uint.max); |
|---|
| 161 | | } |
|---|
| | 158 | double toReal () |
|---|
| | 159 | { |
|---|
| | 160 | return toInt*(1.0/cast(double)uint.max); |
|---|
| | 161 | } |
|---|
| 162 | 162 | |
|---|
| 163 | 163 | /********************************************************************** |
|---|
| … | … | |
| 167 | 167 | **********************************************************************/ |
|---|
| 168 | 168 | |
|---|
| 169 | | double toReal1 () |
|---|
| 170 | | { |
|---|
| 171 | | return toInt*(1.0/(cast(double)uint.max+1.0)); |
|---|
| 172 | | } |
|---|
| | 169 | double toReal1 () |
|---|
| | 170 | { |
|---|
| | 171 | return toInt*(1.0/(cast(double)uint.max+1.0)); |
|---|
| | 172 | } |
|---|
| 173 | 173 | |
|---|
| 174 | 174 | /********************************************************************** |
|---|
| … | … | |
| 178 | 178 | **********************************************************************/ |
|---|
| 179 | 179 | |
|---|
| 180 | | double toReal2 () |
|---|
| 181 | | { |
|---|
| 182 | | return ((cast(double)toInt) + 0.5)*(1.0/(cast(double)uint.max+1.0)); |
|---|
| 183 | | } |
|---|
| | 180 | double toReal2 () |
|---|
| | 181 | { |
|---|
| | 182 | return ((cast(double)toInt) + 0.5)*(1.0/(cast(double)uint.max+1.0)); |
|---|
| | 183 | } |
|---|
| 184 | 184 | |
|---|
| 185 | 185 | /********************************************************************** |
|---|
| … | … | |
| 189 | 189 | **********************************************************************/ |
|---|
| 190 | 190 | |
|---|
| 191 | | double toRealEx () |
|---|
| 192 | | { |
|---|
| 193 | | uint a=toInt >> 5, b=toInt >> 6; |
|---|
| 194 | | return(a*67108864.0+b)*(1.0/9007199254740992.0); |
|---|
| 195 | | } |
|---|
| 196 | | |
|---|
| | 191 | double toRealEx () |
|---|
| | 192 | { |
|---|
| | 193 | uint a=toInt >> 5, b=toInt >> 6; |
|---|
| | 194 | return(a*67108864.0+b)*(1.0/9007199254740992.0); |
|---|
| | 195 | } |
|---|
| | 196 | |
|---|
| 197 | 197 | /********************************************************************** |
|---|
| 198 | 198 | |
|---|
| … | … | |
| 201 | 201 | **********************************************************************/ |
|---|
| 202 | 202 | |
|---|
| 203 | | void seed (uint s, bool pAddEntropy = false) |
|---|
| 204 | | { |
|---|
| 205 | | mt[0]= (s + (pAddEntropy ? vLastRand + cast(uint) this : 0)) & 0xffffffffUL; |
|---|
| 206 | | for (mti=1; mti<mt.length; mti++){ |
|---|
| 207 | | mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); |
|---|
| 208 | | mt[mti] &= 0xffffffffUL; |
|---|
| 209 | | } |
|---|
| 210 | | } |
|---|
| | 203 | void seed (uint s, bool pAddEntropy = false) |
|---|
| | 204 | { |
|---|
| | 205 | mt[0]= (s + (pAddEntropy ? vLastRand + cast(uint) this : 0)) & 0xffffffffUL; |
|---|
| | 206 | for (mti=1; mti<mt.length; mti++){ |
|---|
| | 207 | mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); |
|---|
| | 208 | mt[mti] &= 0xffffffffUL; |
|---|
| | 209 | } |
|---|
| | 210 | } |
|---|
| 211 | 211 | |
|---|
| 212 | 212 | /********************************************************************** |
|---|
| … | … | |
| 217 | 217 | **********************************************************************/ |
|---|
| 218 | 218 | |
|---|
| 219 | | void init (uint[] init_key, bool pAddEntropy = false) |
|---|
| | 219 | void init (uint[] init_key, bool pAddEntropy = false) |
|---|
| 220 | 220 | { |
|---|
| 221 | 221 | int i, j, k; |
|---|
| 222 | | i=1; |
|---|
| 223 | | j=0; |
|---|
| 224 | | |
|---|
| 225 | | seed (19650218UL, pAddEntropy); |
|---|
| 226 | | for (k = (mt.length > init_key.length ? mt.length : init_key.length); k; k--) { |
|---|
| 227 | | mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))+ init_key[j] + j; |
|---|
| 228 | | mt[i] &= 0xffffffffUL; |
|---|
| 229 | | i++; |
|---|
| 230 | | j++; |
|---|
| 231 | | |
|---|
| 232 | | if (i >= mt.length){ |
|---|
| 233 | | mt[0] = mt[mt.length-1]; |
|---|
| 234 | | i=1; |
|---|
| 235 | | } |
|---|
| 236 | | |
|---|
| 237 | | if (j >= init_key.length){ |
|---|
| 238 | | j=0; |
|---|
| 239 | | } |
|---|
| 240 | | } |
|---|
| 241 | | |
|---|
| 242 | | for (k=mt.length-1; k; k--) { |
|---|
| 243 | | mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))- i; |
|---|
| 244 | | mt[i] &= 0xffffffffUL; |
|---|
| 245 | | i++; |
|---|
| 246 | | |
|---|
| 247 | | if (i>=mt.length){ |
|---|
| 248 | | mt[0] = mt[mt.length-1]; |
|---|
| 249 | | i=1; |
|---|
| 250 | | } |
|---|
| 251 | | } |
|---|
| 252 | | mt[0] |= 0x80000000UL; |
|---|
| 253 | | mti=0; |
|---|
| 254 | | } |
|---|
| | 222 | i=1; |
|---|
| | 223 | j=0; |
|---|
| | 224 | |
|---|
| | 225 | seed (19650218UL, pAddEntropy); |
|---|
| | 226 | for (k = (mt.length > init_key.length ? mt.length : init_key.length); k; k--) { |
|---|
| | 227 | mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))+ init_key[j] + j; |
|---|
| | 228 | mt[i] &= 0xffffffffUL; |
|---|
| | 229 | i++; |
|---|
| | 230 | j++; |
|---|
| | 231 | |
|---|
| | 232 | if (i >= mt.length){ |
|---|
| | 233 | mt[0] = mt[mt.length-1]; |
|---|
| | 234 | i=1; |
|---|
| | 235 | } |
|---|
| | 236 | |
|---|
| | 237 | if (j >= init_key.length){ |
|---|
| | 238 | j=0; |
|---|
| | 239 | } |
|---|
| | 240 | } |
|---|
| | 241 | |
|---|
| | 242 | for (k=mt.length-1; k; k--) { |
|---|
| | 243 | mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))- i; |
|---|
| | 244 | mt[i] &= 0xffffffffUL; |
|---|
| | 245 | i++; |
|---|
| | 246 | |
|---|
| | 247 | if (i>=mt.length){ |
|---|
| | 248 | mt[0] = mt[mt.length-1]; |
|---|
| | 249 | i=1; |
|---|
| | 250 | } |
|---|
| | 251 | } |
|---|
| | 252 | mt[0] |= 0x80000000UL; |
|---|
| | 253 | mti=0; |
|---|
| | 254 | } |
|---|
| 255 | 255 | } |
|---|
| 256 | 256 | |
|---|
Download in other formats:
|
 |
 |
|
 |
Copyright © 2006-2008 Tango. All Rights Reserved. | Page Width:
Static or
Dynamic
