| Related sites for http://www.fourmilab.ch/random/ |
| Black_Passion_Graphics Offers graphics and web design, plus free ordering and receiving. Subjects include wrestlers, actors, and singers. | | Tcady_Clipart Original parrot and unicorn clipart by Tiffany Cady. | | Less_Tech_Inc_ Offering new, used and refurbished notebook and laptop computers. | | Bizi_International_Inc_ Reseller of used and refurbished networking equipment including routers and switches from manufacturers including Cisco, Juniper, and Extreme Neworks. | | Prehtml_com Offers preHTML, a preprocessing tool. Beta version available for download. | | lsof lists open files (ftp site) | | Orca_Logic_Ltd_ Specialist memory upgrade supplier for workstations, servers, PCs, laptops and printers. | | Success_Partners Great Plains reseller offers consulting and training services. | | XSLT_and_XPath_Quick_Reference Quick reference card developed by Mulberry Technologies in PDF format | | Custom_JSP_and_Servlet_Training_Courses Hands-on servlet and JavaServer Pages training, available on-site. | | RAMCO_Software_Training Delivers hands on, instructor led training in Windows, MS Office and other desktop applications. Located in Washington, United States. | | DMS_Software_Reengineering_Toolkit Generalized compiler technology for custom parsing, analyzing, transforming, and prettyprinting computer languages, including C, C++, COBOL, Ada, Java, C#, SQL. Tasks range from metrics to migrations | | The_manual_Page__PHP The bases of the language, how to use PHP with a MySQL database or an Oracle database, examples. | | PhilDomain Domain name registration, email forwarding and URL forwarding. | | RFC_2875 Diffie-Hellman Proof-of-Possession Algorithms. H. Prafullchandra, J. Schaad. July 2000. | | Juxta_Digital A professional services firm defining strategy and providing development for web, wireless, broadband, desktop, and other new media. | | Website_For_Success Services include web site construction, hosting, content updates, domain registration and search engine submission. Dayton Ohio | | GS_Inc_ Web design firm offering e-commerce, domain name registration, and hosting. | | Harmony_Design Offers branding, graphics, hosting, and e-commerce solutions. Located in La Quinta, California. | | ADTMag__CORBA_State_of_the_Union Article provides information on the background to CORBA, where CORBA can be found today and standards activities. By Charlotte Wales, Fred Waskiewicz. (August 29, 2003) |
|
Pseudorandom Number Sequence Test Program a:link, a:visited { background-color: inherit; color: rgb(0%, 0%, 80%); text-decoration: none; } a:hover { background-color: rgb(30%, 30%, 100%); color: rgb(100%, 100%, 100%); } a:active { color: rgb(100%, 0%, 0%); background-color: rgb(30%, 30%, 100%); } a.i:link, a.i:visited, a.i:hover { background-color: inherit; color: inherit; text-decoration: none; } blockquote.rights { text-align: justify; font-size: smaller; font-family: sans-serif; } body { background-color: #FFFFFF; color: #000000; margin-left: 15%; margin-right: 10%; } dl.options dt { margin-top: 1ex; } h1.title, h2.title { margin-bottom: 0px; text-align: center; } .options dt { margin-top: 1ex; padding-bottom: 0px; } .options dd, .options p { margin-top: 0px; } img.border0 { border: 0px; } p,dd, li, blockquote, td { text-align: justify; } p.byline { margin-top: 0px; text-align: center; } table.footer { width: 100%; } table.footer td.left { width: 50%; text-align: left; font-style: italic; vertical-align: top; } table.footer td.right { width: 50%; text-align: right; vertical-align: top; } table.footer table.buttons { margin-left: auto; } table.footer table.buttons td { text-align: center; }
A Pseudorandom Number Sequence Test ProgramThis page describes a program, ent, which applies varioustests to sequences of bytes stored in files and reports the results ofthose tests. The program is useful for evaluating pseudorandomnumber generators for encryption and statistical samplingapplications, compression algorithms, and other applications where theinformation density of a file is of interest.NAME ent - pseudorandom number sequence testSYNOPSIS ent [ -b -c -f -t -u ] [ infile ]DESCRIPTIONent performs a variety of tests on the stream ofbytes in infile (or standard input if no infileis specified) and produces output as follows on the standardoutput stream: Entropy = 7.980627 bits per character. Optimum compression would reduce the size of this 51768 character file by 0 percent. Chi square distribution for 51768 samples is 1542.26, and randomly would exceed this value less than 0.01 percent of the times. Arithmetic mean value of data bytes is 125.93 (127.5 = random). Monte Carlo value for Pi is 3.169834647 (error 0.90 percent). Serial correlation coefficient is 0.004249 (totally uncorrelated = 0.0).The values calculated are as follows:EntropyThe information density of the contents of the file, expressed as a number of bits per character. The results above, which resulted from processing an image file compressed with JPEG, indicate that the file is extremely dense in information—essentially random. Hence, compression of the file is unlikely to reduce its size. By contrast, the C source code of the program has entropy of about 4.9 bits per character, indicating that optimal compression of the file would reduce its size by 38%. [Hamming, pp. 104–108]Chi-square TestThe chi-square test is the most commonly used test for the randomness of data, and is extremely sensitive to errors in pseudorandom sequence generators. The chi-square distribution is calculated for the stream of bytes in the file and expressed as an absolute number and a percentage which indicates how frequently a truly random sequence would exceed the value calculated. We interpret the percentage as the degree to which the sequence tested is suspected of being non-random. If the percentage is greater than 99% or less than 1%, the sequence is almost certainly not random. If the percentage is between 99% and 95% or between 1% and 5%, the sequence is suspect. Percentages between 90% and 95% and 5% and 10% indicate the sequence is “almost suspect”. Note that our JPEG file, while very dense in information, is far from random as revealed by the chi-square test. Applying this test to the output of various pseudorandom sequence generators is interesting. The low-order 8 bits returned by the standard Unix rand() function, for example, yields: Chi square distribution for 500000 samples is 0.01, and randomly would exceed this value more than 99.99 percent of the times. While an improved generator [Park & Miller] reports: Chi square distribution for 500000 samples is 212.53, and randomly would exceed this value 97.53 percent of the times. Thus, the standard Unix generator (or at least the low-order bytes it returns) is unacceptably non-random, while the improved generator is much better but still sufficiently non-random to cause concern for demanding applications. Contrast both of these software generators with the chi-square result of a genuine random sequence created by timing radioactive decay events. Chi square distribution for 500000 samples is 249.51, and randomly would exceed this value 40.98 percent of the times. See [Knuth, pp. 35–40] for more information on the chi-square test. An interactive chi-square calculator is available at this site.Arithmetic MeanThis is simply the result of summing the all the bytes (bits if the -b option is specified) in the file and dividing by the file length. If the data are close to random, this should be about 127.5 (0.5 for -b option output). If the mean departs from this value, the values are consistently high or low.Monte Carlo Value for PiEach successive sequence of six bytes is used as 24 bit X and Y co-ordinates within a square. If the distance of the randomly-generated point is less than the radius of a circle inscribed within the square, the six-byte sequence is considered a “hit”. The percentage of hits can be used to calculate the value of Pi. For very large streams (this approximation converges very slowly), the value will approach the correct value of Pi if the sequence is close to random. A 500000 byte file created by radioactive decay yielded: Monte Carlo value for Pi is 3.143580574 (error 0.06 percent).Serial Correlation CoefficientThis quantity measures the extent to which each byte in the file depends upon the previous byte. For random sequences, this value (which can be positive or negative) will, of course, be close to zero. A non-random byte stream such as a C program will yield a serial correlation coefficient on the order of 0.5. Wildly predictable data such as uncompressed bitmaps will exhibit serial correlation coefficients approaching 1. See [Knuth, pp. 64–65] for more details.OPTIONS-b The input is treated as a stream of bits rather than of 8-bit bytes. Statistics reported reflect the properties of the bitstream.-c Print a table of the number of occurrences of each possible byte (or bit, if the -b option is also specified) value, and the fraction of the overall file made up by that value. Printable characters in the ISO 8859-1 Latin-1 character set are shown along with their decimal byte values. In non-terse output mode, values with zero occurrences are not printed.-f Fold upper case letters to lower case before computing statistics. Folding is done based on the ISO 8859-1 Latin-1 character set, with accented letters correctly processed.-t Terse mode: output is written in Comma Separated Value (CSV) format, suitable for loading into a spreadsheet and easily read by any programming language. See Terse Mode Output Format below for additional details.-u Print how-to-call information.FILES If no infile is specified, ent obtains its input from standard input. Output is always written to standard output.TERSE MODE OUTPUT FORMATTerse mode is selected by specifying the -t optionon the command line. Terse mode output is written inComma Separated Value (CSV) format, which can be directlyloaded into most spreadsheet programs and is easily readby any programming language. Each record in the CSVfile begins with a record type field, which identifiesthe content of the following fields. If the -coption is not specified, the terse mode output willconsist of two records, as follows:0,File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation1,file_length,entropy,chi_square,mean,Pi_value,correlationwhere the italicised values in the type 1 record are thenumerical values for the quantities named in the type 0column title record. If the -b option is specified, the secondfield of the type 0 record will be “File-bits”, andthe file_length field in type 1 record will be givenin bits instead of bytes. If the -c option is specified,additional records are appended to the terse mode output whichcontain the character counts:2,Value,Occurrences,Fraction3,v,count,fraction. . .If the -b option is specified, only two type 3 records willappear for the two bit values v=0 and v=1.Otherwise, 256 type 3 records are included, one for eachpossible byte value. The second field of a type 3 recordindicates how many bytes (or bits) of value vappear in the input, and fraction gives the decimalfraction of the file which has value v (which isequal to the count value of this record divided bythe file_length field in the type 1 record).BUGS Note that the “optimal compression” shown for the file is computed from the byte- or bit-stream entropy and thus reflects compressibility based on a reading frame of the chosen width (8-bit bytes or individual bits if the -b option is specified). Algorithms which use a larger reading frame, such as the Lempel-Ziv [Lempel & Ziv] algorithm, may achieve greater compression if the file contains repeated sequences of multiple bytes. Download random.zip (Zipped archive)
The program is provided as random.zip, a Zipped archive containing an ready-to-run Win32 command-line program, ent.exe (compiled using Microsoft Visual C++ .NET, creating a 32-bit Windows executable), and in source code form along with a Makefile to build the program under Unix.SEE ALSO Introduction to Probability and Statistics[Hamming] Hamming, Richard W. Coding and Information Theory. Englewood Cliffs NJ: Prentice-Hall, 1980.[Knuth] Knuth, Donald E. The Art of Computer Programming, Volume 2 / Seminumerical Algorithms. Reading MA: Addison-Wesley, 1969. ISBN 0-201-89684-2.[Lempel & Ziv] Ziv J. and A. Lempel. “A Universal Algorithm for Sequential Data Compression”. IEEE Transactions on Information Theory 23, 3, pp. 337-343.[Park & Miller] Park, Stephen K. and Keith W. Miller. “Random Number Generators: Good Ones Are Hard to Find”. Communications of the ACM, October 1988, p. 1192. This software is in the public domain. Permission to use, copy, modify, and distribute this software and its documentation for any purpose and without fee is hereby granted, without any conditions or restrictions. This software is provided “as is” without express or implied warranty.by John WalkerJanuary 28th, 2008   Fourmilab Home Page |
|
