Hey there everybody!
For my work on integrated shrinking approach for elm-test, I’ve had to ask the question of "what’s the maximum integer we can get out of elm/random?"
You might be surprised that the answer isn’t Random.maxInt (2^31 - 1) but instead 
2^32 - 1 
(assuming you’ll put 0 as the bottom limit: Random.int 0 (2^32 - 1)).
More in this writeup: Exploration of elm/random limits · GitHub
I hope it doesn’t have too many logical lapses and the result survives your scrutiny 
Hi Martin,
First of all, good job on the elm/random’s limits exploration! 4,294,967,295 is a pretty good number for most of the random generation tasks. I’m curious about the limits and design decisions behind elm/random implementation based on PCG. In the abstract section of paper there is this line:
The algorithm can be applied at variety of bit sizes, including 64 and 128 bits (which provide 32- and 64-bit outputs, with periods of 2^64 and 2^128).
I couldn’t find any hints/notes directory in elm/random or gists in evancz to answer my questions but would love to hear from core contributors on the subject.
The main contributor likely was @mgold.
I’m guessing that since we can’t use the 64bit integers in the library due to Elm max safe integer being 53bit, the next best thing to drop down to when implementing the PCG algorithm are 32bit integers, 2^32 period and so on.
This was work by Max, and I never got too into the particular algorithm details.
That said, I believe it was something about “getting enough randomness” for a uniform distribution over a given range. If you have 32-bits to produce 32-bits, it seems like you’d have to go in a predetermined order if you want to traverse every value, which is not very random at all! (E.g. every time you see 5 you know 8127 is next, then 902, etc. All the way back to 5.) Using 64-bits to produce 32-bits at least gives you 4 billion predetermined paths, so it would be harder to guess what comes after 5.
But again, I never got into pseudo-randomness algorithms, so this is just my basic intuition.
Would it make sense so fix this with a small patch to set
Random.maxInt = 2^32 -1
(rather than changing the algorithm)?
I’m not sure that’s a good idea: if we did that, Random.int Random.minInt Random.maxInt would only give negative numbers (IMHO that would be broken):
Right now what’s nice is that Random.int Random.minInt Random.maxInt gives you an uniform range of 2^32 signed integers. (half of the range is positive, half negative)
You can move that range around (it seems): Random.int 0 (2^32 - 1) is a range of 2^32 unsigned integers.
But as soon as you try to get more numbers out of that range, things seem to break.
@evancz, your reply made me worry about what happens for Random.int 0 (2^32 - 1) for various seeds (perhaps they all return the same sequence at this edge case? 
), but it seems we’re fine:
I guess to be 100% sure we’d need to find the same number in both and check what its successor is – I didn’t try that. But I’m willing to believe it will differ, until proven otherwise 
This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.
