PRNG: Why transition to Xoshiro128?

[AlanTheBeast]

I recently learned by dint of some experiments on a RaspPi, that FPC seems to be changing the PRNG from the stalwart MersenneTwister to Xoshiro128.

I'm no expert in such, but a little research shows:

MersenneTwister (64) period is 2^19937 - 1, where Xoshiro128 is a mere 2^128 - 1.

To be sure, Xoshiro128 is slightly faster at 0.36 cycles/B, v. MT at 0.62 cycles/B.

Further, MT takes up a lot more room for its state variables: 2504 bytes v. 16 bytes for Xoshiro128.

But, given that most applications are running on machines with gobs of memory, that surely can't be worth losing the 2^19809 X longer period?

Curious:  I searched the forum and don't see any discussion about why this transition is taking place.

[Laksen]

If you are serious about random numbers, surely you wouldn't want the Mersenne Twister, but would roll your own to ensure that your distributions have the properties you expect.

I haven't followed any changes to this recently, but if the RTL was changed to something more lightweight I would be a fan. It's a large pitfall for people coming from Delphi, that suddenly the Random() call takes about 10-100x the time.

[AlanTheBeast]

It's flat enough for me.  I don't need crytpo grade numbers for my uses.

I guess my real point is : why wasn't this discussed before implementing it.

[Kays]

PRNG: Why transition to Xoshiro128?

[…] Curious:  I searched the forum and don't see any discussion about why this transition is taking place.

[…] I guess my real point is : why wasn't this discussed before implementing it.

You looked in the wrong place. You search the git history for that. FPC commit 91CF1774 gets us to some discussion in FPC issue 955D.

[runewalsh]

Sorry, it was my whim, I like meaningless improvements and persuading the people to apply them with fancy scientific papers. Standard RNG is unusable for anything anyway, not because of the underlying algorithm, but because of its design (pathetic 32-bit seed and the only global state). Even for games, once you’ve gotten a taste of modernity and want to e.g. assign different RNGs to that chest and that monster so that hitting the monster and opening the chest is not different from opening the chest and hitting the monster, and saving and reloading doesn’t affect the outcomes.

[PascalDragon]

I guess my real point is : why wasn't this discussed before implementing it.

Because in the end there is no reason to discuss it. The PRNG behind Random is an implementation detail and it's documented as such. You're only supposed to get some random number from it without any guarantees except that there is some randomness involved and that the same sequence of Random calls made from the same setting of RandSeed will result in the same values for the exact same version of FPC compiled for the exact same platform.

[AlanTheBeast]

PRNG: Why transition to Xoshiro128?

[…] Curious:  I searched the forum and don't see any discussion about why this transition is taking place.

[…] I guess my real point is : why wasn't this discussed before implementing it.

You looked in the wrong place. You search the git history for that. FPC commit 91CF1774 gets us to some discussion in FPC issue 955D.

Silly me - looking for Pascal dev development discussions here instead of gitlab ... thanks.

[AlanTheBeast]

I guess my real point is : why wasn't this discussed before implementing it.

Because in the end there is no reason to discuss it. The PRNG behind Random is an implementation detail and it's documented as such. You're only supposed to get some random number from it without any guarantees except that there is some randomness involved and that the same sequence of Random calls made from the same setting of RandSeed will result in the same values for the exact same version of FPC compiled for the exact same platform.

Not sure I agree.  I sometimes have "obfuscated" data using Mersenne, though for trivial things not needing strong encryption.  Only thing needed was a way to save or re-generate the seed.  This change would have lost that data.  (This won't affect me actually, but could have - IAC - I've made a Mersenne T for use as an include or unit).

If I had anything important to encrypt I would use something designed to strongly encrypt files (such as Apple Disk Utility's 256 bit AES or "openssl enc -aes-256-cbc -salt -in file.txt -out file.enc").

OTOH, non declared for loop variables would be an accepted change not needing much discussion, IMO.   

Thanks - all - for your replies.

[MarkMLl]

Because in the end there is no reason to discuss it. The PRNG behind Random is an implementation detail and it's documented as such. You're only supposed to get some random number from it without any guarantees except that there is some randomness involved and that the same sequence of Random calls made from the same setting of RandSeed will result in the same values for the exact same version of FPC compiled for the exact same platform.

[/quote]

Which is a point I tried to emphasise very early on: I got a strong reaction from the developers when I suggested that since the RNG was (at that time) described as Mersenne then it ought to generate the expected sequence when given a known seed.

OTOH, non declared for loop variables would be an accepted change not needing much discussion, IMO.   

Actually, I disagree. IMO a control variable should be defined in the FOR statement itself, which would (a) ensure that type checking could still be used and (b) restrict its scope to the statement immediately following. Wirth's hack that the control variable has an undefined value after a FOR loop is one of the worst things he did, and that was compounded when somebody else added the break statement which (if taken) /did/ leave it with a defined value.

MarkMLl

[Warfley]

Even for games, once you’ve gotten a taste of modernity and want to e.g. assign different RNGs to that chest and that monster so that hitting the monster and opening the chest is not different from opening the chest and hitting the monster, and saving and reloading doesn’t affect the outcomes.

But why? It's not like the seed is reusable anyway (usually whenever you load the game, so you can't just repeat a sequence of events to savescum your way through a game), meaning it is not repeatable, therefore any dependency between those two events is not noticable to the player. If you open a chest and item X is rolled then you hit the monster, sure the result will be different as if you did it the other way around, but you can't test it, because if you reload, you have a new seed and you will get completely different results anyway. Also if you would have started that game 1 second later you get another seed (because it's usually clock based), and again have completely different results.

Note that for example the Random class provided by the unity game engine is also a singleton, meaning also one shared state for all random generations. And about that tiny 32 bit seed, Unity also only has a 32 bit seed. I think if state of the art game engines are fine with that, so can you.
The bigger issue is usually the speed for the random generation, which is why Unity is using the Linear Feedback Shift Register algorithm, even though it is not very sophisticated, it's very lightweight and fast.

[runewalsh]

Warfley, you store different RNGs with serializable states with the chest and the monster as part of their creation, and use them for related events. UnityEngine.Random both provides serializable Random.state and suggests switching to System.Random for “multiple independent random number generators”.

[Warfley]

Yes but System.Random is not provided by unity, it's a C# base class, and it is clearly stated that it is much slower. So it's clearly intended for special cases and unity optimizes for the most common case.

Why do something different with pascal, have a common case provided by random and if you need something more specialized, use something different. Also writing a LFSR with 128 bit state such as used by unity is what, 5 lines of code?
If you have such very specific requirements just write those 5 lines yourself and optimize them for your putposes

The system unit does not need to provide something for every niche application use case, just something that's good enough 90% of the time

[runewalsh]

Warfley, in practice you always need the C# (and many others) approach, you just might not realize it and end up doing increasingly complex workarounds. Certain games achieve what I describe by, say, “taking the per-game seed, concatenating it with the # of rolls made, and using the result (or its hash, or so) as RandSeed” or other nonsense, strictly inferior to just having as many states as you need. Global random can then be implemented for convenience on top of that by declaring a global state variable and wrapping it with a random() function... just as I did with Xoshiro128ss_32, while the reverse is impossible.

[AlanTheBeast]

OTOH, non declared for loop variables would be an accepted change not needing much discussion, IMO.   

Actually, I disagree. IMO a control variable should be defined in the FOR statement itself, which would (a) ensure that type checking could still be used and (b) restrict its scope to the statement immediately following. Wirth's hack that the control variable has an undefined value after a FOR loop is one of the worst things he did, and that was compounded when somebody else added the break statement which (if taken) /did/ leave it with a defined value.

As discussed once upon a time, by not declared, I mean in the VAR section.  Thus:

Code: Pascal  [Select][+][-]

1.       for i := 1 to 100 do            //  i scope begins and is assigned a register or pushed onto the stack here
2.            begin
3.               blaber(i,x);
4.               if (x> -0.1) and (x<0.1) then break;
5.               fliber (x);
6.            end;                              // i ceases to exist here
7.       b := a + i;                          // compiler error
8.  

Whether the undeclared value could be another sort of enumeration:      for b := apples to oranges do
should be okay, but might prove harder to implement (or not).

I'm pretty sure I used a Pascal compiler once upon a time where the final value of the control variable was either the last value of the loop or the successor, but that may have been a fluke.  Just tested it and in both main code and a procedure, the word value is the last value of the loop range after the loop exits.  (cue: "But that's not specified, and therefor cannot be relied upon").   

OTOH, if the control var is outside of a procedure it can be modified by a called procedure.  madness!

As to break (et al), (what a welcome addition! ) it's natural that the control value be as at the break point as it may have been a search of some kind and so i being an index to something would be obviously useful.

[MarkMLl]

 No, do it something like

Code: Pascal  [Select][+][-]

1.       for var i: integer= 1 to 100 do            //  i scope begins and is assigned a register or pushed onto the stack here
2.            begin
3.               blaber(i,x);
4.               if (x> -0.1) and (x<0.1) then break;
5.               fliber (x);
6.            end;                              // i ceases to exist here
7.       b := a + i;                          // compiler error
8.  

I'm pretty sure I used a Pascal compiler once upon a time where the final value of the control variable was either the last value of the loop or the successor, but that may have been a fluke.  Just tested it and in both main code and a procedure, the word value is the last value of the loop range after the loop exits.  (cue: "But that's not specified, and therefor cannot be relied upon").

Wirth specified that it be undefined in the original language. Any attempt to use it after the loop has exited is an error.

As to break (et al), (what a welcome addition! ) it's natural that the control value be as at the break point as it may have been a search of some kind and so i being an index to something would be obviously useful.

Sure, it's welcome but now having a situation where the control variable might or might not have a defined value is utter insanity.

MarkMLl