mt

of 26
11 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
This paper is to appear in \ACM Transactions on Modeling and Computer Simulations: Special Issue on Uniform Random Number Generation (Early in 1998). Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator Makoto Matsumoto1 and Takuji Nishimura2 Keio University/Max-Planck-Institut fr Mathematik u 2 Keio University 1 In this paper, a new algorithm named astronomical period of 219937 dom numbers is proposed. For a particular choice of parameters, the algor
Document Share
Document Tags
Document Transcript
  Thispaperistoappearin\ACMTransactionson ModelingandComputerSimulations:SpecialIssue onUniformRandomNumberGeneration (Earlyin 1998).   MersenneTwister:A623-dimensionally equidistributeduniformpseudorandomnumber generator  MakotoMatsumoto  1  andTakujiNishimura  2 1  KeioUniversity/Max-Planck-InstitutfurMathematik  2  KeioUniversity  Inthispaper,anewalgorithmnamed  MersenneTwister  (MT)forgeneratinguniformpseudoran- domnumbersisproposed.Foraparticularchoiceofparameters,thealgorithmprovidesasuper astronomicalperiodof2  19937  0  1and623-dimensionalequidistributionupto32bitsaccuracy, whileconsumingaworkingareaofonly624words.Thisisanewvariantofthepreviouslypro- posedgeneratorsTGFSR,modiedsoastoadmitaMersenne-primeperiod.Thecharacteristic polynomialhasmanyterms.Thedistributionupto  v  bitsaccuracyfor1    v    32isalsoshown tobegood. Also,analgorithmtochecktheprimitivityofthecharacteristicpolynomialofMTwithcom- putationalcomplexity  O  (  p  2  )isgiven,where  p  isthedegreeofthepolynomial. WeimplementedthisgeneratorasaportableC-code.Itpassedseveralstringentstatistical tests,includingdiehard.Thespeediscomparabletoothermoderngenerators. Thesemeritsareaconsequenceoftheecientalgorithmsuniquetopolynomialcalculations overthetwo-elementeld. CategoriesandSubjectDescriptors:F.2.1[  TheoryofComputation  ]:NumericalAlgorithms andProblems|  Computationsinniteelds  ;G.2.1[  DiscreteMathematics  ]:Combinatorics|  recurrencesanddierenceequations  ;G.3[  ProbabilityandStatistics  ]:randomnumbergener- ation GeneralTerms:Algorithms,Theory,Experimentation AdditionalKeyWordsandPhrases:niteelds,GFSR,incompletearray,inversive-decimation method,  k  -distribution,MersennePrimes,MersenneTwister,  m  -sequences,MT19937,multiple- recursivematrixmethod,primitivepolynomials,randomnumbergeneration,tempering,TGFSR  DedicatedtotheMemoryofProfessorNobuoYONEDA  Name:MakotoMatsumoto Address:3-14-1Hiyoshi,Yokohama223Japan,Tel.+81-45-563-1141,Fax.+81-45-563-5948, email:matumoto@math.keio.ac.jp Aliation:DepartmentofMathematics,KeioUniversity Name:TakujiNishimura Address:3-14-1Hiyoshi,Yokohama223Japan,Tel.+81-45-563-1141,Fax.+81-45-563-5948, email:nisimura@comb.math.keio.ac.jp Aliation:DepartmentofMathematics,KeioUniversity   2  1  M.MatsumotoandT.Nishimura  1.INTRODUCTION 1.1Ashortsummary  Weproposeanewrandomnumbergenerator  MersenneTwister  .Animplemented C-codeMT19937hastheperiod2  19937  0  1and623-dimensionalequidistribution property,whichseemtobebestamongallgeneratorseverimplemented.There aretwonewideasaddedtotheprevioustwistedGFSR[MatsumotoandKurita 1992][MatsumotoandKurita1994]toattaintheserecords.Oneisan  incomplete array  (see  x  3.1)torealizeaMersenne-primeperiod.Theotherisafastalgorithmto testtheprimitivityofthecharacteristicpolynomialofalinearrecurrence,named  inversive-decimationmethod  (see  x  4.3).Thisalgorithmdoesnotrequireeventhe explicitformofthecharacteristicpolynomial.Itneedsonly(1)thedeningre- currence,and(2)somefastalgorithmthatobtainsthepresentstatevectorfrom its1-bitoutputstream.Thecomputationalcomplexityoftheinversive-decimation methodistheorderofthealgorithmin(2)multipliedbythedegreeofthechar- acteristicpolynomial.Toattainhigherorderequidistributionproperties,weused theresolution-wiselatticemethod(see[Tezuka1990][Coutureetal.1993][Tezuka 1994a]),withLenstra'salgorithm[Lenstra1985][Lenstraetal.1982]forsuccessive minima. Westressthatthesealgorithmsmakefulluseofthepolynomialalgebraoverthe two-elementeld.Therearenocorrespondingecientalgorithmsforintegers.  1.2  k  -distribution:areasonablemeasureofrandomness  Manygeneratorsofpresumably\highquality havebeenproposed,butonlyafew canbeusedforserioussimulations.Thisseemstobebecausewelackadecisivedef- initionofgood\randomness forpracticalpseudorandomnumbergenerators,and eachresearcherconcentratesonlyonhisparticularsetofmeasuresforrandomness. Amongmanyknownmeasures,thetestsbasedonthehigherdimensionaluni- formity,suchasthespectraltest(c.f.[Knuth1981]),andthe  k  -distributiontest describedbelow,areconsideredtobestrongest  1  .  Definition1.1.  Apseudorandomsequence  x  i  of  w  -bitintegersofperiod  P  sat- isfyingthefollowingconditionissaidtobek-distributedtov-bitaccuracy:let trunc  v  (  x  )  denotethenumberformedbytheleading  v  bitsof  x  ,andconsider  P  ofthe  kv  -bitvectors  (  trunc  v  (  x  i  )  ;  trunc  v  (  x  i  +1  )  ;  111  ;  trunc  v  (  x  i  +  k  0  1  ))(0    i<P  )  :  Then,eachofthe  2  kv  possiblecombinationsofbitsoccursthesamenumberoftimes inaperiod,exceptfortheall-zerocombinationthatoccursoncelessoften. Foreach  v  =1  ;  2  ;  111  ;w  ,let  k  (  v  )  denotethemaximumnumbersuchthatthe sequenceis  k  (  v  )  -distributedto  v  -bitaccuracy.  Notethattheinequality2  k  (  v  )  v  0  1    P  holds,sinceatmost  P  patternscanoccur inoneperiod,andthenumberofpossiblebitpatternsinthemostsignicant  v  bits  1  Fortheimportanceof  k  -distributionproperty,see[Tootilletal.1973][FushimiandTezuka 1983][Coutureetal.1993][Tezuka1995][Tezuka1994a][TezukaandL'Ecuyer1991][L'Ecuyer1996]. Aconcisedescriptioncanbeseenin[L'Ecuyer1994].   623-dimensionallyequidistributeduniformpseudorandomnumbergenerator  1  3  oftheconsecutive  k  (  v  )wordsis2  k  (  v  )  v  .Sinceweadmitaawatzero,weneedto add  0  1.Wecallthis  thetrivialupperbound  . Thegeometricmeaningisasfollows.Divideeachinteger  x  i  by2  w  tonormalizeit intoapseudorandomrealnumber  x  i  inthe[0  ;  1]-interval.Putthe  P  pointsinthe  k  - dimensionalunitcubewithcoordinates(  x  i  ;x  i  +1  ;:::;x  i  +  k  0  1  )(  i  =0  ;  1  ;:::;P  0  1), i.e.,theconsecutive  k  tuples,forawholeperiod(theadditioninthesuxis consideredmodulo  P  ).Weequallydivideeach[0,1]axisinto2  v  pieces(inother words,consideronlythemostsignicant  v  bits).Thus,wehavepartitionedthe unitcubeinto2  kv  smallcubes.Thesequenceis  k  -distributedto  v  -bitaccuracyif eachcubecontainsthesamenumberofpoints(exceptforthecubeattheorigin, whichcontainsoneless).Consequently,thehigher  k  (  v  )foreach  v  assureshigher- dimensionalequidistributionwith  v  -bitprecision.By  k  -distributiontest  ,wemean toobtainthevalues  k  (  v  ).Thistesttstothegeneratorsbasedonalinearrecursion overthetwoelementeld  F  2  (wecallthesegenerators  F  2  -generators  ). The  k  -distributionhasalsoakindofcryptographicinterpretation,asfollows. Assumethatthesequenceis  k  -distributedto  v  -bitaccuracy,andthatallthebits intheseedarerandomlygiven.Then,knowledgeofthemostsignicant  v  bitsof therst  l  wordsdoesnotallowtheusertomakeanystatementaboutthemost signicant  v  bitsofthenextword,if  l<k  .Thisisbecauseeverybit-patternoccurs equallylikelyinthe  v  bitsofthenextword,bydenitionof  k  -distribution.Thus, ifthesimulatedsystemissensitiveonlytothehistoryofthe  k  orlesspreviously generatedwordswith  v  -bitaccuracy,thenitistheoreticallysafe.  1.3Numberoftermsincharacteristicpolynomial  Anothercriterionontherandomnessof  F  2  -generatorsisthenumberoftermsin thecharacteristicpolynomialofthestatetransitionfunction.Many  F  2  -generators arebasedontrinomials,buttheyshowpoorrandomness(e.g.GFSRrejectedin anIsing-Modelsimulation[Ferrenberg,A.M.etal.1992],andaslightmodication oftrinomials[Fushimi1990]rejectedin[MatsumotoandKurita1994]).Forthese defects,see[Lindholm1968][Fredricsson1975][Compagner1991][Matsumotoand Kurita1992][MatsumotoandKurita1994][MatsumotoandKurita1996]. Asfarasweknow,alltheknown  F  2  -generatorssatisfyingthefollowingtwo criteria:(1)high  k  -distributionpropertiesforeach  v  (2)characteristicpolynomial withmanyterms(notarticiallyextractedfromatrinomial),aregoodgenerators [TezukaandL'Ecuyer1991][L'Ecuyer1996][MatsumotoandKurita1994],according tothestringenttestsandtheresultsintheactualapplications.  1.4Whatweobtained:afast,compact,huge-periodgeneratorMT  Weintroducean  F  2  -typegeneratornamed  MersenneTwister  (MT)whichsatises theabovecriteriaverywell,comparedtoanypreviouslyexistinggenerators.This isavariantoftheTGFSRalgorithmintroducedin[MatsumotoandKurita1992], improvedin[MatsumotoandKurita1994],andheremodiedsoastoadmita Mersenne-primeperiod.Asetofgoodparametersisimplementedasaportable  C  -codenamed  MT19937  (seeAppendixC).Thiscodecanbeusedinanymachine withastandardCcompiler(including64-bitmachines),asanintegerorrealnum- bergenerator.Essentiallythesamecodesaredownloadablefromthehttp-siteof SalzburgUniversity,  http://random.mat.sbg.ac.at/news/  . 
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x