*[Caml-list] zarith: how to pick a random integer?@ 2019-11-27 21:31 François Pottier2019-11-27 21:52 ` Carl Eastlund 0 siblings, 1 reply; 5+ messages in thread 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/ ^ permalink raw reply [flat|nested] 5+ messages in thread

*Re: [Caml-list] zarith: how to pick a random integer?2019-11-27 21:31 [Caml-list] zarith: how to pick a random integer? François Pottier@ 2019-11-27 21:52 ` Carl Eastlund2019-11-28 8:13 ` François Pottier 0 siblings, 1 reply; 5+ messages in thread From: Carl Eastlund @ 2019-11-27 21:52 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 --] ^ permalink raw reply [flat|nested] 5+ messages in thread

*Re: [Caml-list] zarith: how to pick a random integer?2019-11-27 21:52 ` Carl Eastlund@ 2019-11-28 8:13 ` François Pottier0 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/ ^ permalink raw reply [flat|nested] 5+ messages in thread

*Re: [Caml-list] zarith: how to pick a random integer?@ 2019-11-28 9:27 basile2019-11-28 9:30 ` basile 0 siblings, 1 reply; 5+ messages in thread 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 --] ^ permalink raw reply [flat|nested] 5+ messages in thread

*2019-11-28 9:27 basileRe: [Caml-list] zarith: how to pick a random integer?@ 2019-11-28 9:30 ` basile0 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 --] ^ permalink raw reply [flat|nested] 5+ messages in thread

end of thread, back to indexThread overview:5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-11-27 21:31 [Caml-list] zarith: how to pick a random integer? François Pottier 2019-11-27 21:52 ` Carl Eastlund 2019-11-28 8:13 ` François Pottier 2019-11-28 9:27 basile 2019-11-28 9:30 ` basile

caml-list - the Caml user's mailing list Archives are clonable: git clone --mirror https://inbox.ocaml.org/caml-list AGPL code for this site: git clone https://public-inbox.org/ public-inbox