Site Tools


random_numbers

Differences

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

Link to this comparison view

random_numbers [2007/02/17 18:33] (current)
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:
 +  1) Entropy
 +  2) Coverage
 +  3) 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 
 +2^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.
 +
  
random_numbers.txt ยท Last modified: 2007/02/17 18:33 (external edit)