Random numbers - the most heavily used integer sequences.

Thu Jun 24 23:03:29 CEST 2004

SeqFans,

although "random"-looking sequences are considered to be "uninteresting"
by a majority of us, there are some special "random" sequences that are
of extreme practical importance. The deterministic outputs of popular
pseudo-random number generators are probably used millions of times
every day, either in Monto-Carlo simulations or even more frequently in
computer games, making them probably the "most heavily used integer
sequences".

See e.g. the recent article "Generating random numbers" by Eric Uner in
http://www.embedded.com/showArticle.jhtml?articleID=20900500

I'm currently preparing a collection of sequences representing the
actual behavior of (pseudo-) random number generators of a few compilers
or system libraries of computers to which I have access. Most of them
have a default starting point (e.g. 0 or 1) which is used if no explicit
initialization is applied. Most of the older generators are of the
linear congruential type
x(1)=..., x(n)= ( a * x(n-1) + b ) mod m.

There is a table in Knuth's Vol.2, page 106 "Random Numbers / The
Spectral Test" (Table 1) that gives parameters and spectral behavior for
a lot of generators with b=0. I'll try to include also the sequences for
the "winners" in Knuth's assessment. A on-line collection of many
generators is found in the Postscript file
http://random.mat.sbg.ac.at/ftp/pub/data/genacpc.ps , including many
references.

A few examples:

------------------------------------------------------------
The internal state of Digital Fortran RAN, Period 2^32
a(1)=0, a(n) = (69069 * a(n-1) + 1) mod 2^32

0 1 69070 475628535 3277404108 772999773 3877832058 3821835443
1662200408 
2044158073 3788989926 797919023 2743624612 1156259413 1059494674
584849259  
786050992 3369345009 3077427454 1200308583 2654771836 1692139853
4052415402
1850655011 369258504 799809129 147369750 3903738527 2154380372
1755943749  

--------------------------------------------------------
Microsoft's Visual C++: Period 2^32

Internal state:
a(1)=0, a(n)=(a(n-1) * 214013 + 2531011) mod 2**32

0 2531011 505908858 3539360597 159719620 2727824503 773150046 548247209 
2115878600 2832368235 2006221698 2531105853 3989110284 2222380191 
2165923046 1345953809 1043415696 586225427 3870123402 2343900709
3109564500 
3522190791 2090033518 3566711417 3845303128 3357146299 2234209426
4040255757

Output derived from this sequence b(n):
a(n)= (floor(b(n)/65536)) mod 32768)

0 38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142
281 20537 15921 8945 26285 2997 14680 20976 31891 21655 25906 18457 1323
28881 2240 9725 32278 2446 590 840 18587 16907 21237 23611 12617 12456
867 29533 6878 28223 17887 31597 20584 12212 31111 7578 17066

-------------------------------------------------
Brian W Kernighan, Dennis M. Ritchie, The C Programming Language
(Second Edition) Prentice Hall Software Series, 1988

describe the generator
a(1)=1, a(n) = (1103515245 * a(n-1) + 12345) mod 2^31
plus range reduction to 15 bit
which is used in many popular C compilers / libraries

VAX C, BSD omit the range reduction
Function rand() in the Standard C library  Period 2^31 (some UNIX
manuals
erroneously give period 2^32)

C Program:
#include stdio
#include stdlib
main ()
{int i, j;
for (i=1; i<50; i++)
{ j = rand (); printf ("%d\n", j);}
}

1 1103527590 377401575 662824084 1147902781 2035015474 368800899
1508029952
486256185 1062517886 267834847 180171308 836760821 595337866 790425851
2111915288 1149758321 1644289366 1388290519 1647418052 1675546029
1767274722 326272115 1343201072 675780521 744964398 1969681615
1116175964
861472101 1303003706 1686638315 2000430152 1868141281 1860847622
1448521415

----------------------------------------------------
A K&R-compliant C compiler will use

x(1)=1, x(n)=(1103515245 * x(n-1) + 12345) mod 2^31
internally and convert this to a 15 bit output
a(n)= (floor(x(n)/65536)) mod 32768)

in C (WATCOM C ( http://www.openwatcom.org/ )compiler source code):
unsigned long     *randptr;
....
*randptr = *randptr * 1103515245 + 12345;
        return( (int)( (*randptr >> 16) & 0x7FFF ) );

0 21468 9988 22117 3498 16927 16045 19741 12122 8410 12261 27052 5659
9758
21087 25875 32368 26233 15212 17661 20496 8191 23065 23471 32096 10781
14596
23212 24244 5661 514 25643 1350 19576 8051 18234 16882 13023 5983 21166
23479
9992 31833 27345 12782 23097 4112 19915 17992 22933 29621 13004 27273
20265

-------------------------------------------------------

if the initialization a(1)=1 proposed in Kernighan/Ritchie is omitted,
a(1)=0 and the internal sequence becomes

0 12345 1406932606 654583775 1449466924 229283573 1109335178 1051550459
1293799192
794471793 551188310 803550167 1772930244 370913197 639546082 1381971571
1695770928 2121308585 1719212846 996984527 1157490780 1343235941
536853562
1511588075 1538207304 2103497953 706568710 956612807 1521280756
1588911645

-----------------------------------------------
The Watcom Fortran Function URAND:

a(1)=0 a(n) = ( 2147437301 * a(n-1) + 453816693 ) mod 2^31

0 453816693 2013878382 1461722811 653338732 1830525137 1741773690
526418231
109789464 1577774445 1454795974 1716389619 180917764 1381854025 70154322
301698031 2068689712 1594166885 1923590686 579939371 2056610972
914297537
1800695338 1283998631 2036119112 1462760541 1949790326 1780969059
709817396

-----------------------------------------------
RNUN from the IMSL-Library (now IMSL provides a whole battery of RNGs in
IMSL)
a(1)=1, a(n) = 7^5 * a(n-1) mod (2^31-1)
1 16807 282475249 1622650073 984943658 1144108930 470211272 101027544
1457850878 1458777923 2007237709 823564440 1115438165 1784484492
74243042
114807987 1137522503 1441282327 16531729 823378840 143542612 896544303
1474833169 1264817709 1998097157 1817129560 1131570933 197493099
1404280278

-----------------------------------------------
The seriously deficient generator "RANDU" in the IBM Scientific
Subroutine
Library of the 1960s. It gave the famous textbook example for
"pseudo" random numbers fall mainly in the planes", because
there is a very simple relationship
9*a(n-2)-6*a(n-1)+a(n) = 0 mod 2^31
between 3 consecutive output terms.

a(1)=1, a(n) = 65539*a(n-1) mod 2^31 = 65539*a(n-1) mod 2^29

Marsaglia, G. (1968), Random numbers fall mainly in the planes,
Proceedings of the National Academy of Sciences, 61, 25-28.

Java applet demonstrating random number generation with the
Linear Congruential Method (visualization of deficient behavior):

http://www.cs.pitt.edu/~kirk/cs1501/animations/Random.html

Output of RANDU
1 65539 393225 1769499 7077969 26542323 95552217 334432395 1146624417
1722371299 14608041 1766175739 1875647473 1800754131 366148473
1022489195
692115265 1392739779 2127401289 229749723 1559239569 845238963
1775695897
899541067

Digital Fortran RANDU:
For backward compatibility with legacy IBM mainframes Digital Equipment
provided a RANDU implementation, which indeed (implicitely) uses the
same
internal state sequence:

1 65539 393225 1769499 7077969 26542323 95552217 334432395 1146624417
1722371299 14608041 1766175739 1875647473 1800754131 366148473 
1022489195 692115265 1392739779 2127401289 229749723 1559239569
845238963  
1775695897 899541067 153401569 1414474403 663781353 1989836731
1670020913  
701529491 2063890617 1774610987 662584961 888912771 1517695625
1105958811

=================================
I'll try to get more information on existing generators. Does anyone
know
if the generator
a(n)=44485709377909 * a(n-1) mod 2^48 (printed in Table 1 TAOCP Vol2 p
106: 2^46,
text p108 says 2^48) was really in use on CRAY systems?

1 44485709377909 232253848878969 94800993741645 243522309605169
20783065360997
154093299791145 161954398135485 183663036741473 207319719370837
142356556532697
278312552510253 242082341486737 37630394630981 176334633251721
233894773868189
84667698696897 206597894751029 129041734818873 100725643677453
185225226739185

Modern systems start to abandon the simple one step linear congruential
generators in favor of other more sophisticated and statistically less
vulnerable algorithms, e.g. combinations of several generators, more
internal memory, Fibonacci type generators etc.

Any comments are welcome

Hugo Pfoertner