From 4a9d763799c3f0b3c17182b44e8497e174547120 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Mon, 18 Jan 2016 06:27:52 -0800 Subject: 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. --- tests/013/maze.expected | 118 ++++++++++++++++++++++++------------------------ 1 file changed, 59 insertions(+), 59 deletions(-) (limited to 'tests') diff --git a/tests/013/maze.expected b/tests/013/maze.expected index f0a09770..e3cbbf80 100644 --- a/tests/013/maze.expected +++ b/tests/013/maze.expected @@ -1,61 +1,61 @@ + +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ -| | | | | | | -| | | | | | | -+ + + + +----+----+----+----+ + + + + +----+----+----+ + +----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+----+ + + +----+ +----+ +----+----+ +----+----+ +----+ +----+----+ +----+ -| | | | | | | | | | | -| | | | | | | | | | | -+----+----+ + + +----+ +----+----+ + +----+----+----+----+----+ +----+----+ + -| | | | | | | | | | | -| | | | | | | | | | | -+ + + +----+----+----+ + +----+----+ + +----+ + + + + +----+----+ -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+----+ +----+ +----+----+----+ + + + +----+ +----+----+ + + + -| | | | | | | | | | | -| | | | | | | | | | | -+----+----+ + + +----+ +----+ + +----+ + + +----+----+----+----+ + + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+----+----+ +----+----+ + +----+ + + + + + +----+ + + + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ + + + +----+ + +----+----+----+----+ +----+ + + + +----+----+----+ -| | | | | | | | | | -| | | | | | | | | | -+ +----+----+----+----+----+----+----+----+ + +----+----+----+ +----+ +----+----+ + -| | | | | | | | -| | | | | | | | -+ + + +----+----+----+----+ +----+ +----+ +----+ +----+----+----+ +----+ + -| | | | | | | | | | | | | -| | | | | | | | | | | | | -+ +----+----+----+ + + +----+ +----+ +----+ + + + + +----+ + + -| | | | | | | | | | | -| | | | | | | | | | | -+----+ + + +----+----+ +----+ + +----+ +----+----+----+----+----+ +----+ + -| | | | | | | | | | | | -| | | | | | | | | | | | -+ + +----+ + +----+----+ +----+ + +----+ + + + +----+----+ + + -| | | | | | | | | -| | | | | | | | | -+ + +----+----+----+----+----+----+ +----+----+----+----+----+----+----+ + +----+ + -| | | | | | | | | -| | | | | | | | | -+ + +----+----+ +----+ +----+----+ + + + + +----+ + +----+----+ + -| | | | | | | | | | | | | | | -| | | | | | | | | | | | | | | -+----+ + + +----+ +----+ + + +----+----+ +----+ +----+----+ + + + -| | | | | | | | | | | -| | | | | | | | | | | -+ +----+ +----+ +----+----+ + +----+----+ +----+----+----+----+ +----+----+ + -| | | | | | | | | | -| | | | | | | | | | -+----+----+ + +----+ + +----+----+ +----+----+----+----+ + +----+ + +----+ -| | | | | | | | | | | | -| | | | | | | | | | | | -+ + + + + +----+----+----+ +----+----+----+----+ + +----+ + + + + -| | | | | | | -| | | | | | | +| | | | | | | | | +| | | | | | | | | ++ + + + +----+ + + + +----+ + +----+----+ + + +----+ +----+ +| | | | | | | | | | | | +| | | | | | | | | | | | ++----+----+----+----+ + +----+----+----+----+----+ +----+ + +----+ +----+----+ + +| | | | | | | | | +| | | | | | | | | ++ +----+ + + + +----+ +----+----+ +----+ + +----+ +----+ +----+ + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ +----+----+----+----+ + +----+----+ +----+ + + + +----+----+----+ +----+ +| | | | | | | | | | | +| | | | | | | | | | | ++----+----+ + + +----+ + +----+----+ + + +----+----+----+ + + + + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ +----+ + +----+----+----+ + + + +----+ +----+ + +----+ + + + +| | | | | | | | | | | | | +| | | | | | | | | | | | | ++ + +----+ + +----+ +----+----+ +----+ + + +----+----+ +----+----+----+ +| | | | | | | | | | | | +| | | | | | | | | | | | ++ +----+ +----+----+ +----+ + + + +----+ + +----+----+----+ + + + +| | | | | | | | | | | | +| | | | | | | | | | | | ++ + +----+ + +----+ + +----+----+----+ +----+----+ +----+ + + + + +| | | | | | | | | | | | | | +| | | | | | | | | | | | | | ++----+ + + +----+ +----+----+ +----+ + + + +----+----+ +----+----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+----+----+ +----+----+ +----+ + + + +----+----+ + + +----+----+ +| | | | | | | | +| | | | | | | | ++ +----+ +----+----+----+----+----+ +----+----+ + +----+----+----+----+----+----+ + +| | | | | | | | | | +| | | | | | | | | | ++ + +----+ + +----+ + +----+----+----+----+ + +----+ +----+ + +----+ +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+ +----+----+ +----+ +----+----+ + +----+----+ +----+ +----+----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++----+----+ + + + + +----+ +----+----+----+ + + +----+----+----+ +----+ +| | | | | | | | | | +| | | | | | | | | | ++ +----+----+ +----+----+----+----+----+----+ + +----+----+----+ +----+ + +----+ +| | | | | | | | | +| | | | | | | | | ++----+ + + +----+ + +----+----+----+ +----+ + + +----+----+ +----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+ +----+----+----+----+----+----+ + +----+----+----+ + +----+----+----+ + +| | | | | | | | | | | +| | | | | | | | | | | ++ +----+----+----+ + +----+ +----+ +----+----+ + + + + + + + + +| | | | | | | +| | | | | | | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ + -- cgit v1.2.3