random: wrong mask width for power-of-two moduli.

This mistake causes wasteful behavior for power-of-two
moduli in the random function, in both the bignum and
fixnum cases. For instance, the modulus 16 is taken
to be 17 bits wide. But we really want the width 16:
the number of bits needed for values in the range [0, 16).
The result isn't wrong, but the loop generates 17-bit
random numbers, and then throws away those which equal
or exceed the modulus, which is wasteful.

* mpi/mpi.c (mp_is_pow_two): New function.

* mpi/mpi.h (mp_is_pow_two): Declared.

* rand.c (random): In bignum case, after counting
bits in the modulus, subtract 1 if the modulus is a power
of two. In the fixnum case, subtract 1 from the modulus
and then count the bits in the reduced value.

* tests/013/maze.expected: regenerate due to different
prng behavior.

1 files changed, 2 insertions, 2 deletions

diff --git a/rand.c b/rand.c
index a2215124..fe3b6044 100644
--- a/rand.c
+++ b/rand.c
@@ -185,7 +185,7 @@ val random(val state, val modulus)
 
   if (bignump(modulus)) {
     mp_int *m = mp(modulus);
-    int bits = mp_count_bits(m);
+    int bits = mp_count_bits(m) - mp_is_pow_two(m);
     int rands_needed = (bits + 32 - 1) / 32;
     int msb_rand_bits = bits % 32;
     rand32_t msb_rand_mask = convert(rand32_t, -1) >> (32 - msb_rand_bits);
@@ -222,10 +222,10 @@ val random(val state, val modulus)
     return normalize(out);
   } else if (fixnump(modulus)) {
     cnum m = c_num(modulus);
-    int bits = highest_bit(m);
     if (m == 1) {
       return zero;
     } else if (m > 1) {
+      int bits = highest_bit(m - 1);
 #if SIZEOF_PTR >= 8
       int rands_needed = (bits + 32 - 1) / 32;
 #endif