Re: [Caml-list] zarith: how to pick a random integer?

Re: [Caml-list] zarith: how to pick a random integer?

[basile]

[-- Attachment #1: Type: text/plain, Size: 1060 bytes --]


On Wednesday, November 27, 2019 22:31 CET, François Pottier <francois.pottier@inria.fr> wrote:
 
Hello,

I am using zarith and would like to pick a random integer
comprised between 0 and some bound. I would like a function
Z.random of type Z.t -> Z.t, but this function seems to be
missing, and I am not sure how to program it in an efficient
and correct way. Any suggestions would be welcome. Thanks!

 
I tend to believe that the following idea might be good, but please check with real probability experts. I definitely am not one (but one of my best colleagues is one).

Let B be the bound.

You take a random number modulus 2*B. Let R be that number

You modelize the [0;B[ interval as a ring of numbers. For example if B is 5 : 0 -> 1 -> 2 -> 3 -> 4 -> 0 -> 1 -> .... ad infinitium


You memoize the previously given random number N

On that ring, you go R steps forward and obtain P. That is your new random number and on the next iteration the R would be that P

But check with an expert, I am not one

--

Basile
 

[-- Attachment #2: Type: text/html, Size: 1325 bytes --]

Re: [Caml-list] zarith: how to pick a random integer?

[basile]

[-- Attachment #1: Type: text/plain, Size: 1269 bytes --]


On Thursday, November 28, 2019 10:27 CET, basile@starynkevitch.net <basile@starynkevitch.net> wrote:


Sorry for the important typo. Corrected below

On Wednesday, November 27, 2019 22:31 CET, François Pottier <francois.pottier@inria.fr> wrote:
 
Hello,

I am using zarith and would like to pick a random integer
comprised between 0 and some bound. I would like a function
Z.random of type Z.t -> Z.t, but this function seems to be
missing, and I am not sure how to program it in an efficient
and correct way. Any suggestions would be welcome. Thanks!

 
I tend to believe that the following idea might be good, but please check with real probability experts. I definitely am not one (but one of my best colleagues is one).

Let B be the bound.

You take a random number modulus 2*B. Let R be that number

You modelize the [0;B[ interval as a ring of numbers. For example if B is 5 : 0 -> 1 -> 2 -> 3 -> 4 -> 0 -> 1 -> .... ad infinitium


You memoize the previously given random number N

On that ring, you go R steps forward and obtain P. That is your new random number and on the next iteration the N would be that P

But check with an expert, I am not one

--

Basile Starynkevitch http://starynkevitch.net/Basile
 


 

[-- Attachment #2: Type: text/html, Size: 1593 bytes --]

[Caml-list] zarith: how to pick a random integer?

[François Pottier]

Hello,

I am using zarith and would like to pick a random integer
comprised between 0 and some bound. I would like a function
Z.random of type Z.t -> Z.t, but this function seems to be
missing, and I am not sure how to program it in an efficient
and correct way. Any suggestions would be welcome. Thanks!

-- 
François Pottier
francois.pottier@inria.fr
http://gallium.inria.fr/~fpottier/

Re: [Caml-list] zarith: how to pick a random integer?

[Carl Eastlund]

[-- Attachment #1: Type: text/plain, Size: 1399 bytes --]

See the Make_random functor in the janestreet Bigint library, which is
built on top of zarith. (It's a functor to produce random distributions
based on both Random.State.t and Base_quickcheck.Generator.t; the functor
itself is not exposed.)

https://github.com/janestreet/bignum/blob/master/bigint/src/bigint.ml

In short, we generate 30-bit chunks of randomness until we have at least
enough bits for our range. We combine those into a number. Usually, we just
modulo that by the range and return it. But to preserve fairness, we first
have to check if the number is in the last fraction-of-range part of the N
bits, and if so retry from scratch. The odds of retry are always less than
50%, so retrying is never too bad.

This is the same trick that Random.int does, but with an unbounded number
of bits instead of a fixed number of bits.

On Wed, Nov 27, 2019 at 4:31 PM François Pottier <francois.pottier@inria.fr>
wrote:

>
> Hello,
>
> I am using zarith and would like to pick a random integer
> comprised between 0 and some bound. I would like a function
> Z.random of type Z.t -> Z.t, but this function seems to be
> missing, and I am not sure how to program it in an efficient
> and correct way. Any suggestions would be welcome. Thanks!
>
> --
> François Pottier
> francois.pottier@inria.fr
> http://gallium.inria.fr/~fpottier/
>


-- 
Carl Eastlund

[-- Attachment #2: Type: text/html, Size: 2116 bytes --]

Re: [Caml-list] zarith: how to pick a random integer?

[François Pottier]

On 27/11/2019 22:51, Carl Eastlund wrote:
> See the Make_random functor in the janestreet Bigint library,

Thanks Carl, this is really helpful!

-- 
François Pottier
francois.pottier@inria.fr
http://gallium.inria.fr/~fpottier/