2017-10-20

Navigation

Skip Navigation Links

Hash algorithms

Asymmetric Algorithms

Symmetric Cipher Algorithms

Encoding Algorithms

Compression Algorithms

Pseudo Random Number Algorithms

Steganography

Library Wrappers

String Comparison

Others

Syntax highlighting by Prism
PBCrypto.com Mirror

Mersenne Twister

Algorithm creator(s)

Makoto Matsumoto, Takuji Nishimura


PB author(s)

Greg Turgeon


Description

A PRNG with a far longer period and far higher order of equidistribution than any other implemented generators. (It is proved that the period is 2^19937-1, and 623-dimensional equidistribution property is assured.)


Note

Has an enormous period at 2^19937-1, but possesses no cryptographic security.


Source

https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/25125-mersenne-twister-prng-for-pbwin70-pbcc30


See also


Source Code

Download source code file mersenne_twister.bas (Right-click -> "Save as ...")

#IF 0
-- MT.BAS --
 [revised]
   
The Mersenne Twister pseudo-random number generator has a 
period of (2^19937-1).  More detailed information is available at:
 http://www.math.sci.hiroshima-u.ac.j...at/MT/emt.html 
      
The PB code provided below incorporates several widely discussed 
improvements to the original Mersenne Twister implementation supplied 
by Makoto Matsumoto and Takuji Nishimura. Contributors to this public 
discussion include Shawn Cokus, Richard Wagner, and Eric Landry. 
   
George Marsaglia's DIEHARD utility is usually considered a standard 
tool for examining the output of PRNGs. DIEHARD can be found at:
 http://stat.fsu.edu/pub/diehard/ 
The code below includes a routine that will create the 10MB file 
required for running the entire suite of Diehard tests. Specifying 
the output file name (by defining the $DHFILE equate) causes the 
file to be created.
   
Note that this PRNG has an enormous period, but it possesses no 
cryptographic security. 
   
The following code compiles with either PBWIN70+ or PBCC30+.
   
This implementation replaces the original, which was posted in 2002. 
Advantages of this new version include enhanced efficiency, no 
reliance on global data, and the ability to run multiple generators 
simultaneously.
   
-- Greg Turgeon  1/2005
gturgeon at verizon dot net
#ENDIF 
   
#COMPILE EXE
#DIM ALL
#REGISTER NONE
'============
   
'-- Utility macros --
   
#IF %def(%PB_WIN32)
'--------------------
MACRO eol=$CR
'--------------------
MACRO ShowText(T)
   msgbox T
END MACRO
#ELSE
'--------------------
MACRO eol=$CRLF
'--------------------
MACRO ShowText(T)
   stdout T
END MACRO
#ENDIF
   
'--------------------
MACRO zbs(x)=string$(x,0)
   
'--------------------
MACRO EnterCC
#IF %DEF(%PB_CC32)
LOCAL launched&
if (cursory = 1) and (cursorx = 1) then launched& = -1
#ENDIF
END MACRO
   
'--------------------
MACRO ExitCC
#IF %DEF(%PB_CC32)
if launched& then
   input flush
   print "Press any key to end"
   waitkey$
end if
#ENDIF
END MACRO
   
'--------------------
MACRO FUNCTION shiftl(x,shiftval)
MACROTEMP retval
LOCAL retval AS DWORD
retval = x
!  shl   retval, shiftval
END MACRO = retval
   
'--------------------
MACRO FUNCTION shiftr(x,shiftval)
MACROTEMP retval
LOCAL retval AS DWORD
retval = x
!  shr   retval, shiftval
END MACRO = retval
   
   
   
'-- MT19937 equates & macros --
%N        = 624
%M        = 397
   
%MATRIX_A = &h9908b0df???
%UMASK    = &h80000000???
%LMASK    = &h7fffffff???
   
'--------------------
MACRO MixBits(v,w)=(((v) AND %UMASK) OR ((w) AND %LMASK))
   
'--------------------
MACRO FUNCTION Twist(u,v,w)
MACROTEMP x, y
LOCAL x AS DWORD, y AS DWORD
x = MixBits(v,w)
!  shr   x, 1
y = ((-(w AND 1)) AND %MATRIX_A)
END MACRO = (u XOR x XOR y)
   
   
TYPE MT_CONTEXT
   pState   AS DWORD PTR
   State    AS STRING * (4*(%N+1))
   Seed     AS DWORD
   Idx      AS LONG
END TYPE
   
DECLARE FUNCTION InitMT&(Ctx AS MT_CONTEXT)
DECLARE FUNCTION RandomMT???(Ctx AS MT_CONTEXT)
   
'-- Unrem and supply file name for Diehard data file
'$DHFILE = "f:\diehard\mt.$$$"
   
#IF %def($DHFILE)
DECLARE FUNCTION MakeDiehardFile&()
#ENDIF
   
'====================
FUNCTION PBMain&()
REGISTER i&, j&
LOCAL t$, ctx AS MT_CONTEXT
EnterCC
   
ctx.Seed = 5489
InitMT ctx
   
t = ""
for i = 1 to 5
   for j = 1 to 5
      t = t + using$("############", RandomMT(ctx)) + "  "
   next j
   t = t + eol
next i
ShowText(t)
   
#IF %def($DHFILE)
MakeDiehardFile
#ENDIF
   
ExitCC
END FUNCTION
   
   
'====================
FUNCTION InitMT&(Ctx AS MT_CONTEXT)
LOCAL i???, x???, y???, pd AS DWORD PTR
   
'-- Default seed if none supplied
if Ctx.Seed = 0 then Ctx.Seed = 5489
'-- Zero initial state & save pointer to it
Ctx.State  = zbs(sizeof(Ctx.State))
Ctx.pState = varptr(Ctx.State)
   
pd  = Ctx.pState
@pd = Ctx.Seed
for i = 1 to %N-1
   x = @pd
   y = x XOR shiftr(x,30)
   'y = (y * 1812433253) + i
   'Be sure to handle PB DWORD 
   'multiply this way
   !  mov   edx, y
   !  mov   eax, 1812433253
   !  mul   edx
   !  mov   x, eax
   incr pd
   @pd = x + i
next i
   
'-- Force reload on first call to RandomMT()
Ctx.Idx = %N+1
END FUNCTION
   
   
'====================
FUNCTION RandomMT???(Ctx AS MT_CONTEXT)
REGISTER i&
LOCAL x???, pd AS DWORD PTR
   
if Ctx.Idx >= %N then 'reload state array
   'if RandomMT() called w/o seeding
   if Ctx.@pState[0] = 0 then
      Ctx.Seed = 5489 : InitMT(Ctx)
   end if
   
   'local copy for speed
   pd = Ctx.pState
   
   for i = 0 to (%N-%M)-1
      @pd = Twist(@pd[%M],@pd[0],@pd[1])
      incr pd
   next i
   
   for i = (%N-%M) to (%N-2)
      @pd = Twist(@pd[%M-%N],@pd[0],@pd[1])
      incr pd
   next i
   
   @pd = Twist(@pd[%M-%N],@pd[0],Ctx.@pState[0])
   Ctx.Idx = 0
end if
   
x = Ctx.@pState[Ctx.Idx] : incr Ctx.Idx
   
x = x XOR  shiftr(x,11)
x = x XOR (shiftl(x, 7) AND &h9D2C5680)
x = x XOR (shiftl(x,15) AND &hEFC60000)
function = x XOR shiftr(x,18)
END FUNCTION
   
#IF %def($DHFILE)
'-- NOTE: Routine performs no file access error checking.
'============
FUNCTION MakeDiehardFile&()
REGISTER i&, j&
LOCAL  t$, buffer$, outfile&
LOCAL ctx AS MT_CONTEXT, pd AS DWORD PTR
   
'-- Truncate any existing $DHFILE
outfile = freefile
open $DHFILE for binary as outfile base = 0
seteof outfile
close outfile
   
ctx.Seed = 5489
InitMT ctx
   
for i = 1 to 10
   buffer = zbs(1000000)
   pd = strptr(buffer)
   j = len(buffer)\sizeof(@pd)
   do while j
      @pd = RandomMT(ctx) : incr pd
      decr j
   loop
   open $DHFILE for binary as outfile base = 0
   seek outfile, lof(outfile)
   put$ outfile, buffer
   if i = 10 then
      t = "Size of "+ $DHFILE + ":"+ str$(lof(outfile))
      ShowText(t)
   end if
   close outfile
next i
END FUNCTION
#ENDIF
'-- end MT.BAS --

Mirror provided by Knuth Konrad