From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 677AEBC57 for ; Sun, 9 May 2010 12:07:38 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtgAAG8l5kuA1s0wkWdsb2JhbACRXow9FQEBAQEJCwoHEQUdvBiCY4IyBIM9 X-IronPort-AV: E=Sophos;i="4.52,356,1270418400"; d="scan'208";a="62538930" Received: from slay.it.helsinki.fi ([128.214.205.48]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 09 May 2010 12:07:37 +0200 Received: from slay.it.helsinki.fi (slay.it.helsinki.fi [128.214.205.48]) by slay.it.helsinki.fi (8.13.1/8.13.1) with ESMTP id o49A7SVf007580; Sun, 9 May 2010 13:07:28 +0300 Received: from ruuvi.it.helsinki.fi (ruuvi.it.helsinki.fi [128.214.205.65]) by smtp-rs1.it.helsinki.fi (8.13.1/8.13.1) with ESMTP id o49A7Slx013700 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Sun, 9 May 2010 13:07:28 +0300 Received: from ruuvi.it.helsinki.fi (localhost.localdomain [127.0.0.1]) by ruuvi.it.helsinki.fi (8.13.1/8.13.1) with ESMTP id o49A7Sek024490; Sun, 9 May 2010 13:07:28 +0300 Received: (from lealanko@localhost) by ruuvi.it.helsinki.fi (8.13.1/8.13.1/Submit) id o49A7SQK024489; Sun, 9 May 2010 13:07:28 +0300 Date: Sun, 9 May 2010 13:07:28 +0300 From: Lauri Alanko To: caml-list@inria.fr Subject: Generating random generators Message-ID: <20100509100728.GA23132@ruuvi.it.helsinki.fi> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.1i X-HY-Tests: ALL_TRUSTED X-Spam: no; 0.00; lauri:01 alanko:01 haskell:01 prng:01 prng:01 ocaml's:01 val:01 pitfalls:01 invokes:01 overkill:01 lauri:01 digest:01 imperative:01 int:01 algorithm:01 To parallelize a probabilistic algorithm while retaining reproducibility, it is often useful to have several independent streams of pseudo-random numbers. In Haskell, there is a standard operation Random.split, which takes a PRNG state and produces two new PRNG states which should hopefully produce two seemingly unrelated number streams. OCaml's random library works in an imperative setting where each generation operation implicitly updates the state of the generator, so the corresponding operation would simply be generating a new random generator: val spawn : Random.State.t -> Random.State.t Alas, such an operation is not provided by the library. The most straightforward implementation would be the following: let spawn s = Random.State.make (Array.init 55 (fun _ -> Random.State.bits s)) However, random numbers are tricky, and I'm suspicious of just adding a new operation ad hoc when I don't understand how the underlying PRNG works. Hence, I'd appreciate if anyone could offer some insight on whether the above approach has any hidden pitfalls (i.e. some sort of regularity that might appear when the values from two generated streams are combined in a particular fashion), or if there is a faster way of generating new generators robustly. Random.State.make invokes Digest.string for every int of the seed, so it seems like overkill. Thanks in advance. Lauri