trying to implement Mersenne Twister

[codifiesParticipant]

I want a repeatable sequence of numbers to do procedurally generated levels (I want to be sure of the same sequence regardless of OS or hardware)

I’ve attempted to implement https://en.wikipedia.org/wiki/Mersenne_Twister but seem to be getting four distinct bands of values when I plot 1000 values in a spreadsheet

anyone got any ideas what I’m doing wrong?

Monkey

[crayon-5cb9b3aad1250814286441 inline="true" ]'https://en.wikipedia.org/wiki/Mersenne_Twister Class MT19937 Method New(seed:uint) oldSeed = seed reset() End Method Method get:uint() If index >= 624 Then twist() Local y:UInt = mt[index] y = y ~ y Shr 11 y = y ~ y Shl 7 & 2636928640 y = y ~ y Shl 15 & 4022730752 y = y ~ y Shr 18 index = index + 1 Return mask(y) End Method Method reset() index = 624 mt[0] = oldSeed For Local i:Int = 1 To 624 mt[i] = mask(1812433253 * (mt[i-1] ~ mt[i-1] Shr 30) + i) Next End Method Private Field oldSeed:short Field index:int Field mt:UInt[] = New uint[624] Method mask:uint(x:UInt) Return $FFFFFFFF & x End Method Method twist() Local y:uint For Local i:Int = 0 To 624 y =mask( (mt[i] & $80000000) + (mt[(i+1) Mod 624] & $7fffffff) ) mt[i] = mask( mt[(i + 397) Mod 624] ~ y Shr 1 ) If (y Mod 2) <> 0 Then mt[i] = mt[i] ~ $9908b0df Next index = 0 End Method End Class Function Main() Local mt:MT19937 = New MT19937(12345678) #Rem For Local i:Int = 0 To 32 Print mt.get() Next Print "------" mt.reset() #end rem For Local i:Int = 0 To 1024 Print mt.get() Next End Function

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

[crayon-5cb9b3aad1250814286441 inline="true" ]'https://en.wikipedia.org/wiki/Mersenne_Twister   Class MT19937 Method New(seed:uint) oldSeed = seed reset() End Method Method get:uint() If index >= 624 Then twist() Local y:UInt = mt[index] y = y ~ y Shr 11 y = y ~ y Shl 7 & 2636928640 y = y ~ y Shl 15 & 4022730752 y = y ~ y Shr 18 index = index + 1 Return mask(y) End Method   Method reset() index = 624 mt[0] = oldSeed For Local i:Int = 1 To 624 mt[i] = mask(1812433253 * (mt[i-1] ~ mt[i-1] Shr 30) + i) Next End Method Private Field oldSeed:short Field index:int Field mt:UInt[] = New uint[624] Method mask:uint(x:UInt) Return $FFFFFFFF & x End Method Method twist() Local y:uint For Local i:Int = 0 To 624 y =mask( (mt[i] & $80000000) + (mt[(i+1) Mod 624] & $7fffffff) ) mt[i] = mask( mt[(i + 397) Mod 624] ~ y Shr 1 ) If (y Mod 2) <> 0 Then mt[i] = mt[i] ~ $9908b0df Next index = 0 End Method   End Class   Function Main() Local mt:MT19937 = New MT19937(12345678) #Rem For Local i:Int = 0 To 32 Print mt.get() Next   Print "------" mt.reset() #end rem   For Local i:Int = 0 To 1024 Print mt.get() Next End Function

[/crayon]

[abakoboParticipant]

Eeeks. That kind of bit shifting is so ugly..

With a fast look I see that oldseed is sometimes a short and sometimes a uint.. Is it normal?
In that kind of code we are supposed to see only unsigned things don’t we? (index i signed too)

[codifiesParticipant]

ack I was trying it as short must have missed one, sadly that makes no difference to this issue I described? the index type doesn’t seem to be causing the issue either….

out of interest why is bitshifting ugly?

[codifiesParticipant]

BINGO!

basically it was an issue with the order of precidence of operations, obviously things are evaluated differently to C / python….

Monkey

[crayon-5cb9b3aada192866616717 inline="true" ] 'https://en.wikipedia.org/wiki/Mersenne_Twister Class MT19937 Method New(seed:uint) oldSeed = seed reset() End Method Method get:uint() If index >= 624 Then twist() Local y:UInt = mt[index] y = y ~ (y Shr 11) y = y ~ ((y Shl 7) & 2636928640) y = y ~ ((y Shl 15) & 4022730752) y = y ~ (y Shr 18) index = index + 1 Return mask(y) End Method Method reset() index = 624 mt[0] = oldSeed For Local i:Int = 1 To 624 mt[i] = mask(1812433253 * (mt[i-1] ~ (mt[i-1] Shr 30)) + i) Next End Method Private Field oldSeed:UInt Field index:UInt Field mt:UInt[] = New uint[625] Method mask:uint(x:UInt) Return $FFFFFFFF & x End Method Method twist() Local y:UInt For Local i:Int = 0 To 624 y =mask( (mt[i] & $80000000) + (mt[(i+1) Mod 624] & $7fffffff) ) mt[i] = mask( mt[(i + 397) Mod 624] ~ y Shr 1 ) If (y Mod 2) <> 0 Then mt[i] = mt[i] ~ $9908b0df Next index = 0 End Method End Class Function Main() Local mt:MT19937 = New MT19937(123) #Rem For Local i:Int = 0 To 32 Print mt.get() Next Print "------" mt.reset() #end rem For Local i:Int = 0 To 1024 Print mt.get() Next End Function

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

[crayon-5cb9b3aada192866616717 inline="true" ] 'https://en.wikipedia.org/wiki/Mersenne_Twister   Class MT19937 Method New(seed:uint) oldSeed = seed reset() End Method Method get:uint() If index >= 624 Then twist() Local y:UInt = mt[index] y = y ~ (y Shr 11) y = y ~ ((y Shl 7) & 2636928640) y = y ~ ((y Shl 15) & 4022730752) y = y ~ (y Shr 18) index = index + 1 Return mask(y) End Method   Method reset() index = 624 mt[0] = oldSeed For Local i:Int = 1 To 624 mt[i] = mask(1812433253 * (mt[i-1] ~ (mt[i-1] Shr 30)) + i) Next End Method Private Field oldSeed:UInt Field index:UInt Field mt:UInt[] = New uint[625] Method mask:uint(x:UInt) Return $FFFFFFFF & x End Method Method twist() Local y:UInt For Local i:Int = 0 To 624 y =mask( (mt[i] & $80000000) + (mt[(i+1) Mod 624] & $7fffffff) ) mt[i] = mask( mt[(i + 397) Mod 624] ~ y Shr 1 ) If (y Mod 2) <> 0 Then mt[i] = mt[i] ~ $9908b0df Next index = 0 End Method   End Class   Function Main() Local mt:MT19937 = New MT19937(123) #Rem For Local i:Int = 0 To 32 Print mt.get() Next   Print "------" mt.reset() #end rem   For Local i:Int = 0 To 1024 Print mt.get() Next End Function

[/crayon]

[kanatiParticipant]

Ah this brings back memories.  Wrote the twister into a dll for use with B+ and BMax back in the day because both created a different set depending on which CPU architecture you had (Well, on certain intels and certain AMDs they did).  Glad to see someone else decided to implement it in Monkey so I don’t have to.   

[papgarParticipant]

Ooh this is really important for procedural generation in games and getting consistent results from a seed.  How is the performance using this is it a ton slower than just rand or not too bad?

[kanatiParticipant]

I haven’t tried codifies implementation of it but I wouldn’t imagine it to be significantly slower than the built in PRNG.  I know when I implemented it for blitzplus and blitzmax I saw no performance hit at all.  Though I will admit that I didn’t stress test it against Mark’s PRNG.  But it definitely gave consistent results across platforms.

[Author]

Posts