 wrote:
> ostor wrote:
>
> > Nagyon egyszerűen, kb 100 C sorban megvalósítható pl a
>
> > Minimal standard random number generator
> > Linear Congruential Method, the "minimal standard generator" Park &
> > Miller, 1988, Comm of the ACM, 31(10), pp. 1192-1201
> >
> A forrást már egyszer felraktam a listára, ezért most csak az érdeklődőknek
> küldöm el.
huangpo wrote:
ostror, addig is amig megjön a source 1 kis olvasni való a "véletlenről"
:-)))))
Analyzing Pseudorandom Number Algorithms
-----------------------------------
Justin Dobbs  >
Abstract
The subject of randomness has long intrigued the scientific
community. Random number generators on microcomputers are the foundation
for many
applications, including cryptography and digital imaging. Quality in
random number generators is critical; on a small scale, a faulty random
number generator
can make a simple card game predictable. On a larger scale, the most
complex and "industrial-strength" cryptosystems may be rendered useless.
Three pseudorandom number algorithms (predetermined, universal
logic and calculation methods) were tested on the basis of even
distribution, lack of
sequence repetition, and speed. The algorithms were run for 100 trials
of 10,000 iterations each, with chi-square and z-score values calculated
at the end of
each trial and averaged at the end of the complete test. The C library
rand() function was rated best because of sequence quality and speed,
while the Mother of All Random Number Generators excelled at quality of
sequence but lacked speed. The R250
(ftp://ftp.uu.net/published/dr-dobbs/ddj9105.zip) algorithm was fast but
produced sequences lacking distribution uniformity.
Hypothesis
The R250 algorithm will likely be the best of the three in terms
of speed, while the Mother of All algorithm will excel at the tests for
randomness. The C
library's rand() function will fail both tests.
Introduction
The dawn of the computer age has given rise to many areas of
endeavor, one of which has been the development of new and more complex
encryption
schemes.
From the start it was clear that better, faster random numbers
were needed to fuel the encryption engines. Computers' mechanical,
predictable nature made truly random number impossible without an
external source of randomness, known as entropy. In order to be
efficient, however, computers needed a way of scrambling things up well
enough without entropy. This is where random number algorithms have fit
in.
When a computer generates a random number without an external
source of entropy (be it a Geiger counter or wind vane), the result is
referred to as being pseudorandom, since its randomness can always be
tested with similar numbers generated in sequence. This is the weakness
in computer generated random numbers; the numbers are part of a finite
sequence, and, given the starting (or seed) value, any number in the
sequence can be determined.
Testing for Randomness: A Statistical Approach
When one throws a die multiple times, each result has a
probability of 1/6, meaning that the possible outcomes are independent
of each other. If a 1 is the
result of only one throw and each number always comes up exactly once,
one might infer that the die is rigged. A good random number algorithm
generates an independent distribution of numbers that is consistent,
though not perfect.
......
itt statisztikai képek és a cikk de nem akartam mindet ide paste , see
@ URL http://max.jrd.com/rand/
......
Conclusion
Best is a relative term. The algorithm which is fastest may be the
most appropriate for a quick simulation, while the algorithm with fewest
repeat sequences but with less speed may be better-suited to an
encryption system. Here, the term best refers to a typical end-user
application, like a simple solitaire game.
From the results, one might conclude that the C library's rand()
function is the best choice overall. The quality of sequence is
comparable to the Mother of All algorithm, yet it is about as fast as
R250. R250 would be best suited for applications where quality of
sequence is not as important as blazing speed.
rand() may not be the best choice, however, because only its
interface to the program is common across operating systems; although it
is a standard
component of the C language, the underlying algorithm used in this test
is unique to the Linux operating system.
Several aspects of the algorithms went untested, notably
multimensional repetition and other subtle patterns in the sequence. The
testing protocol would
need to be modified to test such properties. Looking at distribution
quality, sequence repetition, and speed, however, provides a sound basis
for evaluation.
Further Reading
Deley, David W. Computer Generated Random Numbers, at
http://www.phantom.com/~dsharp/rnmain.html
Glass, Gene V. and Kenneth D. Hopkins. Statistical Methods in Education
and Psychology, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, Inc., 1970.
Hellekalek, Peter. Random Number Generators, at
http://random.mat.sbg.ac.at/, January 1997.
Knuth, D. E. The Art of Computer Programming, 2nd ed., vol. 2. Reading,
MA: Addison-Wesley Publishing Company, Inc., 1981.
Landau, Rubin H. Monte-Carlo Techniques, at
http://comphy.physics.orst.edu/ComPhys/MONTE/mc3/mc3.html, 1994.
Ralston, Anthony and Edwin D. Reilly, Jr. Encyclopedia of Computer
Science and Engineering, Second Edition. Yew York: Van Nostrand Reinhold
Company,
1983.
Schneider, Kurt. Analyzing Random Number Generators, at
http://euclid.ucsd.edu/~kschneid/spring104/, 1996.
 , Computational Science Education Project.
Random Number Generators, at http://csep1.phy.ornl.gov/rn/rn.html.
huang po
|
