random() produces different value than on CPython

[Victor Norman]

We have written an application using Tkinter and that uses the random module to generate random numbers.

We have a whole test suite to test our functionality to make sure it is correct.

We ported our code over to Brython and now find that all our tests fail. We have determined that this is because the brython implementation of random produces different results than the CPython version of random.

E.g.:

CPython:

random.seed(0)

random.random() ==> 0.8444218515250481

Brython:

random.seed(0)

random.random() ==> 0.5488135039273248

Is this a bug or not? It probably isn't, but I wondered what your opinions are.

Thanks.

Vic

[Joao S. O. Bueno]

Definetely not a bug.
It is ok to rely on replicability over different runs on the same interprteer, same OS, 

but I doubt it is repeatable even across Python versions. 

--
You received this message because you are subscribed to the Google Groups "brython" group.
To unsubscribe from this group and stop receiving emails from it, send an email to brython+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/brython/a6d3f8ce-81ca-40c4-a60e-209e70941fdan%40googlegroups.com.

[Andy Lewis]

Actually, it is guaranteed to be repeatable  across different versions of CPython - the CPython documentation says:

"Most of the random module’s algorithms and seeding functions are subject to change across Python versions, but two aspects are guaranteed not to change:

• If a new seeding method is added, then a backward compatible seeder will be offered.

• The generator’s random() method will continue to produce the same sequence when the compatible seeder is given the same seed."

I checked some different CPythons (2.7, 3.6, 3.8), and also pypy2 and pypy3 and all gave the same result as Victor.

But that still doesn't mean that Brython should feel obliged to give the same result.

Best wishes

Andy

On Friday, June 18, 2021 at 6:34:01 PM UTC+1 gwi...@gmail.com wrote:

Definetely not a bug.
It is ok to rely on replicability over different runs on the same interprteer, same OS, 

but I doubt it is repeatable even across Python versions. 

 

To view this discussion on the web visit https://groups.google.com/d/msgid/brython/a6d3f8ce-81ca-40c4-a60e-209e70941fdan%40googlegroups.com.

[Edward Elliott]

For comparison, in javascript the implementation of PRNGs (pseudo-random number generators) is left up to the browser.  So repeatability is not guaranteed across any two machines.

However, it seems most browsers switched to the same PRNG algorithm in 2015 (xorshift128+).  So Math.random () works the same.  However, javascript does not provide a way to seed Math.random so there's no way to get a reproducible starting point.  If you want a seeded repeatable PRNG in javascript, you have to roll your own.  See:

https://hackernoon.com/how-does-javascripts-math-random-generate-random-numbers-ef0de6a20131

Brython's implementation uses the Mersenne twister algorithm (source).  I tried random.seed (0) on two browsers and got the same first result as you, 0.5488.  So brython does maintain compatibility across browsers.

CPython also uses the Mersenne twister PRNG algorithm.  So in theory, they could be compatible.  However there are other settings besides the initial seed, which must be different in cpython and brython.  See the cpython source.

I'll dig into the source files later to see if they can be easily synced, which would let brython return the same results as cpython.  Then it's up to Pierre whether to incorporate the change.  I agree with Andy, it's not necessary for brython and cpython to return the same PRNG sequence.  But it might be nice to have.

For reference, you can also check the page on brython stdlib differences to see areas where brython libs differs from cpython.

--

You received this message because you are subscribed to the Google Groups "brython" group.
To unsubscribe from this group and stop receiving emails from it, send an email to brython+u...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/brython/059a6b99-7847-4915-8718-3e89c9f89b1fn%40googlegroups.com.

[Edward Elliott]

Here's what I learned so far about random.seed in brython vs cpython.  I've done all I can.  Any further work is up to Pierre if he wants to make them compatible.

1. cpython uses a c module to implement mersenne twister algorithm.  source code

2. brython uses random.js to implement mersenne twister.  source code

the js code is derived from same c source.  all parameters appear to be the same.

3. Calling random.seed in cpython seems to call _random_Random_seed_impl in the c module, which then calls random_seed.  No matter the seed type (int, string, bytes, etc), random_seed calls init_by_array to setup the mersenne twister state.

4. brython's random.js also has a function init_by_array that seems to work the same.  However this function is never called anywhere that I can see.  Instead, calling random.seed uses init_genrand to setup the mersenne twister state.  This initializes state in a different way than the cpython code.  So that's why results are different in brython.

5. I ran a slightly modified random.js locally to see if init_by_array works the same as in the C module.  It does.   These two sequences return the same internal state:

cpython :      random.seed (0) ; random.getstate ()   

random.js :   r = RandomStream () ; r.init_by_array ([0], 1) ; r.getstate ()  

This means brython random module could generate the same sequence as cpython from a given seed.  All that's lacking is using the same calls to setup the RNG.

That said, fixing it would be a bit tricky.  Python random.seed accepts ints, strings, or bytes.  Cpython does setup in random_seed before calling init_by_array.  Each type is handled somewhat differently.  Brython would have to replicate that handling in random.js then call init_by_array to setup the RNG state.  It's possible, just requires translating this c code to js.  The c function is not self-contained, it uses many functions and macros defined elsewhere.

One more thing - I noticed that brython and cpython return slightly different objects from  random.getstate().  In both cases, the state object has 3 elements:

• a version number, which is always 3
• an array of unsigned ints (32-bit) representing the mersenne twister state
• the length of the array, which is always 624

Brython returns a tuple as : (version, int array, len)

Cpython returns a tuple as : (version, int array + [624], none). see source code.

In other words, Cpython puts the array length as an item at the end of the int array, and the third return value is empty.  Not sure why, perhaps it's a bug, but the format isn't documented anywhere.  Anyway it's been like that since at least python 2.7, so it's unlikely to change.

If brython wants to return compatible RNG state, then getstate in random.js need to be updated, particularly line 294:

random.getstate = function(){return [VERSION, mt, mti]}

where the second element should be mti appended to mt, and the third element is empty.  And setstate needs to be similarly updated to read the values in using that format.

With this change, you could save a PRNG state in cpython with random.getstate and restore it in brython with random.setstate (or vice versa).  This would let the same pseudo-random sequence be generated across platforms, or a sequence started on one platform and resumed on another, without using a seed value.  Something to think about.

HTH,

[Ray Luo]

Thanks, Edward, for the hard work on this technological investigation! Regardless of the next decision, I would suggest a github issue would be created with your findings, even if it would be later classified as a WontFix. This forum is for more generic topics.

[Pierre Quentel]

Le samedi 19 juin 2021 à 23:25:07 UTC+2, Edward Elliott a écrit :

Here's what I learned so far about random.seed in brython vs cpython.  I've done all I can.  Any further work is up to Pierre if he wants to make them compatible.

1. cpython uses a c module to implement mersenne twister algorithm.  source code

2. brython uses random.js to implement mersenne twister.  source code

the js code is derived from same c source.  all parameters appear to be the same.

3. Calling random.seed in cpython seems to call _random_Random_seed_impl in the c module, which then calls random_seed.  No matter the seed type (int, string, bytes, etc), random_seed calls init_by_array to setup the mersenne twister state.

4. brython's random.js also has a function init_by_array that seems to work the same.  However this function is never called anywhere that I can see.  Instead, calling random.seed uses init_genrand to setup the mersenne twister state.  This initializes state in a different way than the cpython code.  So that's why results are different in brython.

5. I ran a slightly modified random.js locally to see if init_by_array works the same as in the C module.  It does.   These two sequences return the same internal state:

cpython :      random.seed (0) ; random.getstate ()   

random.js :   r = RandomStream () ; r.init_by_array ([0], 1) ; r.getstate ()  

This means brython random module could generate the same sequence as cpython from a given seed.  All that's lacking is using the same calls to setup the RNG.

That said, fixing it would be a bit tricky.  Python random.seed accepts ints, strings, or bytes.  Cpython does setup in random_seed before calling init_by_array.  Each type is handled somewhat differently.  Brython would have to replicate that handling in random.js then call init_by_array to setup the RNG state.  It's possible, just requires translating this c code to js.  The c function is not self-contained, it uses many functions and macros defined elsewhere.

One more thing - I noticed that brython and cpython return slightly different objects from  random.getstate().  In both cases, the state object has 3 elements:

• a version number, which is always 3
• an array of unsigned ints (32-bit) representing the mersenne twister state
• the length of the array, which is always 624

Brython returns a tuple as : (version, int array, len)

Cpython returns a tuple as : (version, int array + [624], none). see source code.

In other words, Cpython puts the array length as an item at the end of the int array, and the third return value is empty.  Not sure why, perhaps it's a bug, but the format isn't documented anywhere.  Anyway it's been like that since at least python 2.7, so it's unlikely to change.

If brython wants to return compatible RNG state, then getstate in random.js need to be updated, particularly line 294:

random.getstate = function(){return [VERSION, mt, mti]}

where the second element should be mti appended to mt, and the third element is empty.  And setstate needs to be similarly updated to read the values in using that format.

With this change, you could save a PRNG state in cpython with random.getstate and restore it in brython with random.setstate (or vice versa).  This would let the same pseudo-random sequence be generated across platforms, or a sequence started on one platform and resumed on another, without using a seed value.  Something to think about.

HTH,

Many thanks Edward for the information. In today's commits I have implemented the changes you suggest; Brython now gives the same results as CPython (at least in all the tests I have made) when the seed is an int, str, bytes or bytearray.

Not yet for floats because it is based on the hash value, and Brython doesn't compute the correct hash for floats (if someone can help on this, he is welcome !)

- Pierre