caml-list - the Caml user's mailing list
 help / color / Atom feed
From: "basile@starynkevitch.net" <basile@starynkevitch.net>
To: "François Pottier" <francois.pottier@inria.fr>
Cc: caml-list@inria.fr
Subject: Re: [Caml-list] zarith: how to  pick a random integer?
Date: Thu, 28 Nov 2019 10:27:17 +0100
Message-ID: <5cef-5ddf9300-35-4e2fd700@138599352> (raw)

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

             reply index

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-11-28  9:27 basile [this message]
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

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-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=5cef-5ddf9300-35-4e2fd700@138599352 \
    --to=basile@starynkevitch.net \
    --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 the In-Reply-To header
  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