# 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 < 199 do
result <<= 1
max <<= 1
result += f2()    # f2() gives a random bit
max += 1
end

return result if result >= 0 && result <= 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.

• The if condition here return result if result >= 0 && result <= 199 seems unnecessary since the result should always be in that range. - never mind – Marc Rohloff Apr 5 '17 at 14:38

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


loop do
result = 0
bits.times do
result <<= 1
result += f2
end
return result if result >= 0 && result <= 199
end

• This is another way... but I was actually a bit worried that what if the calculation of "number of times for the loop" is off by 1 due to some arithmetics inaccuracy (due to floating point if I use log base 2 to find out that number). If you use the conversion to a binary number and get the number of bits in there, that should work too... except the time it takes to get that number of bits, should not be different from my shifting of max... say, if the to_s(2) takes about 8 steps to find the number, then my max <<= 1 also would have run 8 times too. Just some thoughts... – nonopolarity Apr 5 '17 at 13:30
• Personally I liked the max <<= 1 method because it is like a "control in an experience" sitting by the side saying: ok, what if the random bit has always been one, then what number will result have become? – nonopolarity Apr 5 '17 at 13:32
• Although this is much more efficient the problem is that you are actually getting a number between 0 and 255 so the distribution is not even. There is a 20% chance your function will actually not even return a result. – Marc Rohloff Apr 5 '17 at 14:36
• I'm doing the same thing the original code did: throw away numbers that don't match the range. – David Stanley Apr 5 '17 at 18:04
        while max < 199 do
result <<= 1
max <<= 1


You don't have to do the left shift on max.

        while max < 8 do
result <<= 1


That will save you a math operation every iteration.

I'm not a Ruby guy, but in a lot of languages, you'd do this with a for loop so as to put all the looping logic on the same line.

• so what if the question now change to f12345678(), or that we want to change the function to take the 200 as f(200) instead of f200(), then you'd manually calculate that "magic number"? – nonopolarity Apr 5 '17 at 3:37
• You could, or you could flip the logic with max > 0 and max >>= 1. If you get rid of the addition instead, you can write an fn function, which will also fix the magic numbers in the code. – mdfst13 Apr 5 '17 at 14:09

Some notes:

• Your f2 method can be written as just

def f2
rand(2)
end


No return or Random.-prefix necessary

• You don't need the result >= 0 check in f200. The shift operation won't "overflow" bits into the sign bit, and Ruby adjusts the internal storage for numbers that would overflow regular 32 and 64 bit types. So the number will always be zero or positive

• As David Stanley mentioned, you can easily get the bit-length of your maximum and iterate that number of times, instead of tracking max yourself. I would however use reduce/inject to do the inner loop and avoid block side-effects:

bits = n.to_s(2).length # where n = 199, for instance
result = bits.times.reduce(0) do |memo|
(result + f2) << 1
end
return result if result < n


As for solving the problem, I'd suggest the same overall solution you'd normally use in most languages: floor(rand() * max) where rand() return a float.

To do that here, you could:

• Generate a random (N-1)-bit integer using the technique you have (where N = 32, for instance)
• Divide that with 2^N, giving you a random float from zero up-to-but-excluding 1.0 (which is what the rand method already does, but whatever)
• Multiply with whatever maximum you have, and floor the result

E.g. for a variable max:

N = 32 # random number's bit-length
def fn(max)
random = (N-1).times.reduce(0) { |memo| (memo + f2) << 1 }
result = random.fdiv(2**N) * max
result.floor
end


Or for hard-coded 200:

N = 32 # random number's bit-length
def f200
random = (N-1).times.reduce(0) { |memo| (memo + f2) << 1 }
result = random.fdiv(2**N) * 200
result.floor
end