caml-list - the Caml user's mailing list
help / color / Atom feed
* Re: [Caml-list] zarith: how to  pick a random integer?
@ 2019-11-28  9:27 basile
2019-11-28  9:30 ` basile
From: basile @ 2019-11-28  9:27 UTC (permalink / raw)
To: François Pottier; +Cc: caml-list

[-- 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 --]

<html><br />On Wednesday, November 27, 2019 22:31 CET, François Pottier &lt;francois.pottier@inria.fr&gt; wrote:<br />&nbsp;<blockquote type="cite" cite="a025b23b-a84d-164f-7fb9-06a5ee083753@inria.fr"><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 -&gt; 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 />&nbsp;</blockquote><br />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).<br /><br />Let B be the bound.<br /><br />You take a random number modulus 2*B. Let R be that number<br /><br />You modelize the [0;B[ interval as a ring of numbers. For example if B is 5 : 0 -&gt; 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 0 -&gt; 1 -&gt; .... ad infinitium<br /><br /><br />You memoize the previously given random number N<br /><br />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<br /><br />But check with an expert, I am not one<br /><br />--<br /><br />Basile<br />&nbsp;</html>

* Re: [Caml-list] zarith: how to  pick a random integer?
2019-11-28  9:27 [Caml-list] zarith: how to pick a random integer? basile
@ 2019-11-28  9:30 ` basile
0 siblings, 0 replies; 5+ messages in thread
From: basile @ 2019-11-28  9:30 UTC (permalink / raw)
To: François Pottier; +Cc: caml-list

[-- 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 --]

<html><br />On Thursday, November 28, 2019 10:27 CET, basile@starynkevitch.net &lt;basile@starynkevitch.net&gt; wrote:<br /><br /><br />Sorry for the important typo. Corrected below<br /><br />On Wednesday, November 27, 2019 22:31 CET, François Pottier &lt;francois.pottier@inria.fr&gt; wrote:<br />&nbsp;<blockquote type="cite" cite="a025b23b-a84d-164f-7fb9-06a5ee083753@inria.fr"><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 -&gt; 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 />&nbsp;</blockquote><br />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).<br /><br />Let B be the bound.<br /><br />You take a random number modulus 2*B. Let R be that number<br /><br />You modelize the [0;B[ interval as a ring of numbers. For example if B is 5 : 0 -&gt; 1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 0 -&gt; 1 -&gt; .... ad infinitium<br /><br /><br />You memoize the previously given random number N<br /><br />On that ring, you go R steps forward and obtain P. That is your new random number and on the next iteration the <strong>N</strong> would be that P<br /><br />But check with an expert, I am not one<br /><br />--<br /><br />Basile Starynkevitch http://starynkevitch.net/Basile<br />&nbsp;<br /><br /><br />&nbsp;</html>

* Re: [Caml-list] zarith: how to pick a random integer?
2019-11-27 21:51 ` Carl Eastlund
@ 2019-11-28  8:13   ` François Pottier
0 siblings, 0 replies; 5+ messages in thread
From: François Pottier @ 2019-11-28  8:13 UTC (permalink / raw)
To: Carl Eastlund; +Cc: caml users

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/

* Re: [Caml-list] zarith: how to pick a random integer?
2019-11-27 21:31 François Pottier
@ 2019-11-27 21:51 ` Carl Eastlund
2019-11-28  8:13   ` François Pottier
From: Carl Eastlund @ 2019-11-27 21:51 UTC (permalink / raw)
To: François Pottier; +Cc: caml users

[-- 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&#39;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 &lt;<a href="mailto:francois.pottier@inria.fr" target="_blank">francois.pottier@inria.fr</a>&gt; 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 -&gt; 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>

* [Caml-list] zarith: how to pick a random integer?
@ 2019-11-27 21:31 François Pottier
2019-11-27 21:51 ` Carl Eastlund
From: François Pottier @ 2019-11-27 21:31 UTC (permalink / raw)
To: caml users

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/

end of thread, back to index

2019-11-28  9:27 [Caml-list] zarith: how to pick a random integer? basile
2019-11-28  9:30 ` basile
-- strict thread matches above, loose matches on Subject: below --
2019-11-27 21:31 François Pottier
2019-11-27 21:51 ` Carl Eastlund
2019-11-28  8:13   ` François Pottier

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