Commit [436b2a] Maximize Restore History

Better equidistributed and faster/less consing integer RANDOM.

Up to now the implementation of RANDOM with an integer argument just
generated a few more random bits than the length of the argument and
took this value MOD the argument. This led to a slightly uneven
distribution of the possible values unless the argument was a power of
two. Moreover, for bignums, the algorithm was quadratic both in time and
space dependent on the number of bits of the argument.

Instead generate random integers using an accept-reject loop and change
the bignum implementation to an algorithm that is linear in time and
space.

I took some inspiration from WHN's attempt at an accept-reject loop
implementation in commit 0a7604d54581d2c846838c26ce6a7993629586fa and
following.

Thanks to Christophe Rhodes for reviewing this patch!

Some details:

The implementation works correctly with both a random chunk size equal
to the word size and equal to half the word size. This is currently
necessary as a 32-bit pseudo random generator is used both under 32 and
under 64 bit word size.

In the generic RANDOM case, fixnum and bignum limits are differentiated:

With a fixnum limit an accept-reject loop on a masked random chunk is
always used. Under 64 bit word size two random chunks are used only if
the limit is so large that one doesn't suffice. This never conses.

With a bignum limit four cases are differentiated to minimize consing.
If just one random chunk is needed to supply a sufficient number of bits
the implementation only conses if the result is indeed a bignum:
* If the limit is a power of two, a chunk is generated and shifted to
get the correct number of bits.
* If the limit is not a power of two an accept-reject loop with shifting
is used.
If more than one random chunk is needed, a bignum is always consed even
if it happens to normalize to a fixnum:
* If the limit is a power of two a straightforward algorithm is used to
fill a newly created bignum with random bits.
* If the limit is not a power of two an accept-reject loop is used that
detects rejection early by starting from the most significant bits,
thus generating on the average only one random chunk more than needed
to fill the result once.
The test for power of two is non-consing, too.

In the case of a compile-time constant integer argument (of at most word
size) a DEFTRANSFORM triggers, that, in the general case, compiles an
accept-reject loop. For values of the limit where this sufficiently
reduces the rejection probability the largest multiple of the limit
fitting in one or two random chunks is used instead inside the loop.
To bring the result in the correct range a division is then necessary
(which the compiler converts into a multiplication). Powers of two are
optimized by leaving out the rejection test. In those cases where a word
has more bits than a random chunk, the generated expression uses two
chunks only if necessary.

Lutz Euler Lutz Euler 2012-05-01

added src/code/bignum-random.lisp
changed src/code/random.lisp
changed src/code/target-random.lisp
changed src/compiler/float-tran.lisp
changed tests/random.pure.lisp
changed NEWS
changed build-order.lisp-expr
changed package-data-list.lisp-expr
src/code/bignum-random.lisp Diff Switch to side-by-side view
Loading...
src/code/random.lisp Diff Switch to side-by-side view
Loading...
src/code/target-random.lisp Diff Switch to side-by-side view
Loading...
src/compiler/float-tran.lisp Diff Switch to side-by-side view
Loading...
tests/random.pure.lisp Diff Switch to side-by-side view
Loading...
NEWS Diff Switch to side-by-side view
Loading...
build-order.lisp-expr Diff Switch to side-by-side view
Loading...
package-data-list.lisp-expr Diff Switch to side-by-side view
Loading...