Random numbers broken on 64-bit platforms

Random numbers broken on 64-bit platforms

[Andreas Rottmann]

[-- Attachment #1: Type: text/plain, Size: 561 bytes --]

Hi!

While implementing SRFI-27, I noticed that Guile's RNG is quite broken
on 64-bit platforms (where unsigned long is 64 bit). This has two
consequences:

- Crashes for some numbers between 2^32 and 2^63; for example try this:

  (random (expt 2 46))

- Bignum random numbers will be seriously distorted in their
  distribution, since scm_c_random() only returns 32 random bits, and
  that function is used by scm_c_random_bignum(), which expects it to
  return a `unsigned long' worth of random bits, AFAICT.

I believe the attached patch fixes this issue.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fix-random-64bit.diff --]
[-- Type: text/x-diff, Size: 2375 bytes --]

From: Andreas Rottmann <a.rottmann@gmx.at>
Subject: Fix random number generator on 64-bit platforms

* libguile/random.c (scm_c_random): On platforms where `unsigned long' has 64
  bit, generate up to 64 bit of randomness. This is expected by
  scm_c_random_bignum(), and hence was a serious distortion of the random value
  distribution for values exceeding 2^32. This change also fixes a crash when
  the `m' argument is a value above 2^32.

---
 libguile/random.c |   28 +++++++++++++++++++++++++++-
 1 files changed, 27 insertions(+), 1 deletions(-)

diff --git a/libguile/random.c b/libguile/random.c
index 281d43a..1a9fd59 100644
--- a/libguile/random.c
+++ b/libguile/random.c
@@ -223,7 +223,8 @@ unsigned char scm_masktab[256];
 unsigned long
 scm_c_random (scm_t_rstate *state, unsigned long m)
 {
-  unsigned int r, mask;
+  unsigned long r, mask;
+#if SCM_SIZEOF_UNSIGNED_LONG == 4
   mask = (m < 0x100
 	  ? scm_masktab[m]
 	  : (m < 0x10000
@@ -232,6 +233,31 @@ scm_c_random (scm_t_rstate *state, unsigned long m)
 		? scm_masktab[m >> 16] << 16 | 0xffff
 		: scm_masktab[m >> 24] << 24 | 0xffffff)));
   while ((r = scm_the_rng.random_bits (state) & mask) >= m);
+#elif SCM_SIZEOF_UNSIGNED_LONG == 8
+  mask = (m < 0x100
+	  ? scm_masktab[m]
+	  : (m < 0x10000
+	     ? scm_masktab[m >> 8] << 8 | 0xff
+	     : (m < 0x1000000
+		? scm_masktab[m >> 16] << 16 | 0xffff
+                : (m < (1UL << 32)
+                   ? scm_masktab[m >> 24] << 24 | 0xffffff
+                   : (m < (1UL << 40)
+                      ? ((unsigned long) scm_masktab[m >> 32] << 32
+                         | 0xffffffffUL)
+                      : (m < (1UL << 48)
+                         ? ((unsigned long) scm_masktab[m >> 40] << 40
+                            | 0xffffffffffUL)
+                         : (m < (1UL << 56)
+                            ? ((unsigned long) scm_masktab[m >> 48] << 48
+                               | 0xffffffffffffUL)
+                            : ((unsigned long) scm_masktab[m >> 56] << 56
+                               | 0xffffffffffffffUL))))))));
+  while ((r = ((scm_the_rng.random_bits (state) << 32
+                | scm_the_rng.random_bits (state))) & mask) >= m);
+#else
+#error "Cannot deal with this platform's unsigned long size"
+#endif
   return r;
 }
 
-- 
tg: (3fdc1d0..) t/fix-random-64bit (depends on: master)

[-- Attachment #3: Type: text/plain, Size: 63 bytes --]


Regards, Rotty
-- 
Andreas Rottmann -- <http://rotty.yi.org/>

Re: Random numbers broken on 64-bit platforms

[Andreas Rottmann]

Andreas Rottmann <a.rottmann@gmx.at> writes:

> Hi!
>
> While implementing SRFI-27, I noticed that Guile's RNG is quite broken
> on 64-bit platforms (where unsigned long is 64 bit). This has two
> consequences:
>
> - Crashes for some numbers between 2^32 and 2^63; for example try this:
>
>   (random (expt 2 46))
>
> - Bignum random numbers will be seriously distorted in their
>   distribution, since scm_c_random() only returns 32 random bits, and
>   that function is used by scm_c_random_bignum(), which expects it to
>   return a `unsigned long' worth of random bits, AFAICT.
>
> I believe the attached patch fixes this issue.
>
I should add that this affects both 1.8.7 and current git.

Regards, Rotty
-- 
Andreas Rottmann -- <http://rotty.yi.org/>

Re: Random numbers broken on 64-bit platforms

[Andy Wingo]

On Fri 16 Jul 2010 15:54, Andreas Rottmann <a.rottmann@gmx.at> writes:

> While implementing SRFI-27, I noticed that Guile's RNG is quite broken
> on 64-bit platforms (where unsigned long is 64 bit).

Well, that is a particularly opaque piece of code, but I can't deny that
your patch does look right, and certainly improves the situation, so I'm
applying it. Would you mind contributing some test cases as well?
Thanks!

Andy
-- 
http://wingolog.org/