Discussion about Double versus Long for random generator in Gama ? #2025

Closed
reyman opened this Issue Oct 15, 2016 · 6 comments

Projects

None yet

4 participants

@reyman
Contributor
reyman commented Oct 15, 2016 edited

Hi,

I'm surprised by the fact that Gama use/accept a Double and not a Long to generate/initialize seed for Random.

'nextDouble()' return a number between 0.0 and 1.0 The plage of value is not so important and we can have problems of precision (colision between seed generated). Why not using Long type ?

I add Romain Reuillon in copy of this issue, because it's a specialist of this question.

@romainreuillon
Contributor
romainreuillon commented Oct 15, 2016 edited

Modern pseudo-random number generators (Mersene Twister, WELL...) operate on bitwise operations (for instance XOR). They have a huge state way longer than a single long value. Therefore the "seed" value is use to initialise a "poor quality" random number generator that is used to initialise the state of the one that will be used for the simulation. The important thing is to be sure that the PRNG used for initialisation is initialised with distinct set of values bitwise. The best way to do that is to generate seeds incrementally (if you draw them at random you're are hit by the birthday paradox which make it not that unlikely that you will generate twice the same seed, for a small amount of seed and 64 bits seed this is probably negligible though). Using double and then rounding them to long is problematic cause:

  • you don't know for sure that 2 distinct double will produce 2 distinct seeds because of the rounding operation,
  • double as no usable max value if you want to draw the seed at random,
  • a part of the info in the double value is erased by the rounding operation making the seed generation way more vulnerable to the birthday paradox when generating seed at random.

To avoid the user producing erroneous simulation results I think that the seed should be specified as a long value.

@AlexisDrogoul
Member

I think we already had a similar discussion, but can't find it. Long and Double are both coded on 64bits and this number is never rounded AFAIK in the RNG. So whether you consider these 64 bits to represent a Long or a Double is not really important, as Double.doubleToLongBits (and the reverse) are used to extract the bits.

So neither of the problems mentioned above are relevant in my opinion. And I quite dont understand the 'nextDouble()' problem. The random seed is not generated using this, is it ?

What you can do is to use Double.longToDoubleBits when you pass long values from OpenMole (instead of rounding it, which I hope you dont do !)

@ptaillandier
Contributor

Hi,

As a side note, I do not know if it is the normal behavior or not of the
default random number generator of GAMA, but this one one seems to have
some problems with "small" seed. See the following model:

model testrnd

global {

init {

write "******* SEED 1 *********";

seed <- 1.0;

loop times: 3 {

write string(seed) + "->" + rnd(100);

}

write "******* SEED 10 ^-50 *********";

seed <- 10 ^ (-50);

loop times: 3 {

write string(seed) + "->" + rnd(100);

}

write "******* SEED 1.1 * 10 ^-50 *********";

seed <- 1.1 * 10 ^ (-50);

loop times: 3 {

write string(seed) + "->" + rnd(100);

}

}

}

experiment main type: gui;

Results:

******* SEED 1 *********

1.0->40

1.0->93

1.0->74

******* SEED 10 ^-50 *********

1.0E-50->43

1.0E-50->24

1.0E-50->13

******* SEED 1.1 * 10 ^-50 *********

1.1000000000000002E-50->43

1.1000000000000002E-50->24

1.1000000000000002E-50->13

2016-10-15 17:35 GMT+02:00 Alexis Drogoul notifications@github.com:

I think we already had a similar discussion, but can't find it. Long and
Double are both coded on 64bits and this number is never rounded AFAIK in
the RNG. So whether you consider these 64 bits to represent a Long or a
Double is not really important, as Double.doubleToLongBits (and the
reverse) are used to extract the bits.

So neither of the problems mentioned above are relevant in my opinion. And
I quite dont understand the 'nextDouble()' problem. The random seed is not
generated using this, is it ?

What you can do is to use Double.longToDoubleBits when you pass long
values from OpenMole (instead of rounding it, which I hope you dont do !)


You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#2025 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABb7HYQAF45Go3LbM9pK_UUljJegHrMJks5q0PK-gaJpZM4KXqoe
.

@reyman
Contributor
reyman commented Oct 15, 2016 edited

@AlexisDrogoul We say that because we revert some code in Gama to use Double and not Long.

Original behavior :
OpenMole generate a Long -> Gama Task take a Long -> Gama Headless convert to Double

We found that conversion produce collision (Different Long value produce same Double value). So we revert the code with patrick : 08d7767

This code

And now we use :
OpenMole generate a Double -> Gama Task take a Double -> Gama Headless use a Double

But discussion with @romainreuillon about Long versus Double convince me to post this issue to discuss.

@AlexisDrogoul
Member
AlexisDrogoul commented Oct 15, 2016 edited

OK. I've taken a look and it seems everything comes down to a single line in the RandomUtils class, where I found this horrible long l = realSeed.longValue(); line in createSeed... I dont remember where this one comes from, but it is a conversion (the thing I was warning against !) and not a bitwise translation.

When I declare some flag (i.e. static boolean USE_BITWISE = true;) and use it to write:

        long l;
        if (!USE_BITWISE)
            l = realSeed.longValue();
        else
            l = Double.doubleToRawLongBits(realSeed);

to replace this line, the problem mentioned by Patrick vanishes. I get:

******* SEED 1 *********
1.0->78
1.0->79
1.0->51
******* SEED 10 ^-50 *********
1.0E-50->20
1.0E-50->72
1.0E-50->54
******* SEED 1.1 * 10 ^-50 *********
1.1000000000000002E-50->0
1.1000000000000002E-50->44
1.1000000000000002E-50->88

I think the collision problems mentioned above came from this line. I dont know, however, if I should commit it or not, as it will change the 'default' behavior of many models (it is not a bad thing if the seed computation is more consistant, but it may come as a 'surprise' for some users).

@ptaillandier
Contributor

Hi,

For me, it is better to commit the fix: users that want to exactly
reproduce the same behavior as before can still use old versions of
GAMA.... and for new users, the results obtained will be more consistent
(and avoid bad surprises like the ones we had when we got the same results
for 50 runs over 100 whereas the seeds were supposed to be different for
the 100 runs).

Cheers,

Patrick

2016-10-15 22:47 GMT+02:00 Alexis Drogoul notifications@github.com:

OK. I've taken a look and it seems everything comes down to a single line
in the RandomUtils class, where I found this horrible long l =
realSeed.longValue(); line in createSeed... I dont remember where this
one comes from, but it is a conversion (the thing I was warning against !)
and not a bitwise translation.

When I declare some flag (i.e. static boolean USE_BITWISE = true;) and
use it to write:

``
long l;
if (!USE_BITWISE)
l = realSeed.longValue();
else
l = Double.doubleToRawLongBits(realSeed);

to replace this line, the problem mentioned by Patrick vanishes. I get:

******* SEED 1 *********
1.0->78
1.0->79
1.0->51
******* SEED 10 ^-50 *********
1.0E-50->20
1.0E-50->72
1.0E-50->54
******* SEED 1.1 * 10 ^-50 *********
1.1000000000000002E-50->0
1.1000000000000002E-50->44
1.1000000000000002E-50->88

I think the collision problems mentioned above came from this line. I dont know, however, if I should commit it or not, as it will change the 'default' behavior of many models (it is not a bad thing if the seed computation is more consistant, but it may come as a 'surprise' for some users).


You are receiving this because you commented.
Reply to this email directly, view it on GitHub
#2025 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ABb7Ha5jQ6KjQFWDJ5fAOFhtGj_S7Ke-ks5q0TvrgaJpZM4KXqoe
.

@AlexisDrogoul AlexisDrogoul added a commit that closed this issue Oct 16, 2016
@AlexisDrogoul AlexisDrogoul Fixes #2025. Fixes #738.
Generalization of the 'parallel:' facet to grid, species, ask and
experiment. Chnages in the API of IScope for supporting parallel
operations. Changes in QuadTree and GamaGraph for solving sync problems.
Changes in the step method of agents (now divided in 3 sub-methods:
preStep(), doStep(), postStep()). Addition of the
msi.gama.runtime.concurrent package and several classes dedicated to
concurrent runs.

Signed-off-by: AlexisDrogoul <alexis.drogoul@gmail.com>
683d6c4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment