Accueil     À propos     Téléchargement     Ressources     Contactez-nous

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Random questions
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2009-12-03 (11:01) From: AUGER Subject: Re: [Caml-list] Random questions
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