Randomness of the random library

Help requests on developing Logtalk applications

Moderator: Paulo Moura

Post Reply
Parker
Posts: 33
Joined: Wed Feb 27, 2008 2:51 pm

Randomness of the random library

Post by Parker » Mon Jun 30, 2008 3:05 pm

I have been using the predicate random::randset/4 to choose elements from a list at random. However, it has caught my attention that the results are not very random. Perhaps it is just the way I am seeding - could someone suggest a good way of seeding the PRNG?

Note how the first random number after seeding is rather predictable and unvarying. Is this to be expected?

Code: Select all

?- random::set_seed(1),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(2),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(3),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(4),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(5),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(6),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(7),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(8),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(9),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(10),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(1000),random::randset(1,0,10,Index).
Index = [0].

?- random::set_seed(2500),random::randset(1,0,10,Index).
Index = [2].

?- random::set_seed(3900),random::randset(1,0,10,Index).
Index = [3].

?- random::set_seed(4613),random::randset(1,0,10,Index).
Index = [4].

?- random::set_seed(5189),random::randset(1,0,10,Index).
Index = [5].

?- random::set_seed(6898),random::randset(1,0,10,Index).
Index = [6].

?- random::set_seed(6899),random::randset(1,0,10,Index).
Index = [6].

?- random::set_seed(6900),random::randset(1,0,10,Index).
Index = [6].

?- random::set_seed(6901),random::randset(1,0,10,Index).
Index = [6].

?- random::set_seed(6902),random::randset(1,0,10,Index).
Index = [6].
Cheers,
Parker
Platform: Logtalk 2.31.6, SWI 5.6.54, ubuntu linux 8.04 on 32-bit i386

Paulo Moura
Logtalk developer
Posts: 475
Joined: Sat May 05, 2007 8:35 am
Location: Portugal
Contact:

Re: Randomness of the random library

Post by Paulo Moura » Mon Jun 30, 2008 3:38 pm

Parker wrote:I have been using the predicate random::randset/4 to choose elements from a list at random. However, it has caught my attention that the results are not very random. Perhaps it is just the way I am seeding - could someone suggest a good way of seeding the PRNG?
The basic idea is to use as a seed a value that is not repeatable or that is not easily repeated such as the current cpu time or the current date. For example, using SWI-Prolog:

Code: Select all

   ?- Seed is truncate(cputime*1000000), random::randset(5,0,10,Index).
Index = [3,4,6,8,9],
Seed = 582000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(5,0,10,Index).
Index = [0,2,5,6,9],
Seed = 584000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(5,0,10,Index).
Index = [0,3,4,5,9],
Seed = 586000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(5,0,10,Index).
Index = [1,4,5,7,9],
Seed = 588000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(5,0,10,Index).
Index = [1,4,6,8,9],
Seed = 589000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(1,0,10,Index).
Index = [0],
Seed = 593000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(1,0,10,Index).
Index = [8],
Seed = 595000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(1,0,10,Index).
Index = [9],
Seed = 597000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(1,0,10,Index).
Index = [6],
Seed = 599000 ? 
yes
   ?- Seed is truncate(cputime*1000000), random::randset(1,0,10,Index).
Index = [9],
Seed = 601000 ? 
yes
Cheers,

Paulo
Paulo Moura
Logtalk developer

Parker
Posts: 33
Joined: Wed Feb 27, 2008 2:51 pm

Re: Randomness of the random library

Post by Parker » Mon Jun 30, 2008 5:20 pm

Paulo Moura wrote:
Parker wrote:I have been using the predicate random::randset/4 to choose elements from a list at random. However, it has caught my attention that the results are not very random. Perhaps it is just the way I am seeding - could someone suggest a good way of seeding the PRNG?
The basic idea is to use as a seed a value that is not repeatable or that is not easily repeated such as the current cpu time or the current date. For example, using SWI-Prolog:
I encountered the problem while using

Code: Select all

time::now(_Hours,_Mins,Secs),random::set_seed(Secs),
Obviously this wasn't a wide enough range.

It would be helpful if the possible range of values that set_seed/1 can take were made explicit. In case it varies for different Prolog back-ends then something like [-max_int,+max_int]

Cheers,
Parker

Paulo Moura
Logtalk developer
Posts: 475
Joined: Sat May 05, 2007 8:35 am
Location: Portugal
Contact:

Re: Randomness of the random library

Post by Paulo Moura » Tue Jul 01, 2008 3:32 pm

Parker wrote: It would be helpful if the possible range of values that set_seed/1 can take were made explicit. In case it varies for different Prolog back-ends then something like [-max_int,+max_int]
Take a look to the implementation of the set_seed/1 predicate. The predicate argument (seed) is used to calculate three integers using mod/2 operations. The random generator algorithm implemented by the library object "random" is, I believe, used widely. It's possible that background information on the algorithm exists that could help answer your question but I don't have any reference handy.

Cheers,

Paulo
Paulo Moura
Logtalk developer

Parker
Posts: 33
Joined: Wed Feb 27, 2008 2:51 pm

Re: Randomness of the random library

Post by Parker » Tue Jul 01, 2008 4:26 pm

Thanks for the reply Paulo.

If the code is based on the algorithm found in SWI prolog library/random.pl originally implemented by Richard O'Keefe, then it says:

Code: Select all

%       Query/set the state of the  random  library.   A,  B  and  C are
%       integers in the range 1..30,000.

Paulo Moura
Logtalk developer
Posts: 475
Joined: Sat May 05, 2007 8:35 am
Location: Portugal
Contact:

Re: Randomness of the random library

Post by Paulo Moura » Tue Jul 01, 2008 4:43 pm

Hi!

I've a copy of the Edinburgh Prolog library, which contains what is probably the original implementation of the algorithm. It does not contain the text you cite above. Nevertheless, looking at the mod/2 operations, the idea would be to always reset the internal seed, represented by three integers, such that each integer is a natural number less than the second argument of the corresponding mod/2 operation.

Cheers,

Paulo
Paulo Moura
Logtalk developer

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest