caml-list - the Caml user's mailing list
 help / Atom feed
From: Carl Eastlund <>
To: François Pottier <>
Cc: caml users <>
Subject: Re: [Caml-list] zarith: how to pick a random integer?
Date: Wed, 27 Nov 2019 16:51:46 -0500
Message-ID: <> (raw)
In-Reply-To: <>

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

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

> 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

Carl Eastlund

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

  reply index

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-11-27 21:31 François Pottier
2019-11-27 21:52 ` 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:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \ \

* 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

AGPL code for this site: git clone public-inbox