three_hack.c

/*
https://math.stackexchange.com/a/3306

A simple (practical, low-computation) approach to choosing among three options with 
equal probability exploits the fact that in a run of independent flips of an unbiased 
coin, the chance of encountering THT before TTH occurs is 1/3. So:

Flip a coin repeatedly, keeping track of the last three outcomes. (Save time, if you 
like, by assuming the first flip was T and proceeding from there.)

Stop whenever the last three are THT or TTH.

If the last three were THT, select option 1. Otherwise flip the coin one more time, 
choosing option 2 upon seeing T and option 3 otherwise.
*/

// $ gcc -O3 -Wall three_hack.c -o three_hack
// works, 500K results in 8M bits

#include <stdio.h>
#include <assert.h>

#define BYTES 1000000
#define BITS (BYTES*8)

unsigned char ent[BYTES];

unsigned char mask[8] = {
  0b00000001,
  0b00000010,
  0b00000100,
  0b00001000,
  0b00010000,
  0b00100000,
  0b01000000,
  0b10000000
};

int ent_bit(unsigned idx) {
  return (ent[idx/8] & mask[idx%8]) != 0;
}

int main(){
  FILE * dur = fopen("/dev/urandom", "r");
  assert(dur);
  assert(BYTES == fread(ent, 1, BYTES, dur));
  fclose(dur);

  unsigned numerator=0, denominator=0;
  for(int i=2; i<BITS; i++) {
    if((ent_bit(i-0) && !ent_bit(i-1) && ent_bit(i-2)) || (!ent_bit(i-0) && ent_bit(i-1) && ent_bit(i-2))) {
      denominator++;
      if(ent_bit(i-0) && !ent_bit(i-1) && ent_bit(i-2)) numerator++;
      i+=1; // i+=2 would be a fresh start, doesn't seem neccessary
    }
  }
  printf("%u/%u = %lf\n", numerator, denominator, (double)numerator / (double)denominator);

  return 0;
}