new RNG is very broken

[ocyzl]

For example, after doing (define rng (make-pseudo-random-generator)) once, (pseudo-random-generator-next! rng (expt 2 32)) always returns 0, no matter how many times it's called, instead of returning a random integer chosen uniformly from the half-open interval [0, 2³²) as it should.

[mflatt]

Thanks for the report!

[ocyzl]

That looks much better. I think there are still a couple of small mistakes, though.

On line 3168, the second argument to random-int should be #x80000000 (2³¹), not #x7FFFFFFF (2³¹ - 1), because random-int returns a random number strictly less than its argument, and you want it to be able to return any 31-bit number, including the one that's all 1s.

Also, you can avoid some unnecessary calls to random-int if you let y be (- x 1) and then use y instead of x throughout the computation of maybe-result on lines 3160 - 3170. For example, if x is 2³¹, you need 31 random bits, so it's sufficient to call random-int once, but the current code calls it at least twice (more if maybe-result turns out to be too big).

[mflatt]

Thank you for your analysis and help! I've pushed another attempt, and hopefully I understood you correctly about (- x 1). (I think I understand why that works, but I am not sure I have it right.)

[ocyzl]

I'm not entirely sure I'm right, but here are my thoughts.

random-integer is supposed to return a number strictly less than x. So (- x 1) (i.e., y) is the largest number it could return. So (integer-length y) (i.e., len) is how many bits you need from random-int.

During the last iteration of the loop, when len < 32, the most significant bits of y (i.e., z) are the largest value that the corresponding bits of maybe-result should be allowed to have. And in order to get a random number that might be that large, you need to pass (+ z 1) to random-int, because it also returns a number strictly less than its argument.

So I think your current code is correct.