no way to compare when less than two revisions

Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+# $EPIC: random_numbers.txt,v 1.2 2007/02/17 18:33:25 jnelson Exp $
+======About pseudo-random numbers:======
+Psuedo-random number generators (RNG) always have tension between three
+opposing forces:
+) Entropy
+) Coverage
+) Repeatability
+=====Entropy:=====
+Entropy is the tendancy of a RNG to avoid revealing what the next random
+number is going to be.   Entropy can be roughly measured by asking this
+question: If I see <N> numbers from the random number generator, can I guess
+what the possible values of the <N+1>th value is?  As N grows increasingly
+larger, does the possible values of N+1 grow increasingly smaller?
+High entropy can be imaged as deck of cards where you select a card, and
+then re-shuffle the deck before you select the next card.
+=====Coverage:=====
+Coverage is the tendancy of an RNG to select each value approximately the
+same number of times.  Coverage can be roughly measured by determining
+whether the selections-per-number is flat (more coverage) or bell shaped
+(less coverage),
+High coverage can be imagined as a deck of cards where you select a card,
+and then remove that card from the deck, until all the cards have been
+used, and then you re-shuffle.
+=====Repeatability:=====
+Repeatability is the tendancy of an RNG to be able to generate the same
+values each time it is used.  Repeatability is determined by observation.
+Repeatability can be imagined as a deck of cards where the order is
+predetermined, and you select each card in order.
+=====Why are these forces in opposition?=====
+Any psuedo-random number generator that uses an algorithm has to have a
+starting value ("seed").  Most RNGs are fully repeatable, given the same
+initial seed.  The quality of the entropy is therefore only as good as
+the secrecy of the seed.
+Any psuedo-random number generator that uses a mathematical formula to
+decide what the next value is, bases the next number in part on the previous
+number.  The best
+RNGs create values that are very very large (arc4random creates values
+[0..2^170]) and then give you only a few bits of that number.  This hides
+from the viewer what the number is, and hinders the calculation of the
+next number.
+Any psuedo-random number generator that uses an external data source does
+not have to be seeded, but the quality of the entropy depends on the
+external source.
+======Enough blathering!  What about EPIC?======
+The client has four random number generators:
+^ [[SET RANDOM_SOURCE]] ^ Type ^ Entropy ^ Coverage ^ Repeatability ^ Seeded ^
+|  0  | /dev/urandom           | High    | Medium   | Low           | No     |
+|  1  | Classic ircII RNG      | None    | High     | High          | Yes    |
+|  2  | gettimeofday()         | Medium  | Low      | Low           | No     |
+|  3  | Arc4random             | High    | Medium   | Low           | No     |
+=====Urandom:=====
+The /dev/urandom RNG reads 32 bits from /dev/urandom and returns them to you.
+This requires that the client hold open /dev/urandom, which will reduce the
+number of file descriptors available.  If /dev/urandom is not available,
+this RNG falls back to the classic ircII RNG.  You cannot seed this RNG.
+=====Classic ircII:=====
+This is the RNG used by all versions of ircII.  It is always available, and
+it is fully portable across all ircII clients.  Based on a 32 bit seed, it
+generates a 32 bit number and returns it.  Given one number, it is possible
+to generate all the random numbers that succeed it.  This RNG must be seeded,
+and is fully repeatable with the same seed.
+=====gettimeofday():=====
+This is the RNG historically used by EPIC.  It is usually available on all
+epic and bx clients.  It works by calling gettimeofday() twice in succession
+and using the low 16 bits of each call to generate a 32 bit number.  Given
+faster computers and faster syscalls these days than 10 years ago, this RNG
+doesn't give very good coverage, but it's hard to predict the exact time.
+You cannot seed this RNG.
+=====Arc4random:=====
+This is the RNG currently recommended for all-purpose use.  This RNG generates
+numbers between 0 and 2^170 and returns the lowest 32 bits.  Not knowing what
+the high 138 bits are makes it unreasonably difficult to calculate the next
+value, since it's understood that all 2^32 values are possible within the
+^138 different paths.  The Arc4random RNG is auto-seeding from /dev/urandom
+so it is not repeatable.
+======History:======
+The classic ircII RNG first appeared in ircII.
+The gettimeofday() RNG first appeared in EPIC3.
+The /dev/urandom RNG first appeared in EPIC4pre2.001.
+The arc4random RNG first appeared in EPIC4-1.1.8.