* Random Number Generator Problem
@ 2003-07-25 14:34 Brien
2003-07-25 15:34 ` Robert I. Eachus
2003-07-25 17:06 ` Anisimkov
0 siblings, 2 replies; 5+ messages in thread
From: Brien @ 2003-07-25 14:34 UTC (permalink / raw)
Preface: I'm using GNAT on a windows box.
I'm generating a series of unsigned 64 bit integers and I get the same
value for about half of the results. The ada built-in random number
generator seems to be giving me 2**63 much more often than any other
number. I can't figure out why this would be. Here is some sample
code to demonstrate my problem.
with Interfaces;
with Ada.Numerics.Discrete_Random;
with Ada.Text_Io;
use Ada.Text_Io;
procedure Generate_Random_Test is
type Unsigned_Dbl_Integer is new Interfaces.Unsigned_64;
package Rand is new
Ada.Numerics.Discrete_Random(Unsigned_Dbl_Integer);
Rand_Gen : Rand.Generator;
begin
for I in 1..1000 loop
Put_Line(Unsigned_Dbl_Integer'Image(Rand.Random(Rand_Gen)));
end loop;
end Generate_Random_Test;
When I run this code, i get 9,233,........,808 (which is 2**63) as
about half of my results.
Thanks for the help!
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Random Number Generator Problem
2003-07-25 14:34 Random Number Generator Problem Brien
@ 2003-07-25 15:34 ` Robert I. Eachus
2003-07-28 13:14 ` Brien
2003-07-25 17:06 ` Anisimkov
1 sibling, 1 reply; 5+ messages in thread
From: Robert I. Eachus @ 2003-07-25 15:34 UTC (permalink / raw)
Brien wrote:
> When I run this code, i get 9,233,........,808 (which is 2**63) as
> about half of my results.
There are two problems here. The first, which you should definitely
report to ACT, is that the code for the discrete generator uses
(long_)integers. Obviously 2**64 > 2**63, so there is a problem here.
The fix is that when generating values of this type, the bounds should
be Long_Integer'First and Long_Integer'Last, not 0 and Max_Binary_Modulus.
There is a line in the algorithm which folds out of range values into
the largest possible value. For normal ranges, this line preserves the
unbiased nature of the results. But in this case, half the results
(generated as Long_Floats) will be out of range for the (intermediate)
Long_Integer type.
The second problem is that you may be trying to accomplish something
that the Ada RM does not promise. The algorithm as written will
generate many more than 2**32 values. (About 2**50 but I'd have to dig
out my documentation to get the exact number of possible values.) If
you really need the possibility of 2**64 unbiased values, there are few,
if any, RNGs outside of cryptography that will do what you want.
The GNAT generator IS a cryptographic generator with a few cheats to
make it highly efficient--but not useful for cryptographic purposes. I
just haven't gotten around to generating a version of the algorithm that
will provide 2**64 unbiased values. If you haven't guessed, this will
take several days of CPU time (in the background on this machine is
fine) to find the necessary constants, plus modifications to the
generator code.
So, how many values do you really need? And are there other
characteristics that you need? It is probably the case that I can give
you some code that takes twice as long as the GNAT generator and does
what you need. (Notice though that it will take years to generate all
of the possible values for the current generator, even on today's
fastest CPUs. So I thought I had a few years before this issue became
urgent.)
--
Robert I. Eachus
�In an ally, considerations of house, clan, planet, race are
insignificant beside two prime questions, which are: 1. Can he shoot? 2.
Will he aim at your enemy?� -- from the Laiden novels by Sharon Lee and
Steve Miller.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Random Number Generator Problem
2003-07-25 14:34 Random Number Generator Problem Brien
2003-07-25 15:34 ` Robert I. Eachus
@ 2003-07-25 17:06 ` Anisimkov
2003-07-25 18:05 ` Robert I. Eachus
1 sibling, 1 reply; 5+ messages in thread
From: Anisimkov @ 2003-07-25 17:06 UTC (permalink / raw)
> I'm generating a series of unsigned 64 bit integers and I get the same
> value for about half of the results.
I was reporting this bug to ACT.
Do not use mod 2**64 types in random generator untill this bug would be
fixed.
Use mod 2**63 or multiplication of two random numbers of mod 2**32.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Random Number Generator Problem
2003-07-25 17:06 ` Anisimkov
@ 2003-07-25 18:05 ` Robert I. Eachus
0 siblings, 0 replies; 5+ messages in thread
From: Robert I. Eachus @ 2003-07-25 18:05 UTC (permalink / raw)
Anisimkov wrote:
>> I'm generating a series of unsigned 64 bit integers and I get the
>> same value for about half of the results.
>
>
> I was reporting this bug to ACT.
>
> Do not use mod 2**64 types in random generator untill this bug would
> be fixed. Use mod 2**63 or multiplication of two random numbers of
> mod 2**32.
I assume you mean Rand * 2**32 + Rand, where Rand'Modulus = 2**64 and
the range of the subtype used to instantiate the generator is any power
of two from 32 to 63.
If you use Rand * Rand, the distribution is not Uniform. (This can
easily be seen. The mean of Rand * Rand is 2**62, not 2**63.)
However there is another problem worth noting. If both random values
come from the same generator, the period of the combined generator will
be half the period of the full generator. This is still going to be
about 2**49 with GNAT, so it is not likely to be a big issue yet. ;-)
But as I said, I do have it on my to do list to create a generator for
types with a range of > 2**48 that has a period greater than 2**64.
--
Robert I. Eachus
�In an ally, considerations of house, clan, planet, race are
insignificant beside two prime questions, which are: 1. Can he shoot? 2.
Will he aim at your enemy?� -- from the Laiden novels by Sharon Lee and
Steve Miller.
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Random Number Generator Problem
2003-07-25 15:34 ` Robert I. Eachus
@ 2003-07-28 13:14 ` Brien
0 siblings, 0 replies; 5+ messages in thread
From: Brien @ 2003-07-28 13:14 UTC (permalink / raw)
Thanks for the response!
I am only using this to generate some test data, so I don't need
anything near a completely uniform distribution. Multiplying two 32
bit random numbers together will suit my purposes quite well, I was
just curious about why that sort of uneven distribution would happen.
Again, thanks for your very informative answer.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2003-07-28 13:14 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-07-25 14:34 Random Number Generator Problem Brien
2003-07-25 15:34 ` Robert I. Eachus
2003-07-28 13:14 ` Brien
2003-07-25 17:06 ` Anisimkov
2003-07-25 18:05 ` Robert I. Eachus
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox