Lee.Sailer@CMU-CS-C.ARPA (04/06/85)
One problem with Turbo Pascal is that the random() functions fail even the simplest chi-square test. Have any numerical wizards out there got a good random number generator that will work in Turbo Pascal (z80)? Is there a better place to post this? thanks -------
ABN.ISCAMS@USC-ISID.ARPA (04/06/85)
Lee (et al), Needing a good random number generator myself, I scrounged around all OVER the nets and literature, and have about everything available out there. What I do NOT have is the training/knowledge/techniques to tell if ANY of them are truly any good! Various authoritative sources are quite free at warning how difficult it is to generate true random numbers (EVERYTHING is called "pseudo.."), but do darned little to provide a solution! I don't know enough about proper mathematical/logical testing to prove anything myself (and am sorely tried at this point, depending very much on random numbers on an encryption scheme I've been working on for 9 months now). Any methametical geniuses out there who can point me to NOT a long and deep discussion on the validity/nonvalidity of generation methods, but a clean SOLUTION!? Re the original query.. I can list what I DO have and maybe move it to you one way or another if you just want some code to play with. I just can't tell you if it's any GOOD or not! Regards, David Kirschbaum Toad Hall (ABN.ISCAMS@USC-ISID.ARPA)
GRUPP@mit-mc.ARPA (Paul R. Grupp) (04/06/85)
David, The differerence between random numbers and pseudo random numbers is that while pseudo random numbers APPEAR to be random, the same sequence of numbers will be generated each time the pseudo generator is run. This is of course due to the fact that the same code is being executed each time the program is run. A way to prevent this from happining it to SEED the pseudo generator with some truly random number from outside the program i.e. a number from the system clock or the number of clock ticks from a prompt to the reaction time to type something back to the prompt. If you need something that is truly random reguardless of seed even, then you may have to resort to a hardware hack such as the input from a ADC (analog to digital converter) with it's input comming from a "white noise generator". This would be truly random (make sure that the white noise generator is an analog device and not one of the newer "digitaly derived" generators). Hope this helps. Regards, Paul Grupp <GRUPP@MIT-MC.ARPA>
cuccia%ucbmiro@ucb-vax.ARPA (NickCoosh Cuccia) (04/08/85)
Hello out there...
Hope you don't mind if I toss out my fav'rit ref on random
number generators (oops! Pseudo-...). Check out V. 2 of Knuth's
_Art of Computer Programming_ for generation and testing methods.
I usually use the linear congruential method:
x = ax mod m
i+1 i
--------------
m
which gives numbers in the range [0..1). x sub i is the initial
seed, x sub (i+1) the seed used for the next call. Note: the
constants a and m should be relatively prime. An example function
written in Pascal is as follows. Another note: if a and m are
relatively prime then the period of the series generated will be
m.
--Nick Cuccia
--Computer Science Division,
--Dept. of Electrical Engineering and Computer Science,
--University of California-Berkeley
--cuccia%ucbmiro@Berkeley,
--{...}!ucbvax!cuccia
--cut here----cut here----cut here----cut here----cut here----cut here--
function Random(var x: integer): real;
const
A = 2047; (* = 2^11 - 1, a prime number *)
M = 524287; (* = 2^19 - 1, a prime number *)
begin (* random *)
x := (A*x) mod M; (* finding new seed value *)
Random := x / M; (* finding next number in series *)
end; (* function random *)ABRAMSOHN.WBST@XEROX.ARPA (04/08/85)
In writing game programs for the "KIDS", I use the internal clock counter locations in the computer to seed a nominal ramdon number generator. It appears to get rid of the Pseudo part of it, in that the system "never" starts at the same place. Hours*minutes*seconds*day*month*year kind of thing seems to do pretty good. Dennis
ssalzman.es@XEROX.ARPA (04/09/85)
I need a Modula-2 procedure to generate psuedo random numbers for an IBM PC. In general I need a good algorithm for any machine with 16 bit integers, that has a good long cycle life and uniform distribution (can be 'C' or Pascal). Also, does anyone have an algorithm to generate random numbers with a NORMAL distribution. If anyone has anything, please send it in the mail, I can't FTP from this account. Thanks in advance.... Isaac Salzman (SSalzman.ES@Xerox.ARPA)
dms@dciem.UUCP (Dave Sweeney) (04/10/85)
Nick Cuccia writes: > > > function Random(var x: integer): real; > > const > A = 2047; (* = 2^11 - 1, a prime number *) > M = 524287; (* = 2^19 - 1, a prime number *) > > begin (* random *) > x := (A*x) mod M; (* finding new seed value *) > Random := x / M; (* finding next number in series *) > end; (* function random *) While A (= 2047) and M (= 524287) are mutually prime (HCF = 1), which is all that is required for the algorithm, A is not a prime number: 2047 = 23 * 89 which will hopefully discourage 16-bit-machine users from using it for M (which must be prime for the series to have full period). Here at DCIEM we use an implementation of the generator described on p. 464 of Knuth's vol. 2, with k = 55, j = 31. As no multiplications or divisions are involved, it is reasonably fast. -- Dave Sweeney, DCIEM {allegra,ubc-vision,linus,ihnp4,uw-beaver,floyd}!utcsrgv!dciem!dms or {allegra,ihnp4,linus,decvax}!utzoo!dciem!dms
Eldridge.es@XEROX.ARPA (04/12/85)
This message describes several "linear congruential" random number
generators.
A characteristic of the linear congruential method is that the maximum
period is determined by the precision of arithmetic used. For example,
using 16-bit binary arithmetic, the maximum possible period is 65,535.
To make the period reasonably large, 32-bit binary arithmetic should be
used. The selection of the multiplier and constant also affect the
period and distribution of the random numbers. (For more on this refer
to Knuth, Semi-Numerical Algorithms)
Here is the random number generator from a Unix system. It runs on a
VAX which has 32 bit words.
/* @(#)rand.c 4.1 (Berkeley) 12/21/80 */
static long randx = 1;
srand(x)
unsigned x;
{
randx = x;
}
rand()
{
return((randx = randx * 1103515245 + 12345) & 0x7fffffff);
}
If you have real arithmetic available, you might want to try the
following random number generator. It generates a real in the range 0 <
n < 1. This one has a period of 1 million. It comes from the HP-67
library.
NewSeed := Frac(9821. * Seed + 0.211327)
Caution: be sure to avoid a starting seed equal to (1. - 0.211327)/9821.
That seed will produce a result of zero. This formula assumes that the
precision of the arithmetic is ten decimal digits or better.
Most random number generators produce uniformly distributed numbers.
Sometimes it is desirable to have normally (Gaussian) distributed
numbers. The following formula can be used to convert uniformly
distributed numbers into normally distributed numbers with a given mean
and standard deviation.
T = sqrt(-2*ln(rand1))*sin(360*rand2)
G = StdDev*T + Mean
where
rand1 : random number in the range 0 < n < 1
rand2 : another random number in the range 0 < n < 1
StdDev : standard deviation of desired distribution
Mean : mean of desired distribution
Reference
Knuth, Semi-Numerical Algorithms p. 104
The only drawback is that transcendental functions must be evaluated.
This can be speeded up at the expense of memory by the use of table
look-up.
George