PRNG: Why transition to Xoshiro128? lazarus / 64-FPC development ---------------------------------------------------------------------- AlanTheBeast · 2023-09-14 17:57 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 · 2023-09-14 18:57 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 · 2023-09-14 20:32 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 · 2023-09-14 20:50 Quote from: AlanTheBeast on September 14, 2023, 07:57:24 pmPRNG: Why transition to Xoshiro128? […] Curious:  I searched the forum and don't see any discussion about why this transition is taking place.Quote from: AlanTheBeast on September 14, 2023, 10:32:16 pm[…] 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 · 2023-09-14 21:53 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 · 2023-09-17 16:20 Quote from: AlanTheBeast on September 14, 2023, 10:32:16 pmI 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 · 2023-09-17 22:41 Quote from: Kays on September 14, 2023, 10:50:48 pmQuote from: AlanTheBeast on September 14, 2023, 07:57:24 pmPRNG: Why transition to Xoshiro128? […] Curious:  I searched the forum and don't see any discussion about why this transition is taking place.Quote from: AlanTheBeast on September 14, 2023, 10:32:16 pm[…] 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 · 2023-09-17 22:56 Quote from: PascalDragon on September 17, 2023, 06:20:16 pmQuote from: AlanTheBeast on September 14, 2023, 10:32:16 pmI 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 · 2023-09-18 06:22 Quote from: AlanTheBeast on September 18, 2023, 12:56:18 amBecause 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. QuoteOTOH, 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 · 2023-09-18 07:54 Quote from: runewalsh on September 14, 2023, 11:53:58 pmEven 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 · 2023-09-18 13:39 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 · 2023-09-18 16:54 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 · 2023-09-18 18:06 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 · 2023-09-21 20:32 Quote from: MarkMLl on September 18, 2023, 08:22:34 amQuote from: AlanTheBeast on September 18, 2023, 12:56:18 amOTOH, 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i       for i := 1 to 100 do            //  i scope begins and is assigned a register or pushed onto the stack here           begin               blaber(i,x);               if (x> -0.1) and (x<0.1) then break;            fliber (x);           end;                              // i ceases to exist here      b := a + i;                          // compiler error  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 · 2023-09-22 07:15 No, do it something like Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i       for var i: integer= 1 to 100 do            //  i scope begins and is assigned a register or pushed onto the stack here           begin             blaber(i,x);               if (x> -0.1) and (x<0.1) then break;              fliber (x);           end;                            // i ceases to exist here      b := a + i;                        // compiler error  QuoteI'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. QuoteAs 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 ---------------------------------------------------------------------- MarkMLl · 2023-09-22 07:22 Quote from: runewalsh on September 18, 2023, 03:39:16 pmWarfley, 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”. So the chest etc. carry around their own generator polynomial plus the current value. However IMO you'd be better treating this as a crypto exercise, since encryption /by/ /definition/ generates a repeatable result while random number generation /by/ /definition/ produces a result that passes various tests of randomness. I sympathise with the "this is a Mersenne RNG so will generate a known test sequence" argument and its extension that test runs of a program should be reproducible, but this shouldn't be stretched to areas where it's not really applicable. MarkMLl ---------------------------------------------------------------------- Thaddy · 2023-09-22 07:59 The prng's in Freepascal made me so angry that I already wrote a couple of years ago: a: Thread safe randoms b: Delphi compatible random c: A 100% compatible Mersenne twister that is thread safe. d: All of Marsalia et al code into Pascal Although the core team are mostly computer scientists! they know jack shit about keeping data compatibility for statistical use. They simply do not understand that changing PRNG switches unavoidably breaks data sets. All my code can be found on this forum, the wiki and on Rosetta code. In general, the newer PRNG has a better distribution compared to the old one, it is also faster. But in general a PRNG should be pluggable, like in C11 or higher. Just because of statistics. ---------------------------------------------------------------------- runewalsh · 2023-09-22 08:27 Quote from: MarkMLl on September 22, 2023, 09:22:16 amSo the chest etc. carry around their own generator polynomial plus the current value. No, they carry around the state of the RNG (4 uint32s in the case of Xoshiro128**). ---------------------------------------------------------------------- Thaddy · 2023-09-22 08:51 Correct. Also note that you imply the unsigned.. which is even more correct. ---------------------------------------------------------------------- MarkMLl · 2023-09-22 10:06 Quote from: runewalsh on September 22, 2023, 10:27:32 amNo, they carry around the state of the RNG (4 uint32s in the case of Xoshiro128**). Which assumes that the RNG is provided by the RTL, which in that sort of case is clearly undesirable. My preference would be for the RNG to be provided by e.g. an LFSR, with coefficients and state carried around by the object. However as I've said, a crypto approach would be better. MarkMLl ---------------------------------------------------------------------- Kays · 2023-09-23 08:58 Quote from: PascalDragon on September 17, 2023, 06:20:16 pmBecause in the end there is no reason to discuss it.Where is this doctrine codified? Quote from: PascalDragon on September 17, 2023, 06:20:16 pmThe PRNG behind Random is an implementation detail and it's documented as such. […]This is certainly an argument that changing the implementation is not forbidden. It is not an argument that this change must occur. Quote from: runewalsh on September 14, 2023, 11:53:58 pm[…] I like meaningless improvements and persuading the people to apply them with fancy scientific papers. […]I’m afraid it is meaningless noise indeed. If there was a codified design principle the RTL must be as lightweight as possible, I could understand the motifs, why this implementation is an improvement. Otherwise I anticipate in ten years from now we’ll change the PRNG implementation again. Quote from: MarkMLl on September 18, 2023, 08:22:34 am[…] Wirth's hack that the control variable has an undefined value after a FOR loop is one of the worst things he did, […]Minor correction: The utilized control variable does not have an undefined state after a for-loop statement is executed. It just has the state prior evaluation of the for-statement commenced. In other words, the control variable does not get defined by the for-statement. ---------------------------------------------------------------------- MarkMLl · 2023-09-23 12:40 Quote from: Kays on September 23, 2023, 10:58:40 amQuote from: MarkMLl on September 18, 2023, 08:22:34 am[…] Wirth's hack that the control variable has an undefined value after a FOR loop is one of the worst things he did, […]Minor correction: The utilized control variable does not have an undefined state after a for-loop statement is executed. It just has the state prior evaluation of the for-statement commenced. In other words, the control variable does not get defined by the for- statement. My recollection is that Wirth explicitly said it did not have a defined value, however that might depend on the edition of J&W being consulted. I believe that somebody earlier in the thread highlighted different behaviour from different compilers. MarkMLl