```
From: Carl Eastlund <ceastlund@janestreet.com>
To: "François Pottier" <francois.pottier@inria.fr>
Cc: caml users <caml-list@inria.fr>
Subject: Re: [Caml-list] zarith: how to pick a random integer?
Date: Wed, 27 Nov 2019 16:51:46 -0500
Message-ID: <CALyFioQiQc1LCpWA9N3p6JHESRH+7AY+0sZxC2G8o42WbW5xtg@mail.gmail.com> (raw)
In-Reply-To: <a025b23b-a84d-164f-7fb9-06a5ee083753@inria.fr>
[-- 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 --]
<div dir="ltr">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.)<div><br></div><div><a href="https://github.com/janestreet/bignum/blob/master/bigint/src/bigint.ml" target="_blank">https://github.com/janestreet/bignum/blob/master/bigint/src/bigint.ml</a></div><div><br></div><div>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.</div><div><br></div><div>This is the same trick that Random.int does, but with an unbounded number of bits instead of a fixed number of bits.</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Nov 27, 2019 at 4:31 PM François Pottier <<a href="mailto:francois.pottier@inria.fr" target="_blank">francois.pottier@inria.fr</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
Hello,<br>
<br>
I am using zarith and would like to pick a random integer<br>
comprised between 0 and some bound. I would like a function<br>
Z.random of type Z.t -> Z.t, but this function seems to be<br>
missing, and I am not sure how to program it in an efficient<br>
and correct way. Any suggestions would be welcome. Thanks!<br>
<br>
-- <br>
François Pottier<br>
<a href="mailto:francois.pottier@inria.fr" target="_blank">francois.pottier@inria.fr</a><br>
<a href="http://gallium.inria.fr/~fpottier/" rel="noreferrer" target="_blank">http://gallium.inria.fr/~fpottier/</a><br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div>Carl Eastlund<br></div></div></div>
```

next prev parent reply indexThread overview:5+ messages / expand[flat|nested] mbox.gz Atom feed top 2019-11-27 21:31 François Pottier2019-11-27 21:51 ` Carl Eastlund [this message]2019-11-28 8:13 ` François Pottier 2019-11-28 9:27 basile 2019-11-28 9:30 ` basile

Reply instructions:You may reply publically to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the--to,--cc, and--in-reply-toswitches of git-send-email(1): git send-email \ --in-reply-to=CALyFioQiQc1LCpWA9N3p6JHESRH+7AY+0sZxC2G8o42WbW5xtg@mail.gmail.com \ --to=ceastlund@janestreet.com \ --cc=caml-list@inria.fr \ --cc=francois.pottier@inria.fr \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting theIn-Reply-Toheader via mailto: links, try the mailto: link

caml-list - the Caml user's mailing list Archives are clonable: git clone --mirror http://inbox.vuxu.org/caml-list git clone --mirror https://inbox.ocaml.org/caml-list Example config snippet for mirrors Newsgroup available over NNTP: nntp://inbox.vuxu.org/vuxu.archive.caml-list AGPL code for this site: git clone https://public-inbox.org/public-inbox.git