Given a function that returns a random number 0 or 1, write a function that returns a number between 0 and 199 We are given a function f2(), that can return either 0 or 1 with equal probability. Now using this function f2() only, write a function f200() which returns a number from 0 to 199 with equal probability distribution.

In Ruby:

def f2
  return Random.rand(2)
end

def f200
  # this function makes use of the property that, if you throw away
  # evenly distributed numbers, the rest of the numbers are still
  # evenly distributed

  while true do
    max = 0
    result = 0

    while max &lt; 199 do
      result &lt;&lt;= 1
      max &lt;&lt;= 1
      result += f2()    # f2() gives a random bit
      max += 1
    end

    return result if result &gt;= 0 &amp;&amp; result &lt;= 199
  end

end

# this part is only for testing: ==========================================

def print_report(tally)
  number_of_keys = tally.keys().length
  total = tally.values().inject(:+)
  expected_count = total.to_f / number_of_keys

  tally.keys().sort().each {|k| puts "%-8i %-8i off by %6.3f %" % [k, tally[k], ((tally[k] - expected_count) / expected_count * 100).abs()] }
end

n = 1_000_000
puts "checking f200() for #{n} times:"
tallyForF200 = Hash.new(0)
n.times { r = f200(); tallyForF200[r] += 1 }
print_report(tallyForF200)


If you want to see a better result (of more even distributed numbers), increase the n, which is set to 1_000_000 near the end to 10_000_000.
You're just trying to get a certain number of random bits, so calculate that number ahead of time:

bits = 199.to_s(2).length


Then your loop becomes:

loop do
  result = 0
  bits.times do
    result &lt;&lt;= 1
    result += f2
  end
  return result if result &gt;= 0 &amp;&amp; result &lt;= 199
end