When you use a random number generator, usually it gives you a number between 0 and 1. This suggests me that it’s dividing the random integer it produced by some other number. For example,

>>> random.random() 0.14343995062379244

This is Python, which is using Mersenne Twister. What would be the integer it computed before dividing it by [this] other number — the [divisor]? And also what is this other [divisor] number? (I’m asking myself these questions right now and being clueless as to how to approach them.)

You might be interested in https://github.com/racket/ChezScheme/blob/master/c/random.c

Thanks! Two interesting numbers appear in this source.

#define m1 4294967087.0 #define m2 4294944443.0

They both seem to require 32 bits of storage, which suggests that the “word size” of this generator is 32 bits. This tells me that perhaps each integer produced by the generator is divided by 2^32 (or something close to it) so that we always get output between 0 and 1. But I can’t confirm this. Here’s a sample number.

> (random-seed 1) > (random) 0.5067308904603183 > (/ 5067308904603183.0 (expt 2 32)) 1179824.7938517442 >

Clearly things don’t work as I’m guessing they would. I’d like to know how to go from the output (0.5067…) to the integer that the generator really produced. The generator doesn’t produce 0.5067… It produces an integer that’s the result of all its bits in its output. I’d like to map the output back to that integer and I’d think to do that I must find out this last operation the generator performs before handing the user the output number. I think it must be some kind of division and the divisor must be some kind of “word size” associated with the generator.

That’s a lot more interesting! Let me do some calculations here and see what I get.

This is looking plausible. Here’s the number I get.

> (define norm 2.328306549295728e-10) > (define u1 0.5067308904603183) > (/ u1 norm) 2176392497.0 > (- (/ u1 norm) 1.0) 2176392496.0

So I claim the integer produced was 2176392496 though the output is 0.5067308904603183. I’m already satisfied. Thanks for pointing me in this direction. Of course, I still don’t know if I’m right, but I’m happy with a hypothesis. (I had nothing.)

What do you need it for? (If you just need an integer, you can use random-integer).

Or perhaps random-natural.

Oh, this is just intellectual curiosity.

The analog in Mersenne Twister, Python’s default generator. (Interesting. I don’t know why your images look much more zoomed in than mine.)

I think Racket BC uses the Mersenne Twister too,

yes, that file is shared by both

You know, I wouldn’t think that’s right. Isn’t Racket 6 Racket BC? It already uses MRG32k3a. https://download.racket-lang.org/releases/6.12/doc/reference/generic-numbers.html?q=random#%28def._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._random%29%29

You are right.

The choice was probably due to: https://srfi.schemers.org/srfi-27/srfi-27.html

Makes sense. The choice seems good, nevertheless. MRG32k3a passes BigCrush from L’Ecuyer’s TestU01 library.

So that snippet of an implementation of Mersenne Twister suggests that a double is obtained by getting a long and dividing it by 0xffffffff = 2^32 - 1, so I should be able to get the output and multiply it by 2^32 - 1, but that doesn’t yield an integer.

>>> random.random() 0.763774618976614 >>> 0.763774618976614 * (2**32 - 1) 3280387009.255644

So unlike the vast majority of programming languages out there, Racket’s default generator is still “unbroken”.

I think you’re right. Here’s what I get with the following number.

>>> 0.763774618976614 * 2**53 6879470178836243.0

The source code claims the double is 53-bit, so I figure 2^53 is the right multiplier here and it seems to work. If you multiply by 2^52, you still don’t get an integer. I think I found my multiplier. Thanks!

So that implementation dividing by 0xffffffff is actually a 32-bit resolution on the double that it produces. I claim it’s effectively a different generator than than the one Python uses.

Wikipedia mentions both a 32- and a 64-bit version: https://en.wikipedia.org/wiki/Mersenne_Twister

Interesting. It doesn’t mention the 53-bit Python seems to implement.