Browse Prior Art Database

Software Pseudo Random Number Generator without Replacement

IP.com Disclosure Number: IPCOM000108703D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 77K

Publishing Venue

IBM

Related People

Heisch, RR: AUTHOR

Abstract

A software algorithm is described to generate pseudo-random numbers without replacement (i.e., that are not repeated).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Software Pseudo Random Number Generator without Replacement

       A software algorithm is described to generate
pseudo-random numbers without replacement (i.e., that are not
repeated).

      Existing software random number generators, such as the linear
congruential method, etc., can provide quick and fairly efficient
generation of a pseudo-random sequence of numbers.  The generated
sequence, however, is a sampling with replacement, i.e., a particular
number may be repeated several times in sequence.  To provide a
sequence without replacement so that a number will never be repeated
(until, of course, the entire sequence repeats as is typical with
these methods), a pseudo-random number generator is typically used in
conjunction with an array that marks particular numbers as having
been generated so as to avoid duplicating the sequence.  This method
works fine until the desired size of the sequence becomes large.
When this occurs, the size of the array becomes prohibitively large
(1/2 GB bit array for a 32-bit sequence) and the time to generate a
number will vary rather non-deterministically across the sequence
when random multiple collisions occur, etc.

      The technique described here utilizes an existing hardware
solution - the Linear Feedback Shift Register (LFSR).  This very
simple hardware circuit is commonly used for state machine
implementations, hardware random number generators for test pattern
generation, etc.  It consists of XOR gates and latches which
implement a specific polynomial divisor algorithm that guarantees a
non-repeating pseudo-random sequence.

      This hardware technique, with a few modifications, can be
implemented in software as an alternative to the random generator and
memory array method described above.  This method will provide...