1
\$\begingroup\$

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.

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

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 <<= 1
    result += f2
  end
  return result if result >= 0 && result <= 199
end
\$\endgroup\$
  • \$\begingroup\$ 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... \$\endgroup\$ – 太極者無極而生 Apr 5 '17 at 13:30
  • \$\begingroup\$ 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? \$\endgroup\$ – 太極者無極而生 Apr 5 '17 at 13:32
  • \$\begingroup\$ 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. \$\endgroup\$ – Marc Rohloff Apr 5 '17 at 14:36
  • \$\begingroup\$ I'm doing the same thing the original code did: throw away numbers that don't match the range. \$\endgroup\$ – David Stanley Apr 5 '17 at 18:04
0
\$\begingroup\$
        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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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"? \$\endgroup\$ – 太極者無極而生 Apr 5 '17 at 3:37
  • \$\begingroup\$ 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. \$\endgroup\$ – mdfst13 Apr 5 '17 at 14:09
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.