Home > Archive > PERL Modules > July 2004 > math::trulyrandom
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Daniel Miller 2004-06-25, 6:39 pm |
| Hello,
I'm still trying to figure out modules. I need to get 10,000 random numbers
between 1 and 5936277172. I've been using the rand function but it seems
that the significant digits aren't large enough to account for these large
numbers so if I ask for say 1000 random numbers in this range I get 10
duplicates! The number of duplicates goes up exponentially as I generate
more randoms. Anyway, I'd like to use Math::trulyrandom to generate true
random numbers in this range but I need some help with the syntax. Can
someone give me a short snippet of code to show how I would generate a
random number using this module?
Thanks
Dan Miller
| |
| Rusty Phillips 2004-06-25, 6:40 pm |
| The author included an example in his CPAN package, though it
doesn't look like the example will run. :)
Still, it looks like it'll show you how it works.
To get a value, just type
truly_random_value()
That's all it does.
http://search.cpan.org/src/GARY/Math-TrulyRandom-1.0/examples/example_1.pl
| |
| Sisyphus 2004-06-25, 6:40 pm |
| Daniel Miller wrote:
> Hello,
>
> I'm still trying to figure out modules. I need to get 10,000 random numbers
> between 1 and 5936277172. I've been using the rand function but it seems
> that the significant digits aren't large enough to account for these large
> numbers so if I ask for say 1000 random numbers in this range I get 10
> duplicates! The number of duplicates goes up exponentially as I generate
> more randoms. Anyway, I'd like to use Math::trulyrandom to generate true
> random numbers in this range but I need some help with the syntax. Can
> someone give me a short snippet of code to show how I would generate a
> random number using this module?
>
This module doesn't work for me, and hasn't been updated for over 8
years. I think you would be better advised to use one of the "quality"
random number generator modules on cpan - say Crypt::Random.
'perl -V:randbits' will tell you how many random bits rand() produces.
You'll probably find that you're getting only 15 random bits (even
though '5936277172' is a 31 bit number) and that's why you find an
unexpectedly high number of duplicates.
Just for the fun of it, here's a script that produces 1000 random
numbers in the required range (without duplicates) using only perl's
rand function. It does this by selecting 31 random bits at each iteration.
-------------------------------------
use warnings;
use strict;
my @r;
my $reps = 1000;
my $max = 5936277172;
# Fill @r with $reps random uniform numbers less than $max
for(1..$reps) {push @r, create_rand($max)}
# Find out how many duplicates @r contains
print count_dup(\@r), "\n";
sub create_rand {
my $iterations = length(sprintf("%b", $_[0]));
my $ret = '';
for(1..$iterations) {$ret .= int(rand(2))}
$ret = oct("0b$ret");
$ret = int($ret / (2 ** $iterations) * $_[0]);
return $ret;
}
sub count_dup {
my $ret = 0;
for(my $i = 0; $i < @{$_[0]}; $i++) {
for(my $j = $i + 1; $j < @{$_[0]}; $j++) {
if(${$_[0]}[$i] == ${$_[0]}[$j]) {$ret++}
}
}
return $ret;
}
__END__
-------------------------------------------
Cheers,
Rob
--
To reply by email u have to take out the u in kalinaubears.
| |
| Dan Miller 2004-06-25, 6:40 pm |
| Thanks so much for your thoughts and time on this. I had a hunch that this
was a problem with the number of bits rand was using to generate numbers but
lacked the programming skills to solve it. perl -V:randbits gives me 15 bits
as you suspected.
When I run your program to generate 10,000 random numbers I still get no
duplicates. The distribution seems fairly even over the range. (BTW the
number 5936277172 is the number of DNA basepairs in a diploid human genome)
Do you forsee any problem with this?
I really appreciate your help!
Dan
"Sisyphus" <kalinaubears@iinet.net.au> wrote in message
news:40da8619$0$10997$5a62ac22@per-qv1-newsreader-01.iinet.net.au...
> Daniel Miller wrote:
numbers[color=darkred]
large[color=darkred]
>
> This module doesn't work for me, and hasn't been updated for over 8
> years. I think you would be better advised to use one of the "quality"
> random number generator modules on cpan - say Crypt::Random.
>
> 'perl -V:randbits' will tell you how many random bits rand() produces.
> You'll probably find that you're getting only 15 random bits (even
> though '5936277172' is a 31 bit number) and that's why you find an
> unexpectedly high number of duplicates.
>
> Just for the fun of it, here's a script that produces 1000 random
> numbers in the required range (without duplicates) using only perl's
> rand function. It does this by selecting 31 random bits at each iteration.
>
> -------------------------------------
> use warnings;
> use strict;
>
> my @r;
> my $reps = 1000;
> my $max = 5936277172;
>
> # Fill @r with $reps random uniform numbers less than $max
> for(1..$reps) {push @r, create_rand($max)}
>
> # Find out how many duplicates @r contains
> print count_dup(\@r), "\n";
>
> sub create_rand {
> my $iterations = length(sprintf("%b", $_[0]));
> my $ret = '';
> for(1..$iterations) {$ret .= int(rand(2))}
> $ret = oct("0b$ret");
> $ret = int($ret / (2 ** $iterations) * $_[0]);
> return $ret;
> }
>
> sub count_dup {
> my $ret = 0;
> for(my $i = 0; $i < @{$_[0]}; $i++) {
> for(my $j = $i + 1; $j < @{$_[0]}; $j++) {
> if(${$_[0]}[$i] == ${$_[0]}[$j]) {$ret++}
> }
> }
> return $ret;
> }
>
> __END__
> -------------------------------------------
>
> Cheers,
> Rob
>
>
> --
> To reply by email u have to take out the u in kalinaubears.
>
| |
| Sisyphus 2004-06-25, 6:40 pm |
| Dan Miller wrote:
> Thanks so much for your thoughts and time on this. I had a hunch that this
> was a problem with the number of bits rand was using to generate numbers but
> lacked the programming skills to solve it. perl -V:randbits gives me 15 bits
> as you suspected.
You can access the value in a program with:
use Config;
my $random_bits = $Config{randbits};
> When I run your program to generate 10,000 random numbers I still get no
> duplicates.
By my calculations the chance of getting one or more duplicates for
10,000 selections (assuming there's no problem with random number
generator) is about 8 in 1000.
The program I used for the calculation:
use warnings;
use strict;
my $reps = 10000;
my $vals = 5936277172;
print probability_of_at_least_one_duplicate($r
eps, $vals);
sub probability_of_at_least_one_duplicate {
# Stolen from "Mastering Algorithms with Perl"
# ("The Birthday Conundrum", page 570)
my $p = 1;
my $t = $_[1] + 1;
for(my $i = 1; $i < $_[0]; $i++) {
$p *= ($t - $i) / $_[1];
}
return 1 - $p;
}
__END__
Change $reps to 1000 and $vals to 32768 (which was the value it had when
you ran your original program) and you'll see that duplicates are not
unexpected :-)
> The distribution seems fairly even over the range. (BTW the
> number 5936277172 is the number of DNA basepairs in a diploid human genome)
> Do you forsee any problem with this?
>
Do I foresee a problem with that number of basepairs ? If 5936277172 is
the number God chose then it's good enough for me (though, personally, I
would have recommended a power of 2, if I had been asked ;-)
With the method I presented, most numbers in the range 0..5936277171
will have a 1 in 2**31 chance of being selected, but some numbers in
that range have a 1 in 2**30 chance of being selected. (Since there's
2**31 possible inputs and only 5936277172 possible outputs it stands to
reason that there must be some occasional "doubling up".) If that
matters then it's a problem, and you would have to devise another way.
Cheers,
Rob
--
To reply by email u have to take out the u in kalinaubears.
| |
| Sisyphus 2004-06-25, 8:08 pm |
| Sisyphus wrote:
> If that
> matters then it's a problem, and you would have to devise another way.
>
Maybe just select random 31 bit integers by doing 'int(rand(2))' 31
times. If the resulting number is less than 5936277172, accept it.
Otherwise reject it and make another selection.
Cheers,
Rob
--
To reply by email u have to take out the u in kalinaubears.
| |
|
| Sisyphus wrote:
> Daniel Miller wrote:
>
>
> This module doesn't work for me, and hasn't been updated for over 8
> years. I think you would be better advised to use one of the "quality"
> random number generator modules on cpan - say Crypt::Random.
>
> 'perl -V:randbits' will tell you how many random bits rand() produces.
> You'll probably find that you're getting only 15 random bits (even
> though '5936277172' is a 31 bit number) and that's why you find an
> unexpectedly high number of duplicates.
>
> Just for the fun of it, here's a script that produces 1000 random
> numbers in the required range (without duplicates) using only perl's
> rand function. It does this by selecting 31 random bits at each iteration.
>
> -------------------------------------
> use warnings;
> use strict;
>
> my @r;
> my $reps = 1000;
> my $max = 5936277172;
>
> # Fill @r with $reps random uniform numbers less than $max
> for(1..$reps) {push @r, create_rand($max)}
>
> # Find out how many duplicates @r contains
> print count_dup(\@r), "\n";
>
> sub create_rand {
> my $iterations = length(sprintf("%b", $_[0]));
> my $ret = '';
> for(1..$iterations) {$ret .= int(rand(2))}
> $ret = oct("0b$ret");
> $ret = int($ret / (2 ** $iterations) * $_[0]);
> return $ret;
> }
>
> sub count_dup {
> my $ret = 0;
> for(my $i = 0; $i < @{$_[0]}; $i++) {
> for(my $j = $i + 1; $j < @{$_[0]}; $j++) {
> if(${$_[0]}[$i] == ${$_[0]}[$j]) {$ret++}
> }
> }
> return $ret;
> }
Here is a *much* faster (and more accurate) way of finding the duplicates:
sub count_dup {
my %dupes;
my $ret = 0;
for (@{$_[0]}) {
$ret++ if $dupes{$_}++;
}
return $ret;
}
Dave
>
> __END__
> -------------------------------------------
>
> Cheers,
> Rob
>
>
| |
| Sisyphus 2004-07-26, 3:56 am |
| Dave wrote:
>
> Here is a *much* faster (and more accurate) way of finding the duplicates:
>
> sub count_dup {
> my %dupes;
> my $ret = 0;
> for (@{$_[0]}) {
> $ret++ if $dupes{$_}++;
> }
> return $ret;
> }
>
Good point(s), though I find it's twice as fast again if I use "@dupes"
instead of "%dupes":
sub count_dup {
my @dupes;
my $ret = 0;
for (@{$_[0]}) {
$ret++ if $dupes[$_]++;
}
return $ret;
}
Cheers,
Rob
--
To reply by email u have to take out the u in kalinaubears.
| |
|
| Sisyphus wrote:
> Dave wrote:
>
>
> Good point(s), though I find it's twice as fast again if I use "@dupes"
> instead of "%dupes":
>
> sub count_dup {
> my @dupes;
> my $ret = 0;
> for (@{$_[0]}) {
> $ret++ if $dupes[$_]++;
> }
> return $ret;
> }
Twice as fast in what way? Crashing Perl before the subroutine has time
to complete doesn't count. :-)
Seriously though, array subscripts are *not* interchangeable with hash
keys! Consider the difference between $hash{5936277172}++ and
$array[5936277172]++. The former increments the value of a single hash
key by one. The latter will attempt to presize an array to accommodate
5936277173 elements before incrementing the array index 5936277172 by
one, in which case Perl will produce the following error message:
"Modification of non-creatable array value attempted . . . ."
Dave
> Cheers,
> Rob
>
|
|
|
|
|