Random questions

Random questions

[Daniel Bünzli]

I know little about PRGN and unfortunately in a lot of cases the
functions in the Random module don't provide me the right
interface. Could anybody tell me if the following functions preserve
the quality of the underlying PRGN and/or if there's a better way to
achieve that :

1) Generate an arbitrary int

let rint () = Random.bits () lor ((Random.bits () land 1) lsl 30)


2) Generate an arbitrary int in [0;max] (bounds included)

let random_uint ?(max = max_int) =
  if max < 0 then invalid_arg "negative max" else
  if max = max_int then Random.bits else
  let bound = max + 1 in
  fun () -> Random.int bound


3) Generate an arbitrary int in [-max;max] (bounds included)

let random_int ?(max = max_int) =
  if max < 0 then invalid_arg "negative max" else
  if max = max_int then
    let rec aux () =
      let v = rint () in if v = min_int then aux () else v in
      aux
  else
    let bound = (2 * max) + 1 in
    if 0 < bound && bound < max_int then
      fun () -> -max + Random.int bound
    else
      let bound = Int32.add (Int32.mul 2l (Int32.of_int max)) 1l in
      let min = Int32.of_int (-max) in
      fun () -> Int32.to_int (Int32.add min (Random.int32 bound))


5) Generate an arbitrary float in [0;max] (bounds included)

let after_one = 1. +. epsilon_float
let random_ufloat ?(max = max_float) =
  if max < 0. then invalid_arg "negative max" else
  fun () -> (Random.float after_one) *. max


6) Generate an arbitrary float in [-max;max] (bounds included)

let after_one = 1. +. epsilon_float
let random_float ?(max = max_float) =
  if max < 0. then invalid_arg "negative max" else
  fun () -> (-1. +. (Random.float after_one) *. 2.) *. max


Thanks for your answers,

Daniel

Re: [Caml-list] Random questions

[AUGER]

Le Wed, 18 Nov 2009 11:59:08 +0100, Daniel Bünzli  
<daniel.buenzli@erratique.ch> a écrit:

> I know little about PRGN and unfortunately in a lot of cases the
> functions in the Random module don't provide me the right
> interface. Could anybody tell me if the following functions preserve
> the quality of the underlying PRGN and/or if there's a better way to
> achieve that :
>

(* preliminary function: negate_minus_1 : int -> int : n |-> -n-1 *)
let negate_minus_1 = (lor) (-(max_int/2)-1) (* or inline the constant *)


> 1) Generate an arbitrary int
>
> let rint () = Random.bits () lor ((Random.bits () land 1) lsl 30)
It seems ok to me even if this variant seems slightly more efficient,
since we don't have to bother with making a single bit;
note the use of the xor instead of the or, which keeps the probability of  
one bit to 1/2
(in your example, this probability was kept since one of the bit was  
forced to be 0):

let rint () = (Random.bits () lsl 1) lxor (Random.bits ());;

-or-

let rint () = let r = Random.bits () in
	      if Random.bool () then negate_minus_1 r (* or inline negate_minus_1  
*)
	      else r

note these functions don't rely on the fact ints are on 31 bits
if Random.bool is more efficient than Random.bits, the latter seems the  
best; to be benchmarked...

>
>
> 2) Generate an arbitrary int in [0;max] (bounds included)
>
> let random_uint ?(max = max_int) =
>   if max < 0 then invalid_arg "negative max" else
>   if max = max_int then Random.bits else
>   let bound = max + 1 in
>   fun () -> Random.int bound

Seems correct.
I don't know if use of exception is more efficient or not, it is to try:

let random_uint ?(max = max_int) () =
  try if max = max_int then Random.bits () else Random.int (max + 1)
  with Invalid_argument "Random.int" -> invalid_arg "negative max"

>
>
> 3) Generate an arbitrary int in [-max;max] (bounds included)
>
> let random_int ?(max = max_int) =
>   if max < 0 then invalid_arg "negative max" else
>   if max = max_int then
>     let rec aux () =
>       let v = rint () in if v = min_int then aux () else v in
>       aux
>   else
>     let bound = (2 * max) + 1 in
>     if 0 < bound && bound < max_int then
>       fun () -> -max + Random.int bound
>     else
>       let bound = Int32.add (Int32.mul 2l (Int32.of_int max)) 1l in
>       let min = Int32.of_int (-max) in
>       fun () -> Int32.to_int (Int32.add min (Random.int32 bound))
>
>

I think it is better to use the bool trick;
simpler and doesn't use Int32:

let random_int ?(max = max_int) =
    if max < 0 then invalid_arg "negative max" else
    if max = 0 then 0 else
    if Random.bool ()
    then if max = max_int then Random.bits ()
         else Random.int max
    else negate_minus_1 (Random.int (max - 1)) (* inline? *)

> 5) Generate an arbitrary float in [0;max] (bounds included)
>
> let after_one = 1. +. epsilon_float
> let random_ufloat ?(max = max_float) =
>   if max < 0. then invalid_arg "negative max" else
>   fun () -> (Random.float after_one) *. max
This function is less interesting than Random.float:
only less or as many as values as floats in [0.;1.] can be generated
so you will miss many values only to be able to produce max
(for example, you cannot 1+eps if you try random_ufloat ~max:2. ())

The best would be to have a succ function for floats
>
>
> 6) Generate an arbitrary float in [-max;max] (bounds included)
>
> let after_one = 1. +. epsilon_float
> let random_float ?(max = max_float) =
>   if max < 0. then invalid_arg "negative max" else
>   fun () -> (-1. +. (Random.float after_one) *. 2.) *. max
>
same remark
>
> Thanks for your answers,
>
> Daniel
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs


-- 
Cédric AUGER

Univ Paris-Sud, Laboratoire LRI, UMR 8623, F-91405, Orsay

Re: [Caml-list] Random questions

[Daniel Bünzli]

Hello Cedric,

Thanks for your comments. Comments on your comments.

> let rint () = (Random.bits () lsl 1) lxor (Random.bits ());;

That was actually my first version. However I dropped it because I
thought that generating a new random number by the interaction of the
bits of two successive PRN could somehow change the underlying quality
of the generator. Any thought ?

> if Random.bool is more efficient than Random.bits, the latter seems the
> best; to be benchmarked

Random.bool is Random.bits () land 0 = 1.

>> 2) Generate an arbitrary int in [0;max] (bounds included)
>>
>> let random_uint ?(max = max_int) =
>>  if max < 0 then invalid_arg "negative max" else
>>  if max = max_int then Random.bits else
>>  let bound = max + 1 in
>>  fun () -> Random.int bound
>
> Seems correct.
> I don't know if use of exception is more efficient or not, it is to try:
>
> let random_uint ?(max = max_int) () =
>  try if max = max_int then Random.bits () else Random.int (max + 1)
>  with Invalid_argument "Random.int" -> invalid_arg "negative max"

You lose the ability to partially apply random_uint with the max and
avoid the if on each call.


> I think it is better to use the bool trick;
> simpler and doesn't use Int32:
>
> let random_int ?(max = max_int) =
>   if max < 0 then invalid_arg "negative max" else
>   if max = 0 then 0 else
>   if Random.bool ()
>   then if max = max_int then Random.bits ()
>        else Random.int max
>   else negate_minus_1 (Random.int (max - 1)) (* inline? *)
>

Yes, thanks. Your version can also be reordered to be partially applicable.

It should also be noted that all our functions for [int]s don't work
with the intended semantics on 64 bits platforms.

>> 5) Generate an arbitrary float in [0;max] (bounds included)
>>
>> let after_one = 1. +. epsilon_float
>> let random_ufloat ?(max = max_float) =
>>  if max < 0. then invalid_arg "negative max" else
>>  fun () -> (Random.float after_one) *. max
>
> This function is less interesting than Random.float:
> only less or as many as values as floats in [0.;1.] can be generated
> so you will miss many values only to be able to produce max
> (for example, you cannot 1+eps if you try random_ufloat ~max:2. ())

The point you make maybe valid but unfortunately that's also the case
for Random.float as this is the way it is implemented (generate a
number in [0;1[ and scale it).

Best,

Daniel

Re: [Caml-list] Random questions

[AUGER]

Le Thu, 03 Dec 2009 15:48:37 +0100, Daniel Bünzli  
<daniel.buenzli@erratique.ch> a écrit:

> Hello Cedric,
>
> Thanks for your comments. Comments on your comments.
>
>> let rint () = (Random.bits () lsl 1) lxor (Random.bits ());;
>
> That was actually my first version. However I dropped it because I
> thought that generating a new random number by the interaction of the
> bits of two successive PRN could somehow change the underlying quality
> of the generator. Any thought ?

If it is the case, then the generation is of bad quality...
If you can predict the generated values of such combinations,
  then it is easy to predict the values of the base generator;
  which is then a bad generator.
(What I say is not valid for non reversible combination, such as "or" or  
"and",
  even if it implies that generator is of poor quality too;
  and not valid for complex operation, such as emulating the generator  
itself).
I am not expert in this domain, so it is better to directly ask on  
specialists.

>
>> if Random.bool is more efficient than Random.bits, the latter seems the
>> best; to be benchmarked
>
> Random.bool is Random.bits () land 0 = 1.
ok, so this function is not as interessant as I thought.

>
>>> 2) Generate an arbitrary int in [0;max] (bounds included)
>>>
>>> let random_uint ?(max = max_int) =
>>>  if max < 0 then invalid_arg "negative max" else
>>>  if max = max_int then Random.bits else
>>>  let bound = max + 1 in
>>>  fun () -> Random.int bound
>>
>> Seems correct.
>> I don't know if use of exception is more efficient or not, it is to try:
>>
>> let random_uint ?(max = max_int) () =
>>  try if max = max_int then Random.bits () else Random.int (max + 1)
>>  with Invalid_argument "Random.int" -> invalid_arg "negative max"
>
> You lose the ability to partially apply random_uint with the max and
> avoid the if on each call.
>
>
>> I think it is better to use the bool trick;
>> simpler and doesn't use Int32:
>>
>> let random_int ?(max = max_int) =
>>   if max < 0 then invalid_arg "negative max" else
>>   if max = 0 then 0 else
>>   if Random.bool ()
>>   then if max = max_int then Random.bits ()
>>        else Random.int max
>>   else negate_minus_1 (Random.int (max - 1)) (* inline? *)
>>
>
> Yes, thanks. Your version can also be reordered to be partially  
> applicable.
>
> It should also be noted that all our functions for [int]s don't work
> with the intended semantics on 64 bits platforms.

I noticed it, but I may have forgot to write it down.

>
>>> 5) Generate an arbitrary float in [0;max] (bounds included)
>>>
>>> let after_one = 1. +. epsilon_float
>>> let random_ufloat ?(max = max_float) =
>>>  if max < 0. then invalid_arg "negative max" else
>>>  fun () -> (Random.float after_one) *. max
>>
>> This function is less interesting than Random.float:
>> only less or as many as values as floats in [0.;1.] can be generated
>> so you will miss many values only to be able to produce max
>> (for example, you cannot 1+eps if you try random_ufloat ~max:2. ())
>
> The point you make maybe valid but unfortunately that's also the case
> for Random.float as this is the way it is implemented (generate a
> number in [0;1[ and scale it).
Ok, in fact it is reasonnable to do it since generating a random bit  
sequence (uniformly)
won't lead to a uniform law on floats, taking the exposant in  
consideration, will result in
more fine grained generator, but at a rather high cost.
and between 0 and 1 you can use int generation.

Furthermore, use of generated random floats is often done in [0;1] (as it  
is a probability).

>
> Best,
>
> Daniel
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs


-- 
Cédric AUGER

Univ Paris-Sud, Laboratoire LRI, UMR 8623, F-91405, Orsay

Re: [Caml-list] Random questions

[Damien Doligez]

On 2009-12-03, at 12:00, AUGER wrote:

> (* preliminary function: negate_minus_1 : int -> int : n |-> -n-1 *)
> let negate_minus_1 = (lor) (-(max_int/2)-1) (* or inline the  
> constant *)

You probably mean this:

    let negate_minus_1 = (lxor) (-1);;

-- Damien

Re: [Caml-list] Random questions

[AUGER]

Le Thu, 03 Dec 2009 17:01:18 +0100, Damien Doligez  
<damien.doligez@inria.fr> a écrit:

>
> On 2009-12-03, at 12:00, AUGER wrote:
>
>> (* preliminary function: negate_minus_1 : int -> int : n |-> -n-1 *)
>> let negate_minus_1 = (lor) (-(max_int/2)-1) (* or inline the constant *)
>
> You probably mean this:
>
>     let negate_minus_1 = (lxor) (-1);;
>
> -- Damien

You are right

>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs


-- 
Cédric AUGER

Univ Paris-Sud, Laboratoire LRI, UMR 8623, F-91405, Orsay