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 --