From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andreas Rottmann Newsgroups: gmane.lisp.guile.devel Subject: Re: Random numbers (again) broken on 64-bit platforms Date: Sun, 01 Aug 2010 20:44:42 +0200 Message-ID: <87mxt6maud.fsf@delenn.lan> References: <87vd82554r.fsf@delenn.lan> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Trace: dough.gmane.org 1280688564 24565 80.91.229.12 (1 Aug 2010 18:49:24 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 1 Aug 2010 18:49:24 +0000 (UTC) Cc: Guile Development To: Andy Wingo Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Aug 01 20:49:23 2010 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Ofdb7-0004hV-FE for guile-devel@m.gmane.org; Sun, 01 Aug 2010 20:49:21 +0200 Original-Received: from localhost ([127.0.0.1]:54685 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Ofdb6-0007uG-Hz for guile-devel@m.gmane.org; Sun, 01 Aug 2010 14:49:20 -0400 Original-Received: from [140.186.70.92] (port=57052 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1OfdWm-0004n7-JD for guile-devel@gnu.org; Sun, 01 Aug 2010 14:44:53 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1OfdWk-00026h-Tg for guile-devel@gnu.org; Sun, 01 Aug 2010 14:44:52 -0400 Original-Received: from mailout-de.gmx.net ([213.165.64.22]:42410 helo=mail.gmx.net) by eggs.gnu.org with smtp (Exim 4.69) (envelope-from ) id 1OfdWk-00024s-HU for guile-devel@gnu.org; Sun, 01 Aug 2010 14:44:50 -0400 Original-Received: (qmail invoked by alias); 01 Aug 2010 18:44:48 -0000 Original-Received: from 83-215-154-5.hage.dyn.salzburg-online.at (EHLO nathot.lan) [83.215.154.5] by mail.gmx.net (mp016) with SMTP; 01 Aug 2010 20:44:48 +0200 X-Authenticated: #3102804 X-Provags-ID: V01U2FsdGVkX186ozhP/9g6p98HFXSbs39U6R35q0tDnvFkCegxli fi8sGiLU7jcH1p Original-Received: from localhost (localhost.localdomain [127.0.0.1]) by nathot.lan (Postfix) with ESMTP id 93F903A695; Sun, 1 Aug 2010 20:44:47 +0200 (CEST) Original-Received: from nathot.lan ([127.0.0.1]) by localhost (nathot.lan [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Y0p2uO6gj-Pv; Sun, 1 Aug 2010 20:44:42 +0200 (CEST) Original-Received: from delenn.lan (delenn.lan [192.168.3.11]) by nathot.lan (Postfix) with ESMTP id BC1853A693; Sun, 1 Aug 2010 20:44:42 +0200 (CEST) Original-Received: by delenn.lan (Postfix, from userid 1000) id 9420B74EDA; Sun, 1 Aug 2010 20:44:42 +0200 (CEST) In-Reply-To: (Andy Wingo's message of "Tue, 27 Jul 2010 10:52:56 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) X-Y-GMX-Trusted: 0 X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:10751 Archived-At: --=-=-= Andy Wingo writes: > Heya, > > On Mon 26 Jul 2010 23:01, Andreas Rottmann writes: > >> scheme@(guile-user)> (random (ash 1 32)) >> ERROR: In procedure random: >> ERROR: Argument 1 out of range: 4294967296 > > Well, it's not a segfault at least :) > > The point of that change was to indicate that the RNG did not return > sizeof(unsigned long) bits of randomness; it always returned 32 > bits. See the note in "BSD Random Number Functions" in libc's manual: > > *NB:* Temporarily this function was defined to return a `int32_t' > value to indicate that the return value always contains 32 bits > even if `long int' is wider. The standard demands it differently. > Users must always be aware of the 32-bit limitation, though. > > I'll fix this now to avoid the error, but there is still work to do on > the RNG -- we really need to update the RNG, I think. Brian Gough, the > GSL maintainer, says MT19937 is the one to use, and specifically the new > SIMD version at > http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html. We > should replace our MWC RNG with that one. > I've spotted an issue with your fix: the way 64-bit random numbers are generated in scm_random() is bogus; to test that, I used the following code: (define (random-max n iterations) (let loop ((i 0) (result 0)) (if (< i iterations) (loop (+ i 1) (max (random n) result)) result))) (random-max #x1ffffffff 10000000) If you try this, you'll notice that `random-max' returns a much lower number than it should. The attached patch hopefully fixes this issue --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=random64-fix-2.diff From: Andreas Rottmann Subject: Fix the range of `random' on 64-bit platforms For > 32 bit integers still in the fixnum range, scm_random() would return random numbers with a lower range than specified. * libguile/random.c (scm_i_mask32): New static inline function. (scm_c_random): Use `scm_i_mask32'. (scm_c_random64): New function, 64-bit variant of scm_c_random. (scm_random): Use `scm_c_random64' instead of forming the 64-bit random number in a bogus way. * libguile/random.h: Added `scm_c_random64'. --- libguile/random.c | 42 +++++++++++++++++++++++++++--------------- libguile/random.h | 1 + 2 files changed, 28 insertions(+), 15 deletions(-) diff --git a/libguile/random.c b/libguile/random.c index 83870f6..c0a3e04 100644 --- a/libguile/random.c +++ b/libguile/random.c @@ -241,21 +241,42 @@ scm_c_exp1 (scm_t_rstate *state) unsigned char scm_masktab[256]; -scm_t_uint32 -scm_c_random (scm_t_rstate *state, scm_t_uint32 m) +static inline scm_t_uint32 +scm_i_mask32 (scm_t_uint32 m) { - scm_t_uint32 r, mask; - mask = (m < 0x100 + return (m < 0x100 ? scm_masktab[m] : (m < 0x10000 ? scm_masktab[m >> 8] << 8 | 0xff : (m < 0x1000000 ? scm_masktab[m >> 16] << 16 | 0xffff : scm_masktab[m >> 24] << 24 | 0xffffff))); +} + +scm_t_uint32 +scm_c_random (scm_t_rstate *state, scm_t_uint32 m) +{ + scm_t_uint32 r, mask = scm_i_mask32 (m); while ((r = state->rng->random_bits (state) & mask) >= m); return r; } +scm_t_uint64 +scm_c_random64 (scm_t_rstate *state, scm_t_uint64 m) +{ + scm_t_uint64 r; + scm_t_uint32 mask; + + if (m <= SCM_T_UINT32_MAX) + return scm_c_random (state, (scm_t_uint32) m); + + mask = scm_i_mask32 (m >> 32); + while ((r = ((scm_t_uint64) (state->rng->random_bits (state) & mask) << 32) + | state->rng->random_bits (state)) >= m) + ; + return r; +} + /* SCM scm_c_random_bignum (scm_t_rstate *state, SCM m) @@ -377,17 +398,8 @@ SCM_DEFINE (scm_random, "random", 1, 1, 0, return scm_from_uint32 (scm_c_random (SCM_RSTATE (state), (scm_t_uint32) m)); #elif SCM_SIZEOF_UNSIGNED_LONG <= 8 - if (m <= SCM_T_UINT32_MAX) - return scm_from_uint32 (scm_c_random (SCM_RSTATE (state), - (scm_t_uint32) m)); - else - { - scm_t_uint64 upper, lower; - - upper = scm_c_random (SCM_RSTATE (state), (scm_t_uint32) (m >> 32)); - lower = scm_c_random (SCM_RSTATE (state), SCM_T_UINT32_MAX); - return scm_from_uint64 ((upper << 32) | lower); - } + return scm_from_uint64 (scm_c_random64 (SCM_RSTATE (state), + (scm_t_uint64) m)); #else #error "Cannot deal with this platform's unsigned long size" #endif diff --git a/libguile/random.h b/libguile/random.h index 512b7d2..2f1f0f6 100644 --- a/libguile/random.h +++ b/libguile/random.h @@ -67,6 +67,7 @@ SCM_API double scm_c_uniform01 (scm_t_rstate *); SCM_API double scm_c_normal01 (scm_t_rstate *); SCM_API double scm_c_exp1 (scm_t_rstate *); SCM_API scm_t_uint32 scm_c_random (scm_t_rstate *, scm_t_uint32 m); +SCM_API scm_t_uint64 scm_c_random64 (scm_t_rstate *state, scm_t_uint64 m); SCM_API SCM scm_c_random_bignum (scm_t_rstate *, SCM m); -- tg: (7387c23..) t/random64-fix-2 (depends on: master) --=-=-= > Would you be interested in doing this? We would need some test > suites too, I think, and possibly changes to the scm_t_rng structure. > Sorry, I don't have the inclination to work on this ATM. Also, random number tests are kinda hard to write -- it's random stuff, after all :-). Regards, Rotty -- Andreas Rottmann -- --=-=-=--