random_numbers

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

random_numbers [2007/02/17 18:33] |
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)