libgo/go/math/rand/rng.go

   1 // Copyright 2009 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package rand
   6
   7 /*
   8  * Uniform distribution
   9  *
  10  * algorithm by
  11  * DP Mitchell and JA Reeds
  12  */
  13
  14 const (
  15         _LEN  = 607
  16         _TAP  = 273
  17         _MAX  = 1 << 63
  18         _MASK = _MAX - 1
  19         _A    = 48271
  20         _M    = (1 << 31) - 1
  21         _Q    = 44488
  22         _R    = 3399
  23 )
  24
  25 var (
  26         // cooked random numbers
  27         // the state of the rng
  28         // after 780e10 iterations
  29         rng_cooked [_LEN]int64 = [...]int64{
  30                 5041579894721019882, 4646389086726545243, 1395769623340756751, 5333664234075297259,
  31                 2875692520355975054, 9033628115061424579, 7143218595135194537, 4812947590706362721,
  32                 7937252194349799378, 5307299880338848416, 8209348851763925077, 2115741599318814044,
  33                 4593015457530856296, 8140875735541888011, 3319429241265089026, 8619815648190321034,
  34                 1727074043483619500, 113108499721038619, 4569519971459345583, 5062833859075314731,
  35                 2387618771259064424, 2716131344356686112, 6559392774825876886, 7650093201692370310,
  36                 7684323884043752161, 257867835996031390, 6593456519409015164, 271327514973697897,
  37                 2789386447340118284, 1065192797246149621, 3344507881999356393, 4459797941780066633,
  38                 7465081662728599889, 1014950805555097187, 4449440729345990775, 3481109366438502643,
  39                 2418672789110888383, 5796562887576294778, 4484266064449540171, 3738982361971787048,
  40                 4523597184512354423, 10530508058128498, 8633833783282346118, 2625309929628791628,
  41                 8660405965245884302, 10162832508971942, 6540714680961817391, 7031802312784620857,
  42                 6240911277345944669, 831864355460801054, 8004434137542152891, 2116287251661052151,
  43                 2202309800992166967, 9161020366945053561, 4069299552407763864, 4936383537992622449,
  44                 457351505131524928, 342195045928179354, 2847771682816600509, 2068020115986376518,
  45                 4368649989588021065, 887231587095185257, 5563591506886576496, 6816225200251950296,
  46                 5616972787034086048, 8471809303394836566, 1686575021641186857, 4045484338074262002,
  47                 4244156215201778923, 7848217333783577387, 5632136521049761902, 833283142057835272,
  48                 9029726508369077193, 3243583134664087292, 4316371101804477087, 8937849979965997980,
  49                 6446940406810434101, 1679342092332374735, 6050638460742422078, 6993520719509581582,
  50                 7640877852514293609, 5881353426285907985, 812786550756860885, 4541845584483343330,
  51                 2725470216277009086, 4980675660146853729, 5210769080603236061, 8894283318990530821,
  52                 6326442804750084282, 1495812843684243920, 7069751578799128019, 7370257291860230865,
  53                 6756929275356942261, 4706794511633873654, 7824520467827898663, 8549875090542453214,
  54                 33650829478596156, 1328918435751322643, 7297902601803624459, 1011190183918857495,
  55                 2238025036817854944, 5147159997473910359, 896512091560522982, 2659470849286379941,
  56                 6097729358393448602, 1731725986304753684, 4106255841983812711, 8327155210721535508,
  57                 8477511620686074402, 5803876044675762232, 8435417780860221662, 5988852856651071244,
  58                 4715837297103951910, 7566171971264485114, 505808562678895611, 5070098180695063370,
  59                 842110666775871513, 572156825025677802, 1791881013492340891, 3393267094866038768,
  60                 3778721850472236509, 2352769483186201278, 1292459583847367458, 8897907043675088419,
  61                 5781809037144163536, 2733958794029492513, 5092019688680754699, 8996124554772526841,
  62                 4234737173186232084, 5027558287275472836, 4635198586344772304, 8687338893267139351,
  63                 5907508150730407386, 784756255473944452, 972392927514829904, 5422057694808175112,
  64                 5158420642969283891, 9048531678558643225, 2407211146698877100, 7583282216521099569,
  65                 3940796514530962282, 3341174631045206375, 3095313889586102949, 7405321895688238710,
  66                 5832080132947175283, 7890064875145919662, 8184139210799583195, 1149859861409226130,
  67                 1464597243840211302, 4641648007187991873, 3516491885471466898, 956288521791657692,
  68                 6657089965014657519, 5220884358887979358, 1796677326474620641, 5340761970648932916,
  69                 1147977171614181568, 5066037465548252321, 2574765911837859848, 1085848279845204775,
  70                 3350107529868390359, 6116438694366558490, 2107701075971293812, 1803294065921269267,
  71                 2469478054175558874, 7368243281019965984, 3791908367843677526, 185046971116456637,
  72                 2257095756513439648, 7217693971077460129, 909049953079504259, 7196649268545224266,
  73                 5637660345400869599, 3955544945427965183, 8057528650917418961, 4139268440301127643,
  74                 6621926588513568059, 1373361136802681441, 6527366231383600011, 3507654575162700890,
  75                 9202058512774729859, 1954818376891585542, 6640380907130175705, 8299563319178235687,
  76                 3901867355218954373, 7046310742295574065, 6847195391333990232, 1572638100518868053,
  77                 8850422670118399721, 3631909142291992901, 5158881091950831288, 2882958317343121593,
  78                 4763258931815816403, 6280052734341785344, 4243789408204964850, 2043464728020827976,
  79                 6545300466022085465, 4562580375758598164, 5495451168795427352, 1738312861590151095,
  80                 553004618757816492, 6895160632757959823, 8233623922264685171, 7139506338801360852,
  81                 8550891222387991669, 5535668688139305547, 2430933853350256242, 5401941257863201076,
  82                 8159640039107728799, 6157493831600770366, 7632066283658143750, 6308328381617103346,
  83                 3681878764086140361, 3289686137190109749, 6587997200611086848, 244714774258135476,
  84                 4079788377417136100, 8090302575944624335, 2945117363431356361, 864324395848741045,
  85                 3009039260312620700, 8430027460082534031, 401084700045993341, 7254622446438694921,
  86                 4707864159563588614, 5640248530963493951, 5982507712689997893, 3315098242282210105,
  87                 5503847578771918426, 3941971367175193882, 8118566580304798074, 3839261274019871296,
  88                 7062410411742090847, 741381002980207668, 6027994129690250817, 2497829994150063930,
  89                 6251390334426228834, 1368930247903518833, 8809096399316380241, 6492004350391900708,
  90                 2462145737463489636, 404828418920299174, 4153026434231690595, 261785715255475940,
  91                 5464715384600071357, 592710404378763017, 6764129236657751224, 8513655718539357449,
  92                 5820343663801914208, 385298524683789911, 5224135003438199467, 6303131641338802145,
  93                 7150122561309371392, 368107899140673753, 3115186834558311558, 2915636353584281051,
  94                 4782583894627718279, 6718292300699989587, 8387085186914375220, 3387513132024756289,
  95                 4654329375432538231, 8930667561363381602, 5374373436876319273, 7623042350483453954,
  96                 7725442901813263321, 9186225467561587250, 4091027289597503355, 2357631606492579800,
  97                 2530936820058611833, 1636551876240043639, 5564664674334965799, 1452244145334316253,
  98                 2061642381019690829, 1279580266495294036, 9108481583171221009, 6023278686734049809,
  99                 5007630032676973346, 2153168792952589781, 6720334534964750538, 6041546491134794105,
 100                 3433922409283786309, 2285479922797300912, 3110614940896576130, 6366559590722842893,
 101                 5418791419666136509, 7163298419643543757, 4891138053923696990, 580618510277907015,
 102                 1684034065251686769, 4429514767357295841, 330346578555450005, 1119637995812174675,
 103                 7177515271653460134, 4589042248470800257, 7693288629059004563, 143607045258444228,
 104                 246994305896273627, 866417324803099287, 6473547110565816071, 3092379936208876896,
 105                 2058427839513754051, 5133784708526867938, 8785882556301281247, 6149332666841167611,
 106                 8585842181454472135, 6137678347805511274, 2070447184436970006, 5708223427705576541,
 107                 5999657892458244504, 4358391411789012426, 325123008708389849, 6837621693887290924,
 108                 4843721905315627004, 6010651222149276415, 5398352198963874652, 4602025990114250980,
 109                 1044646352569048800, 9106614159853161675, 829256115228593269, 4919284369102997000,
 110                 2681532557646850893, 3681559472488511871, 5307999518958214035, 6334130388442829274,
 111                 2658708232916537604, 1163313865052186287, 581945337509520675, 3648778920718647903,
 112                 4423673246306544414, 1620799783996955743, 220828013409515943, 8150384699999389761,
 113                 4287360518296753003, 4590000184845883843, 5513660857261085186, 6964829100392774275,
 114                 478991688350776035, 8746140185685648781, 228500091334420247, 1356187007457302238,
 115                 3019253992034194581, 3152601605678500003, 430152752706002213, 5559581553696971176,
 116                 4916432985369275664, 663574931734554391, 3420773838927732076, 2868348622579915573,
 117                 1999319134044418520, 3328689518636282723, 2587672709781371173, 1517255313529399333,
 118                 3092343956317362483, 3662252519007064108, 972445599196498113, 7664865435875959367,
 119                 1708913533482282562, 6917817162668868494, 3217629022545312900, 2570043027221707107,
 120                 8739788839543624613, 2488075924621352812, 4694002395387436668, 4559628481798514356,
 121                 2997203966153298104, 1282559373026354493, 240113143146674385, 8665713329246516443,
 122                 628141331766346752, 4571950817186770476, 1472811188152235408, 7596648026010355826,
 123                 6091219417754424743, 7834161864828164065, 7103445518877254909, 4390861237357459201,
 124                 4442653864240571734, 8903482404847331368, 622261699494173647, 6037261250297213248,
 125                 504404948065709118, 7275215526217113061, 1011176780856001400, 2194750105623461063,
 126                 2623071828615234808, 5157313728073836108, 3738405111966602044, 2539767524076729570,
 127                 2467284396349269342, 5256026990536851868, 7841086888628396109, 6640857538655893162,
 128                 1202087339038317498, 2113514992440715978, 7534350895342931403, 4925284734898484745,
 129                 5145623771477493805, 8225140880134972332, 2719520354384050532, 9132346697815513771,
 130                 4332154495710163773, 7137789594094346916, 6994721091344268833, 6667228574869048934,
 131                 655440045726677499, 59934747298466858, 6124974028078036405, 8957774780655365418,
 132                 2332206071942466437, 1701056712286369627, 3154897383618636503, 1637766181387607527,
 133                 2460521277767576533, 197309393502684135, 643677854385267315, 2543179307861934850,
 134                 4350769010207485119, 4754652089410667672, 2015595502641514512, 7999059458976458608,
 135                 4287946071480840813, 8362686366770308971, 6486469209321732151, 3617727845841796026,
 136                 7554353525834302244, 4450022655153542367, 1605195740213535749, 5327014565305508387,
 137                 4626575813550328320, 2692222020597705149, 241045573717249868, 5098046974627094010,
 138                 7916882295460730264, 884817090297530579, 5329160409530630596, 7790979528857726136,
 139                 4955070238059373407, 4918537275422674302, 3008076183950404629, 3007769226071157901,
 140                 2470346235617803020, 8928702772696731736, 7856187920214445904, 4474874585391974885,
 141                 7900176660600710914, 2140571127916226672, 2425445057265199971, 2486055153341847830,
 142                 4186670094382025798, 1883939007446035042, 8808666044074867985, 3734134241178479257,
 143                 4065968871360089196, 6953124200385847784, 1305686814738899057, 1637739099014457647,
 144                 3656125660947993209, 3966759634633167020, 3106378204088556331, 6328899822778449810,
 145                 4565385105440252958, 1979884289539493806, 2331793186920865425, 3783206694208922581,
 146                 8464961209802336085, 2843963751609577687, 3030678195484896323, 4793717574095772604,
 147                 4459239494808162889, 402587895800087237, 8057891408711167515, 4541888170938985079,
 148                 1042662272908816815, 5557303057122568958, 2647678726283249984, 2144477441549833761,
 149                 5806352215355387087, 7117771003473903623, 5916597177708541638, 462597715452321361,
 150                 8833658097025758785, 5970273481425315300, 563813119381731307, 2768349550652697015,
 151                 1598828206250873866, 5206393647403558110, 6235043485709261823, 3152217402014639496,
 152                 8469693267274066490, 125672920241807416, 5311079624024060938, 6663754932310491587,
 153                 8736848295048751716, 4488039774992061878, 5923302823487327109, 140891791083103236,
 154                 7414942793393574290, 7990420780896957397, 4317817392807076702, 3625184369705367340,
 155                 2740722765288122703, 5743100009702758344, 5997898640509039159, 8854493341352484163,
 156                 5242208035432907801, 701338899890987198, 7609280429197514109, 3020985755112334161,
 157                 6651322707055512866, 2635195723621160615, 5144520864246028816, 1035086515727829828,
 158                 1567242097116389047, 8172389260191636581, 6337820351429292273, 2163012566996458925,
 159                 2743190902890262681, 1906367633221323427, 6011544915663598137, 5932255307352610768,
 160                 2241128460406315459, 895504896216695588, 3094483003111372717, 4583857460292963101,
 161                 9079887171656594975, 8839289181930711403, 5762740387243057873, 4225072055348026230,
 162                 1838220598389033063, 3801620336801580414, 8823526620080073856, 1776617605585100335,
 163                 7899055018877642622, 5421679761463003041, 5521102963086275121, 4248279443559365898,
 164                 8735487530905098534, 1760527091573692978, 7142485049657745894, 8222656872927218123,
 165                 4969531564923704323, 3394475942196872480, 6424174453260338141, 359248545074932887,
 166                 3273651282831730598, 6797106199797138596, 3030918217665093212, 145600834617314036,
 167                 6036575856065626233, 740416251634527158, 7080427635449935582, 6951781370868335478,
 168                 399922722363687927, 294902314447253185, 7844950936339178523, 880320858634709042,
 169                 6192655680808675579, 411604686384710388, 9026808440365124461, 6440783557497587732,
 170                 4615674634722404292, 539897290441580544, 2096238225866883852, 8751955639408182687,
 171                 1907224908052289603, 7381039757301768559, 6157238513393239656, 7749994231914157575,
 172                 8629571604380892756, 5280433031239081479, 7101611890139813254, 2479018537985767835,
 173                 7169176924412769570, 7942066497793203302, 1357759729055557688, 2278447439451174845,
 174                 3625338785743880657, 6477479539006708521, 8976185375579272206, 5511371554711836120,
 175                 1326024180520890843, 7537449876596048829, 5464680203499696154, 3189671183162196045,
 176                 6346751753565857109, 241159987320630307, 3095793449658682053, 8978332846736310159,
 177                 2902794662273147216, 7208698530190629697, 7276901792339343736, 1732385229314443140,
 178                 4133292154170828382, 2918308698224194548, 1519461397937144458, 5293934712616591764,
 179                 4922828954023452664, 2879211533496425641, 5896236396443472108, 8465043815351752425,
 180                 7329020396871624740, 8915471717014488588, 2944902635677463047, 7052079073493465134,
 181                 8382142935188824023, 9103922860780351547, 4152330101494654406,
 182         }
 183 )
 184
 185 type rngSource struct {
 186         tap  int         // index into vec
 187         feed int         // index into vec
 188         vec  [_LEN]int64 // current feedback register
 189 }
 190
 191 // seed rng x[n+1] = 48271 * x[n] mod (2**31 - 1)
 192 func seedrand(x int32) int32 {
 193         hi := x / _Q
 194         lo := x % _Q
 195         x = _A*lo - _R*hi
 196         if x < 0 {
 197                 x += _M
 198         }
 199         return x
 200 }
 201
 202 // Seed uses the provided seed value to initialize the generator to a deterministic state.
 203 func (rng *rngSource) Seed(seed int64) {
 204         rng.tap = 0
 205         rng.feed = _LEN - _TAP
 206
 207         seed = seed % _M
 208         if seed < 0 {
 209                 seed += _M
 210         }
 211         if seed == 0 {
 212                 seed = 89482311
 213         }
 214
 215         x := int32(seed)
 216         for i := -20; i < _LEN; i++ {
 217                 x = seedrand(x)
 218                 if i >= 0 {
 219                         var u int64
 220                         u = int64(x) << 40
 221                         x = seedrand(x)
 222                         u ^= int64(x) << 20
 223                         x = seedrand(x)
 224                         u ^= int64(x)
 225                         u ^= rng_cooked[i]
 226                         rng.vec[i] = u & _MASK
 227                 }
 228         }
 229 }
 230
 231 // Int63 returns a non-negative pseudo-random 63-bit integer as an int64.
 232 func (rng *rngSource) Int63() int64 {
 233         rng.tap--
 234         if rng.tap < 0 {
 235                 rng.tap += _LEN
 236         }
 237
 238         rng.feed--
 239         if rng.feed < 0 {
 240                 rng.feed += _LEN
 241         }
 242
 243         x := (rng.vec[rng.feed] + rng.vec[rng.tap]) & _MASK
 244         rng.vec[rng.feed] = x
 245         return x
 246 }