Ada.Numerics.Float_Random.Generator question

Ada.Numerics.Float_Random.Generator question

[Andrew Shvets]

Hello,

If I want a random float number to be generated, the way that I did this in the past was something along these lines:

  function Create_Random_Float(
    From : in Float;
    To : in Float)
      return Float is

    Seed : Ada.Numerics.Float_Random.Generator;
  begin
    Ada.Numerics.Float_Random.Reset(Seed);

    return From + (Ada.Numerics.Float_Random.Random(Seed) * To);
  end Create_Random_Float;

This works.  However, as I'm now looking into the Ada.Numerics.Discrete_Random package, I've noticed that it can generate a random value based on the type that is passed in.  This appeals to me and I'd like to do the same for a custom float type (say I want the delta to be 0.01.)

As Ada.Numerics.Float_Random.Generator is not a generic package, I can't use the same approach.  The best way that I can think of is to create the same result using From and To and then cast the result to the custom float type.

I hope that there is a better solution to this.  Is there?

Re: Ada.Numerics.Float_Random.Generator question

[J-P. Rosen]

Le 17/09/2016 à 21:40, Andrew Shvets a écrit :
> This works.  However, as I'm now looking into the
> Ada.Numerics.Discrete_Random package, I've noticed that it can
> generate a random value based on the type that is passed in.  This
> appeals to me and I'd like to do the same for a custom float type
> (say I want the delta to be 0.01.)

Beware! Random number generators are tricky. It took megabytes of
discussion to come to the conclusion that it was not possible to make a
proper discrete generator out of a floating point generator...

Now, if you want a delta of 0.01, it looks more like a fixed point than
a floating point. This can be easily achieved by instantiating
discrete_random on an integer type with the proper number of values and
then multiplying by 0.01.
-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: Ada.Numerics.Float_Random.Generator question

[Andrew Shvets]

On Saturday, September 17, 2016 at 4:10:03 PM UTC-4, J-P. Rosen wrote:
> Le 17/09/2016 à 21:40, Andrew Shvets a écrit :
> > This works.  However, as I'm now looking into the
> > Ada.Numerics.Discrete_Random package, I've noticed that it can
> > generate a random value based on the type that is passed in.  This
> > appeals to me and I'd like to do the same for a custom float type
> > (say I want the delta to be 0.01.)
> 
> Beware! Random number generators are tricky. It took megabytes of
> discussion to come to the conclusion that it was not possible to make a
> proper discrete generator out of a floating point generator...
> 
> Now, if you want a delta of 0.01, it looks more like a fixed point than
> a floating point. This can be easily achieved by instantiating
> discrete_random on an integer type with the proper number of values and
> then multiplying by 0.01.
> -- 
> J-P. Rosen
> Adalog
> 2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
> Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
> http://www.adalog.fr

So, basically, there is no equally elegant solution for floats as there is for Ada.Numerics.Discrete_Random and integer types.

That's unfortunate.

Re: Ada.Numerics.Float_Random.Generator question

[Jeffrey R. Carter]

On 09/17/2016 12:40 PM, Andrew Shvets wrote:
> Hello,
> 
> If I want a random float number to be generated, the way that I did this in the past was something along these lines:
> 
>   function Create_Random_Float(
>     From : in Float;
>     To : in Float)
>       return Float is
> 
>     Seed : Ada.Numerics.Float_Random.Generator;
>   begin
>     Ada.Numerics.Float_Random.Reset(Seed);
> 
>     return From + (Ada.Numerics.Float_Random.Random(Seed) * To);
>   end Create_Random_Float;
> 
> This works.  

No, it doesn't. If From is 5 and To is 10, This gives a value in 5 .. 15.

However, as I'm now looking into the Ada.Numerics.Discrete_Random package, I've
noticed that it can generate a random value based on the type that is passed in.
 This appeals to me and I'd like to do the same for a custom float type (say I
want the delta to be 0.01.)
> 
> As Ada.Numerics.Float_Random.Generator is not a generic package, I can't use the same approach.  The best way that I can think of is to create the same result using From and To and then cast the result to the custom float type.

The PragmAda Reusable Components contain several RNGs, all of which can be used
to obtain random values of user-defined floating-point types. You can find them at

https://github.com/jrcarter/PragmARC

-- 
Jeff Carter
"C++ is like jamming a helicopter inside a Miata
and expecting some sort of improvement."
Drew Olbrich
51

Re: Ada.Numerics.Float_Random.Generator question

[Andrew Shvets]

On Saturday, September 17, 2016 at 5:01:29 PM UTC-4, Jeffrey R. Carter wrote:
> On 09/17/2016 12:40 PM, Andrew Shvets wrote:
> > Hello,
> > 
> > If I want a random float number to be generated, the way that I did this in the past was something along these lines:
> > 
> >   function Create_Random_Float(
> >     From : in Float;
> >     To : in Float)
> >       return Float is
> > 
> >     Seed : Ada.Numerics.Float_Random.Generator;
> >   begin
> >     Ada.Numerics.Float_Random.Reset(Seed);
> > 
> >     return From + (Ada.Numerics.Float_Random.Random(Seed) * To);
> >   end Create_Random_Float;
> > 
> > This works.  
> 
> No, it doesn't. If From is 5 and To is 10, This gives a value in 5 .. 15.

You're right.

Re: Ada.Numerics.Float_Random.Generator question

[rieachus]

On Saturday, September 17, 2016 at 3:40:13 PM UTC-4, Andrew Shvets wrote:
 
> This works.  However, as I'm now looking into the Ada.Numerics.Discrete_Random package, I've noticed that it can generate a random value based on the type that is passed in.  This appeals to me and I'd like to do the same for a custom float type (say I want the delta to be 0.01.)
> 
> As Ada.Numerics.Float_Random.Generator is not a generic package, I can't use the same approach.  The best way that I can think of is to create the same result using From and To and then cast the result to the custom float type.
> 
> I hope that there is a better solution to this.  Is there?

Since working has to be better, yes.  First, what you seem to be asking for is a PRNG that selects from a uniform distribution of fixed point values.  To do this take the generic discrete random package, and redeclare it with a fixed point type:

generic
   type Result_Subtype is delta <>;
package My_Fixed_Random is

   -- Basic facilities

   type Generator is limited private;

   function Random (Gen : Generator) return Result_Subtype;

   procedure Reset (Gen       : in Generator;
                    Initiator : in Integer);
   procedure Reset (Gen       : in Generator);

   -- Advanced facilities

   type State is private;

   procedure Save  (Gen        : in  Generator;
                    To_State   : out State);
   procedure Reset (Gen        : in  Generator;
                    From_State : in  State);

   Max_Image_Width : constant := implementation-defined integer value;

   function Image (Of_State    : State)  return String;
   function Value (Coded_State : String) return State;

private
   
end My_Fixed_Random;

Now in the body, put an instance of generic discrete random fit to your fixed point type:

package body My_Fixed_Random is
  type Hidden is range Int64(Result_Subtype'First/Result_Subtype'Small)     ..Int64(Result_Subtype'Last/Result_Subtype'Small);

  package Hidden_Pkg is new Ada.Numerics.Discrete_Random(Hidden);

  Complete with the operations from My_Fixed_Random, multiplying by 'Small and converting to Result_Subtype where needed. All done. ;-)  I wish I had gotten this package added to the Numerics section, as you can see it is about a page of very easy code.  But there were lots of other issues that needed resolving, and not enough time to resolve them all.

Now for the evils that I hope you never meet.  With this package, you should generate only numbers that are multiples of 'Small, and each legal value for Result_Subtype should occur with equal probability.  You might have an issue with a value next below 'First, but usually if you have a fixed point type that officially has 2^n - 1 values, you will know what to do to avoid Constraint_Error.  More troubling is that the language rules allow for fixed point types where the specified 'Small or 'Delta does not evenly divide one.  I do think that permission is right--but if you use it, you had better know a lot about numerics.

Re: Ada.Numerics.Float_Random.Generator question

[brbarkstrom]

On Saturday, September 17, 2016 at 3:40:13 PM UTC-4, Andrew Shvets wrote:
> Hello,
> 
> If I want a random float number to be generated, the way that I did this in the past was something along these lines:
> 
>   function Create_Random_Float(
>     From : in Float;
>     To : in Float)
>       return Float is
> 
>     Seed : Ada.Numerics.Float_Random.Generator;
>   begin
>     Ada.Numerics.Float_Random.Reset(Seed);
> 
>     return From + (Ada.Numerics.Float_Random.Random(Seed) * To);
>   end Create_Random_Float;
> 
> This works.  However, as I'm now looking into the Ada.Numerics.Discrete_Random package, I've noticed that it can generate a random value based on the type that is passed in.  This appeals to me and I'd like to do the same for a custom float type (say I want the delta to be 0.01.)
> 
> As Ada.Numerics.Float_Random.Generator is not a generic package, I can't use the same approach.  The best way that I can think of is to create the same result using From and To and then cast the result to the custom float type.
> 
> I hope that there is a better solution to this.  Is there?

Probably best consult Knuth on Random Numbers.  Complicated subject; lots
of numerical issues - testing involves some high-powered math.  See also
Park and Miller in CACM back a fer decades ago.

Bruce B.

Re: Ada.Numerics.Float_Random.Generator question

[Robert Eachus]

On Sunday, September 25, 2016 at 7:41:26 PM UTC-4, brbar...@gmail.com wrote:
> 
> > I hope that there is a better solution to this.  Is there?
> 
> Probably best consult Knuth on Random Numbers.  Complicated subject; lots
> of numerical issues - testing involves some high-powered math.  See also
> Park and Miller in CACM back a fer decades ago.
 
Sigh! I'm probably not the best expert available on random numbers (and pseudo RNGs).  But I could write a book on the inadequacies of Park and Miller, or all that has been learned since Knuth.  It is now possible to have fast PRNGs based on Blum, Blum, and Schub (https://en.wikipedia.org/wiki/Blum_Blum_Shub ) and that is now thirty year old technology. The latest includes not only cryptographically secure RNGs, but quantum cryptography which allows for seeds to be communicated without risk of evesdropping.

Most of that is more than needed for most RNGs, but there is no reason not to be at least that good. Park and Miller for example will "roll over" and start generating the same sequence again.  When it was publish this was not a big risk.  Today even "small" simulations will use more values that Park and Miller should be used to generate.

Oh, and I should probably write up a paper on using RNGs correctly.  It is silly to use an RNG that has lots of (theoretical) nice properties, then throw all that away in how you use the RNG. 

Re: Ada.Numerics.Float_Random.Generator question

[brbarkstrom]

On Monday, September 26, 2016 at 9:04:34 AM UTC-4, Robert Eachus wrote:
> > 
> > > I hope that there is a better solution to this.  Is there?
> > 
> > Probably best consult Knuth on Random Numbers.  Complicated subject; lots
> > of numerical issues - testing involves some high-powered math.  See also
> > Park and Miller in CACM back a fer decades ago.
>  
> Sigh! I'm probably not the best expert available on random numbers (and pseudo RNGs).  But I could write a book on the inadequacies of Park and Miller, or all that has been learned since Knuth.  It is now possible to have fast PRNGs based on Blum, Blum, and Schub (https://en.wikipedia.org/wiki/Blum_Blum_Shub ) and that is now thirty year old technology. The latest includes not only cryptographically secure RNGs, but quantum cryptography which allows for seeds to be communicated without risk of evesdropping.
> 
> Most of that is more than needed for most RNGs, but there is no reason not to be at least that good. Park and Miller for example will "roll over" and start generating the same sequence again.  When it was publish this was not a big risk.  Today even "small" simulations will use more values that Park and Miller should be used to generate.
> 
> Oh, and I should probably write up a paper on using RNGs correctly.  It is silly to use an RNG that has lots of (theoretical) nice properties, then throw all that away in how you use the RNG.

Of course most of the RNG's roll over.  That's been known - and is even
referenced in Knuth.  The key question is selecting the appropriate values
for the algorithm so you can get longer cycles.  I know Park was
moving toward running multiple RNGs and then selecting one of them 
(approximately at random), but that was a long time ago.  

The National Institute for Standards and Technology (NIST) has probably
included RNG's in a note:
https://www.nist.gov/news-events/news/2014/04/nist-removes-cryptography-algorithm-random-number-generator-recommendations.  http://www.colostate.edu/~pburns/monte/rngreport.pdf doesn't have references after 2000.  The most
recent URL I could find in Wikipedia was https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator, which has
an update from Sept. 1, 2016.

Probably the place to start is the NIST URL: http://csrc.nist.gov/groups/ST/toolkit/random_number.html and then consult the last major entry on
that page for the NIST approved algorithms and their suggested validation
algorithms that include recommended statistical tests.

Bruce B.

Re: Ada.Numerics.Float_Random.Generator question

[Some Dude]

To add to Bruce's comment, aren't *all* PRNGs cyclic? I was always under this impression, but admittedly never looked for a proof.

Re: Ada.Numerics.Float_Random.Generator question

[Robert Eachus]

On Thursday, September 29, 2016 at 5:42:17 AM UTC-4, Some Dude wrote:
> To add to Bruce's comment, aren't *all* PRNGs cyclic? I was always under this impression, but admittedly never looked for a proof.

No, a simple counter-example is a generator that uses the digits of pi.  The digits of any transcendental number will do. I'll have to think about generator based on a square root. (Not about whether it would work, it would.  But about how to implement it so that you don't have arbitrary pauses.  Hmm.  One task to generate the root?  Managing priorities could be tricky.)

Re: Ada.Numerics.Float_Random.Generator question

[Paul Rubin]

Robert Eachus <rieachus@comcast.net> writes:
>> aren't *all* PRNGs cyclic?
> No, a simple counter-example is a generator that uses the digits of
> pi.  The digits of any transcendental number will do. 

I don't see how this would work--to never cycle, it would need infinite
internal state.  You could consider the digits of pi to be part of the
state, but to count off the digits, you need a counter of infinite
width.

> But about how to implement it so that you don't have arbitrary pauses.

https://en.wikipedia.org/wiki/Spigot_algorithm

Re: Ada.Numerics.Float_Random.Generator question

[Robert Eachus]

On Friday, September 30, 2016 at 11:59:15 PM UTC-4, Paul Rubin wrote:
> Robert Eachus <rieachus@comcast.net> writes:
> >> aren't *all* PRNGs cyclic?
> > No, a simple counter-example is a generator that uses the digits of
> > pi.  The digits of any transcendental number will do. 
> 
> I don't see how this would work--to never cycle, it would need infinite
> internal state.  You could consider the digits of pi to be part of the
> state, but to count off the digits, you need a counter of infinite
> width.

A quick proof that a PRNG that never cycles requires infinite state:  If the generator ever returns to a previous state?  It cycles.

But there is infinite state, and infinite state.  An infinite state that is a simple counter of the number of values returned is probably acceptable, a generator that requires storing the whole sequence is not.  (Hmm.  The generators in http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf for Pi have a state of k integers for some k.  Of course, these are unbounded integers which will eventually require an array of finite integers to represent.  (Multiprecision arithmetic)  I think that is acceptable.

However, there is another problem with using the digits (binary, decimal, or hexadecimal) of Pi.  There is only one such sequence, so every program that uses it should start where other programs (in particular reruns of the same simulation) left off.  Choosing an n, then calulating ln n or e^n provides a seed that can be different for each run.

Is this discussion more than just idle chatter?  I think so.  Some of the spigot algorithms Paul Rubin points to are practical, given the speed of machines today.  Even if they are not quite, you can use a transcendental PRNG to seed a very long period non-trancendental generator every k values. Also more practical, if you are running a simulation on thousands of CPU cores, you can use a trancendental PRNG to seed each CPUs PRNG, or better reseed every n steps of the simulation.  (Note that you do not need to distribute the new seeds, they can be generated locally.  Again, a trancendental generator with a parameter or parameters is the next thing to look for. ;-)

Re: Ada.Numerics.Float_Random.Generator question

[Dmitry A. Kazakov]

On 2016-10-01 16:23, Robert Eachus wrote:

> But there is infinite state, and infinite state. An infinite state
> that is a simple counter of the number of values returned is probably
> acceptable, a generator that requires storing the whole sequence is not.

There is no difference both are infinite. Single infinite counter is 
capable to store whole sequence and conversely.

> Of course, these are unbounded
> integers which will eventually require an array of finite integers to
> represent. (Multiprecision arithmetic) I think that is acceptable.

An unbounded array of integers is infinite. Once you have it bound, you 
get repeating states or else a program halt.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Ada.Numerics.Float_Random.Generator question

[Robert Eachus]

On Saturday, October 1, 2016 at 11:50:04 AM UTC-4, Dmitry A. Kazakov wrote:
> On 2016-10-01 16:23, Robert Eachus wrote:
> 
> > But there is infinite state, and infinite state. An infinite state
> > that is a simple counter of the number of values returned is probably
> > acceptable, a generator that requires storing the whole sequence is not.
> 
> There is no difference both are infinite. Single infinite counter is 
> capable to store whole sequence and conversely.

My point was that a state which slowly grows toward infinity (the counter) can easily be stored.  Any state that requires infinite storage or grows non-polynomially is right out.  States which grow by some polynomial in the counter?  Depends. 

On the issue of multiple seeds, Pi times an integer is also trancendental, but the values would be correlated between sequences.  Multiplying Pi by a rational number is better, but I think natural logs of primes would work.  Of course, now we have the problem of converting the seed selected by the programmer, or the clock, or whatever, into unique prime seeds.