Random numbers

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Random numbers

Antal-2
>
> It's not just that, but randseed is not a threadvar. This means that
> all your threads use the same randseed variable, so if two threads
> call "random" at the same time they will still get the same "random"
> number.
>
>
> Jonas
And also generating a rand * getpid you can't really get good random
numbers.
I just made a withdrawal program on this idea, so I've got several
repetitions, and upon executing a program again and agian I've got
false random numbers, like: a*n; a*(n+1); a*(n+2).
That's not a solution anyway.

Maybe a bit shifting or some aritmetical function can help to
obtain a more random "looking" number.

I'm trying my next random number generation to filter it with the sin()
function, so I can get a bit more entropy :)
(I can't use atmospheric noise as some suggested)
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Random numbers

Vinzent Höfler
On Friday 03 March 2006 11:06, Antal wrote:

> Maybe a bit shifting or some aritmetical function can help to
> obtain a more random "looking" number.

No. Don't do that:

|Random numbers should not be generated with a method chosen at random.
|       -- Donald E. Knuth

|The generation of random numbers is too important to be left to chance.
|        -- Robert R. Coveyou, Oak Ridge National Laboratory, 1969

The Mersenne Twister Free Pascal uses is one of the best PRNGs known
today, it just has to be used the right way. But calling it from
several threads and "randomly" overwriting its state array is
definitely not the right way to use it.


Vinzent.

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Random numbers

Graeme Geldenhuys-2
In reply to this post by Antal-2
Why not use GUID's (or the other name is UUID's) and convert them to a
Integer from Hex.   You might need to make the GUID value smaller, or
part of the GUID (example the last block).

Regards,
  - Graeme -



On 3/3/06, Antal <[hidden email]> wrote:

> >
> > It's not just that, but randseed is not a threadvar. This means that
> > all your threads use the same randseed variable, so if two threads
> > call "random" at the same time they will still get the same "random"
> > number.
> >
> >
> > Jonas
> And also generating a rand * getpid you can't really get good random
> numbers.
> I just made a withdrawal program on this idea, so I've got several
> repetitions, and upon executing a program again and agian I've got
> false random numbers, like: a*n; a*(n+1); a*(n+2).
> That's not a solution anyway.
>
> Maybe a bit shifting or some aritmetical function can help to
> obtain a more random "looking" number.
>
> I'm trying my next random number generation to filter it with the sin()
> function, so I can get a bit more entropy :)
> (I can't use atmospheric noise as some suggested)
> _______________________________________________
> fpc-pascal maillist  -  [hidden email]
> http://lists.freepascal.org/mailman/listinfo/fpc-pascal
>
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Random numbers

Michalis Kamburelis
In reply to this post by Antal-2
Antal wrote:

>>
>> It's not just that, but randseed is not a threadvar. This means that
>> all your threads use the same randseed variable, so if two threads
>> call "random" at the same time they will still get the same "random"
>> number.
>>
>>
>> Jonas
>
> And also generating a rand * getpid you can't really get good random
> numbers.
> I just made a withdrawal program on this idea, so I've got several
> repetitions, and upon executing a program again and agian I've got false
> random numbers, like: a*n; a*(n+1); a*(n+2).
> That's not a solution anyway.
>
> Maybe a bit shifting or some aritmetical function can help to obtain a
> more random "looking" number.
>

Like Vinzent pointed out, such tricks are not a really good solution. It
seems that most of the thread "Better random numbers ?" concentrated on
my trick with "RandSeed := RandSeed * getpid;". But this *was meant to
be* just a dirty hack, dirty idea, dirty workaround, whatever.

If you want a real, good solution, see the first part of my initial
response. Quoting myself:

"
The proper solution is to use some system-wide generator, that doesn't
have to be initialized every time you initialize your program. On Unix,
just read /dev/urandom, this should return pseudo-random numbers. On
Windows I guess that you will have to do something like that on your own
(e.g. write a program in FPC that runs as a service and can be queried
for random numbers). (Or you can use Cygwin routines to read Cygwin's
/dev/urandom --- never done it, but it should be possible).
"

In other words, don't waste too much time trying to improve the
"RandSeed := RandSeed * getpid;" trick.

Michalis
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Random numbers

Jeff Miller
In reply to this post by Vinzent Höfler
Quoting Vinzent Hoefler <[hidden email]>:

> The Mersenne Twister Free Pascal uses is one of the best PRNGs known
> today, it just has to be used the right way. But calling it from
> several threads and "randomly" overwriting its state array is
> definitely not the right way to use it.

Well said.

Maybe you could use a solution where you call the MT random number
generator K times for each time the program is run.  You "throw away"
the first K-1 random values, and return the K'th random value as the
random value for this run.  Now, for each run, you compute K as some function of
(say) the process id, the current time-based seed from randomize, etc.

With this strategy, you would still be picking points off of a good random
sequence (from MT), although you would take the random value from a rather
poorly-chosen random point in the sequence.

If you can afford the time involved in letting K vary over a large range
(relative to the number of times you will call the random number generator),
then intuitively I think this would give a pretty good random sequence
across runs.

Jeff Miller
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Random numbers

Antal-2
In reply to this post by Antal-2
> |Random numbers should not be generated with a method chosen at random.
> |       -- Donald E. Knuth
>
> |The generation of random numbers is too important to be left to chance.
> |        -- Robert R. Coveyou, Oak Ridge National Laboratory, 1969
>
> The Mersenne Twister Free Pascal uses is one of the best PRNGs known
> today, it just has to be used the right way. But calling it from
> several threads and "randomly" overwriting its state array is
> definitely not the right way to use it.
I'm disappointed, because I compiled the following program (on linux):
rnd.pp
begin
Randomize;
writeln(random(394));
end.

and I ran it for 11 times, and the results are rather strange:
310.
198
344
322*
322*
317-
317-
192
336.
382.
339.
(upon noting the dups I had to re-run again twice, getting:)
120
297.

so, I've got two times a repetition, though I only re-ran the program.
(noted with * and - )
Then I made a new series of random generating:

297.
120
310.
382.
336.
192
317
322
344
198
339.

I only have two problems with these random numbers:
Firstly, I can notice a repetition of some "random" numbers (noted with
".")
Then also 70% of them are 3xx
I learnt about random numbers, that they do not behave by this way.

Anyway, random numbers are behaving randomly, and we also had a big
scandal about the national lottery, when (using mechanical methods),
the occurence of "47" was too frequent in the last ten years,
and also last year we had around 50% without winners :) (which added
hundreds of thousands of EURO to the company manager's salary)

So I am really happy with FPC, but this was a bit strange for me.
So it wasn't running simultaneously, but just executing the binary file by
hand one after another.

I also agree with you Vincent, random numbers must be taken extremly
carefully. But they also have to care for us :)
Actually I can't recall (though I studied it 10 years ago) which functions
should increase the entropy.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Re: Random numbers

Jonas Maebe-2

On 6 mrt 2006, at 13:37, Antal wrote:

>> The Mersenne Twister Free Pascal uses is one of the best PRNGs known
>> today, it just has to be used the right way. But calling it from
>> several threads and "randomly" overwriting its state array is
>> definitely not the right way to use it.
> I'm disappointed, because I compiled the following program (on linux):
> rnd.pp
> begin
> Randomize;
> writeln(random(394));
> end.
>
> and I ran it for 11 times, and the results are rather strange:
> 310.
> 198
> 344
> 322*
> 322*
> 317-
> 317-
> 192
> 336.
> 382.
> 339.
> (upon noting the dups I had to re-run again twice, getting:)
> 120
> 297.

There is nothing strange about this. Randomize initialises randseed  
based on the system clock value expressed in seconds. So if you run  
it twice in the same second, you will get the same number.

> so, I've got two times a repetition, though I only re-ran the program.
> (noted with * and - )
> Then I made a new series of random generating:
>
> 297.
> 120
> 310.
> 382.
> 336.
> 192
> 317
> 322
> 344
> 198
> 339.
>
> I only have two problems with these random numbers:
> Firstly, I can notice a repetition of some "random" numbers (noted  
> with ".")
> Then also 70% of them are 3xx
> I learnt about random numbers, that they do not behave by this way.

You are not generating a series of random numbers based on the  
Mersenne Twister here, because you only generate one random number  
per program run. If you take all these values "together" as  
supposedly belonging to a "series of random numbers", then the result  
is that you are using a different "random" generator, where the next  
"random" number is generated based on the next clock/time value as  
opposed to the previously generated random number.

To test it properly, you should change your test program into this:

var
   i: longint;
begin
Randomize;
  for i := 1 to 20 do
   writeln(random(394));
end.

And then you have to compare the random numbers generated in one such  
a program run, not between different runs.


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Re: Random numbers

Jonas Maebe-2

On 6 mrt 2006, at 13:39, Jonas Maebe wrote:

> And then you have to compare the random numbers generated in one  
> such a program run, not between different runs.

And note that even then you may get two times the same number after  
each other. There is nothing wrong with that though, since if that  
couldn't happen, that would make the next number more and not less  
predictable (since then you would know in advance the next number  
will not be the same as the previous one).


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Re: Random numbers

Vinzent Höfler
In reply to this post by Antal-2
On Monday 06 March 2006 12:37, Antal wrote:

> > The Mersenne Twister Free Pascal uses is one of the best PRNGs
> > known today, it just has to be used the right way. But calling it
> > from several threads and "randomly" overwriting its state array is
> > definitely not the right way to use it.
>
> I'm disappointed, because I compiled the following program (on
> linux): rnd.pp
> begin
> Randomize;
> writeln(random(394));
> end.

Again: You are using a PRNG the wrong way, Jonas already pointed that
out.

Randomize is supposed to be called exactly once and then never again and
after then a (rather large) series of random number should be
generated. The way you use it, by reinitializing a PRNG before each
generation of a single random number, basically means all you get is
the "entropy" of the randomizer (the system clock) and not the one of
the PRNG. Well, last time I checked, the system clock is not exactly
random.


Vinzent.

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Re: Random numbers

Alain Michaud
In reply to this post by Jonas Maebe-2
Hi,

  I am not a mathematician myself, but I predict that unless you make
extensive tests over a very long period of time  you will never find any
corelations!



On Mon, 2006-03-06 at 13:39 +0100, Jonas Maebe wrote:

> On 6 mrt 2006, at 13:37, Antal wrote:
>
> >> The Mersenne Twister Free Pascal uses is one of the best PRNGs known
> >> today, it just has to be used the right way. But calling it from
> >> several threads and "randomly" overwriting its state array is
> >> definitely not the right way to use it.
> > I'm disappointed, because I compiled the following program (on linux):
> > rnd.pp
> > begin
> > Randomize;
> > writeln(random(394));
> > end.
> >
> > and I ran it for 11 times, and the results are rather strange:
> > 310.
> > 198
> > 344
> > 322*
> > 322*
> > 317-
> > 317-
> > 192
> > 336.
> > 382.
> > 339.
> > (upon noting the dups I had to re-run again twice, getting:)
> > 120
> > 297.
>
> There is nothing strange about this. Randomize initialises randseed  
> based on the system clock value expressed in seconds. So if you run  
> it twice in the same second, you will get the same number.
>
> > so, I've got two times a repetition, though I only re-ran the program.
> > (noted with * and - )
> > Then I made a new series of random generating:
> >
> > 297.
> > 120
> > 310.
> > 382.
> > 336.
> > 192
> > 317
> > 322
> > 344
> > 198
> > 339.
> >
> > I only have two problems with these random numbers:
> > Firstly, I can notice a repetition of some "random" numbers (noted  
> > with ".")
> > Then also 70% of them are 3xx
> > I learnt about random numbers, that they do not behave by this way.
>
> You are not generating a series of random numbers based on the  
> Mersenne Twister here, because you only generate one random number  
> per program run. If you take all these values "together" as  
> supposedly belonging to a "series of random numbers", then the result  
> is that you are using a different "random" generator, where the next  
> "random" number is generated based on the next clock/time value as  
> opposed to the previously generated random number.
>
> To test it properly, you should change your test program into this:
>
> var
>    i: longint;
> begin
> Randomize;
>   for i := 1 to 20 do
>    writeln(random(394));
> end.
>
> And then you have to compare the random numbers generated in one such  
> a program run, not between different runs.
>
>
> Jonas
> _______________________________________________
> fpc-pascal maillist  -  [hidden email]
> http://lists.freepascal.org/mailman/listinfo/fpc-pascal

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Random numbers

Michalis Kamburelis-2
In reply to this post by Antal-2
(Second send, it seems that mails from my old email address do not reach
fpc lists)

Antal wrote:

>>
>> It's not just that, but randseed is not a threadvar. This means that
>> all your threads use the same randseed variable, so if two threads
>> call "random" at the same time they will still get the same "random"
>> number.
>>
>>
>> Jonas
>
> And also generating a rand * getpid you can't really get good random
> numbers.
> I just made a withdrawal program on this idea, so I've got several
> repetitions, and upon executing a program again and agian I've got false
> random numbers, like: a*n; a*(n+1); a*(n+2).
> That's not a solution anyway.
>
> Maybe a bit shifting or some aritmetical function can help to obtain a
> more random "looking" number.
>

Like Vinzent pointed out, such tricks are not a really good solution. It
seems that most of the thread "Better random numbers ?" concentrated on
my trick with "RandSeed := RandSeed * getpid;". But this *was meant to
be* just a dirty hack, dirty idea, dirty workaround, whatever.

If you want a real, good solution, see the first part of my initial
response. Quoting myself:

"
The proper solution is to use some system-wide generator, that doesn't
have to be initialized every time you initialize your program. On Unix,
just read /dev/urandom, this should return pseudo-random numbers. On
Windows I guess that you will have to do something like that on your own
(e.g. write a program in FPC that runs as a service and can be queried
for random numbers). (Or you can use Cygwin routines to read Cygwin's
/dev/urandom --- never done it, but it should be possible).
"

In other words, don't waste too much time trying to improve the
"RandSeed := RandSeed * getpid;" trick.

Michalis
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: random numbers

Antal-2
In reply to this post by Antal-2
> There is nothing strange about this. Randomize initialises randseed
> based on the system clock value expressed in seconds. So if you run
> it twice in the same second, you will get the same number.
>
> You are not generating a series of random numbers based on the
> Mersenne Twister here, because you only generate one random number
> per program run. If you take all these values "together" as
> supposedly belonging to a "series of random numbers", then the result
> is that you are using a different "random" generator, where the next
> "random" number is generated based on the next clock/time value as
> opposed to the previously generated random number.
>
> To test it properly, you should change your test program into this:
>
> var
>   i: longint;
> begin
> Randomize;
>  for i := 1 to 20 do
>   writeln(random(394));
> end.
>
> And then you have to compare the random numbers generated in one such
> a program run, not between different runs.
>
>
> Jonas
I also noticed this kind of behavior before, so that program was
speccially made to track down the problem.
I know fully understand the behavior of the Randomize, so I might suggest
you to initialise the randseed not based on seconds, but, preferrably on
milliseconds, which renders a better approach of randomizing.
I suppose it's not too complicated, but it can make hings better.
As I noticed, when initialized the randseed with the same value, the whole
rand values in the chain will be totally identical, which I'm afraid is
rather far from what we might expect from a "real" random number
generator!

Thanks,
Antal
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Re: random numbers

Vincent Snijders
Antal wrote:
> As I noticed, when initialized the randseed with the same value, the
> whole rand values in the chain will be totally identical, which I'm
> afraid is rather far from what we might expect from a "real" random
> number generator!

Indeed, it isn't a real random number generator and in fact this is a
good thing, otherwise you wouldn't be able to reproduce any behaviour
with a Pseudo RNG. The fact it is Pseudo is advantageous in some cases.

Vincent
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Re: random numbers

Jonas Maebe-2

On 9 mrt 2006, at 18:38, Vincent Snijders wrote:

>> As I noticed, when initialized the randseed with the same value,  
>> the whole rand values in the chain will be totally identical,  
>> which I'm afraid is rather far from what we might expect from a  
>> "real" random number generator!
>
> Indeed, it isn't a real random number generator and in fact this is  
> a good thing, otherwise you wouldn't be able to reproduce any  
> behaviour with a Pseudo RNG. The fact it is Pseudo is advantageous  
> in some cases.

And this behaviour is indeed what many people expect, since it's  
exactly the same in TP and Delphi (and in C).


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Re: random numbers

Vinzent Höfler
On Thursday 09 March 2006 17:47, Jonas Maebe wrote:
> On 9 mrt 2006, at 18:38, Vincent Snijders wrote:
> >
> > Indeed, it isn't a real random number generator and in fact this is
> > a good thing, otherwise you wouldn't be able to reproduce any
> > behaviour with a Pseudo RNG. The fact it is Pseudo is advantageous
> > in some cases.
>
> And this behaviour is indeed what many people expect,

Even _require_.

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal