#!/usr/bin/ruby
def log2(n)
  Math.log(n) / Math.log(2)
end

def flip(n)
  # rather than simulate log2(n) coin flips, let's agree that flipping log2(n)
  # fair coins to represent a binary number gives us a uniformly distributed
  # random number between 0 and m-1, where m is the smallest power of 2 greater
  # than or equal to n.
  #
  # The überparanoid can implement individual coin flips here
  m = 2**(log2(n).ceil)
  rand(m)
end

# Repetitions
Z = 1000000

if ARGV.empty? 
  puts "Give me n, fool."
  exit 1 
end
n = ARGV.shift.to_i

hist = Array.new(n, 0)
reflips_tot = 0

Z.times do |i|
  reflips = -1
  begin
    x = flip(n)
    reflips += 1
  end until x < n
  reflips_tot += reflips
  hist[x] += 1
end

hist.each_with_index {|x,i| 
  h = 60.0 / hist.max
  puts "%3d: %s" % [i, "*" * (x*h)]
}
puts "Average reflips per prize: #{reflips_tot.to_f / Z}"