random_numbers
no way to compare when less than two revisions
Differences
This shows you the differences between two versions of the page.
— | random_numbers [2007/02/17 18:33] (current) – created - external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | # $EPIC: random_numbers.txt, | ||
+ | |||
+ | ======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. | ||
+ | question: If I see <N> numbers from the random number generator, can I guess | ||
+ | what the possible values of the < | ||
+ | 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. | ||
+ | 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, | ||
+ | |||
+ | =====Why are these forces in opposition? | ||
+ | Any psuedo-random number generator that uses an algorithm has to have a | ||
+ | starting value (" | ||
+ | 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. | ||
+ | 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. | ||
+ | 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! | ||
+ | The client has four random number generators: | ||
+ | |||
+ | ^ [[SET RANDOM_SOURCE]] ^ Type ^ Entropy ^ Coverage ^ Repeatability ^ Seeded ^ | ||
+ | | 0 | / | ||
+ | | 1 | Classic ircII RNG | None | High | High | Yes | | ||
+ | | 2 | gettimeofday() | ||
+ | | 3 | Arc4random | ||
+ | |||
+ | =====Urandom: | ||
+ | The / | ||
+ | This requires that the client hold open / | ||
+ | number of file descriptors 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 fully portable across all ircII clients. | ||
+ | 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. | ||
+ | and using the low 16 bits of each call to generate a 32 bit number. | ||
+ | faster computers and faster syscalls these days than 10 years ago, this RNG | ||
+ | doesn' | ||
+ | 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. | ||
+ | so it is not repeatable. | ||
+ | |||
+ | ======History: | ||
+ | The classic ircII RNG first appeared in ircII. | ||
+ | The gettimeofday() RNG first appeared in EPIC3. | ||
+ | The / | ||
+ | The arc4random RNG first appeared in EPIC4-1.1.8. | ||
+ | |||
random_numbers.txt · Last modified: 2007/02/17 18:33 by 127.0.0.1