2015-07-31

HOWTO: the poor man's random number generator

Spoiler: the described binary random number generator (RNG) usually doesn't consume any electricity, but still definitely needs a minimal investment :-)

Random number generation procedure:
  1. prepare the stochastic system: get yourself a coin and check it for usability;
  2. toss the coin;
  3. note the obtained coin position;
  4. go to stage 2 (if still needed, repeat as much times as needed);
  5. convert the noted coin position into a usable form.
Some theoretical aspects:
  • if a coin had an ideal uniformity and symmetry, it could be considered an ideal (metal) disc;
  • a common coin has 2 distinctive sides, so the probability to see a specific side up (not taking the edge into account) is 1/2 = 0.5;
  • a system with 2 stable states can give you a hint of a binary numeral system;
  • the obvious lack of system's memory gives you an opportunity to generate as many random bits as you want;
  • if you toss the coin n times, you can get a random number from 0 to (2n-1); e. g., for 8 flips, the max number is: 28 - 1 = 256 - 1 = 255.
Let's assume:
  1. "heads" (obverse; usually shows the state emblem or related things) mean "0", while "tails" (reverse; usually shows the value of a coin) mean "1";
  2. it (the generation) starts with the least significant bit;
  3. the bits with larger weights are written to the left of the lesser ones.
Example: You've flipped a coin 8 times and got "0-1-0-1-0-1-0-1".
What number is it? Let's put that garbage those nice results into a table and see.

Legend:
n
Position number (bit number)
2n
Position weight (bit weight)
an
Position digit (bit value)
n76543210
2n1286432168421
an10101010

Calculation:
a = 0*1 + 1*2 + 0*4 + 1*8 + 0*16 + 1*32 + 0*64 + 1*128 = 170
So, the binary "10101010" equals "170" in the common decimal system.

Note: yes, it's a bit slow, but it can also train your brain's arithmetic performance a little, as a side effect ;-)

External (Wikipedia) links:
  1. Coin flipping
  2. Random number generation
  3. Binary number
  4. Decimal
  5. Positional notation

No comments:

Post a Comment