# Re: Pseudo Random Number Generation across PicoLisp implementations

```On Sun, Apr 26, 2015 at 5:48 PM, Alexander Burger <a...@software-lab.de> wrote:
> Hi Christophe,
>
> […]
>
>> return n>=0? n*2 : -n*2+1;
>>
>> This ensures the return value is non negative (?).
>> But why would not the result overflow?
>
> Yes, it may overflow. The above operation is to keep the sign bit in bit
> zero of the result. The sign bit is more important than the highest bit
> of the number.```
```
Interesting. But I don't understand why the sign bit is so important
for the seed. Maybe it's related to what I discovered when working
on (rand), see below.

Ah ah ! In fact I realised this when working on the rand function.
It didn't occurred to me that it was also the solution for initSeed.
After sending the email about initSeed, I returned to rand.
I did take more time to test EmuLisp's new rand function,
in particular when sending it two args.

In fact rand worked better than I first thought since it gave
the same results than the Ersatz one. It is not proved, but
when I say "the results are the same", in fact the results
matched for ten consecutive calls of (rand 0 10000) which
is a quite high probability for «eternal» matching.
The quality of the tests is the same when testing (rand)
and (rand T), with respect to the space of the possible values.

Here I'll discuss
1: (rand 0 10000)
2: (rand)
3: (rand T)

1)a) First, for (rand 0 10000), my implementation in EmuLisp
was correct when trying to mimic Ersatz.

1)b) Moreover, when removing this line:
shiftedSeed = shiftedSeed.div(2);
which implemented the >>>33 instead of >>>32,
the results are the ones of PicoLisp32.

2)a) Then for (rand), my implementation accidentally borrowed
a line of pil32: getting the higher bits instead of the lower ones.
Now that the mistake is fixed it correctly mimics Ersatz.
I had to use the x<2^31 ? x : x-2^32
trick (discussed by Alex) to mimic the (int) casting.

2)b) I got stuck when trying to mimic the (rand) of pil32.
In doRand, at this line in big.c:
return box(hi(Seed));
In Ersatz in rand (x n)
at this line:
return new Number((int)Seed);
This seemed so similar that I banged my head on the screen showing
the discrepancies between the results of pil32 and Ersatz that I couldn't
make disappear.
Then, I noticed a pattern, that leaded to reversing the sign bit trick you
just explained in initSeed: n>=0? n*2 : -n*2+1;
One the one hand, Ersatz takes the lower 32 bits of the seed,
then returns them as a signed integer. But on the other hand,
pil32 takes the higher 32 bits as n (unsigned integer) and returns
n%2==0 ? n/2 : -(n-1)/2.
Correct ?
A question: why did you choose different implementations ?
Is it for a better efficiency in Ersatz ?

3) (rand T) behaves the same across pil32, Ersatz and EmuLisp.

Alex, if nobody in the mailing list is against modifying the rand of
Ersatz, may I humbly ask you to use >>>32 instead of >>>33 ?
This change in the official Ersatz will allow me to have reproducibility
across the implementations of PicoLisp I use without asking my users
to use an unofficial version of Ersatz.

Also, it would be nice, but much less important to me since I don't use
calls to rand with no args, to have the same behavior for (rand) with
pil32 and Ersatz.

chri

--

http://profgra.org/lycee/ (site pro)
http://delicious.com/profgraorg (liens, favoris)