From: Neil Ludban <stu3168 AT austin DOT onu DOT edu>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: Fast random number generator
Date: Tue, 15 Jul 1997 10:19:37 -0400
Organization: Ohio Northern University
Lines: 40
Message-ID: <Pine.A32.3.96.970715092629.31965B-100000@austin.onu.edu>
References: <33C91424 DOT 7615 AT wanadoo DOT fr>
NNTP-Posting-Host: austin.onu.edu
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
In-Reply-To: <33C91424.7615@wanadoo.fr>
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Precedence: bulk

On Sun, 13 Jul 1997, Alan Poppleton wrote:

> I need a fast and simple algorithm which can produce a fairly random 
> number given two seeds - x and y.  Any ideas?  It MUST be SIMPLE and 
> FAST and it only needs to return a number between 0 and 15.
> 

There seems to be a confusion of ideas here.  First, random number
generators produce _sequences_ of numbers that appear to be random.  Where
the sequence starts is determined by the initial state, or seed.  Each
time a new number is produced, the state is modified, and eventually the
state returns back to where it started, and the sequence is repeated.

Using two seeds to produce _a_ number will not be random.  Every time you
use the same seeds, you will get the same 'random' number.  The best you
can do is find an algorithm that avoids any patterns in the seeds x and y
(for example, ((x + y) % 16) would produce obvious patterns if you used it
to color pixels in a plane). 

You are worried about speed, which implies that you will be producing
sequences.  If you must use x and y every time, try to stick with
addition, subtraction, bit shifting, and xor-ing, with a final % 16 at the
end.  The easiest thing would be to use the random library in C.  Another
thing you could try is to use x and y to modify the state of a regular
generator before getting the next random number (this is just as likely to
break the randomness as create it).

For more info on random numbers, theories, analysis of algorithms, and
some sample code, take a look at

http://euclid.ucsd.edu/~kschneid/spring104/

hope this helps.

	--Neil

====================
Neil Ludban
n-ludban AT onu DOT edu