My colleague, David, had an interesting problem:
For example, if an error should occur 33% of the time, it should be predictable like: ERROR, ok, ok, ERROR, ok, ok, ...
Or at 50% error rate: ERROR, ok, ERROR, ok, ...
“
devdriven:
p(t)
in range [0,1)
at time t
and P
is the probability of the event (e.g. I/O error) then: event?(t) = p(t) < P
.
Pseudo-random numbers are predictable if you know the seed."
David:
devdriven:
p(t)
is an event probability at t
, p(t)
could be defined as p(t) = (t modulo 100) / 100
.
However p(t) < P
is not "evenly" distributed over t in [0,100)
.
For P = .50
, the stream of events would be: ERROR
(50 times) ..., ok
(50 times), ...
The algorithm should distribute P * 100
events "evenly" over 100 time values. What is P
? 33% is 33/100, 50% is 50/100: ratios.
The slope of a 2D line between two discrete points is a ratio!
Bresenham's Line Algorithm does just this when rasterizing lines to pixels -- how does it work?
It uses discrete differential error tracking to determine how far y
is from a linear function: f(x) = slope * x
. The change of the error's sign tells us when to increment y
(e.g.: emit an event to move up one pixel). This technique can be extended to any polynomial by cascading errors for each derivative. It is a robust, iterative solution that guarantees correctness and repeatability over intervals of slope.numerator * slope.denominator
."
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | # event-bres.rb require 'rational' def bres ratio Enumerator.new do | yielder | # Note: error = 0 means zero_crossing is always true for first elem. # This can be balanced by using error = ratio.denominator / 2 error = 0 loop do error -= ratio.numerator if zero_crossing = error < 0 error += ratio.denominator end yielder.yield zero_crossing end end end ratio = Rational(33, 100) stream = bres(ratio) y = 0 stream.take(15).each do | event | y += 1 if event puts "%.2f %s %*s" % [ ratio.to_f, event ? 'X' : ' ', y, '*' ] end puts (0..100).step((ARGV[0] || 10).to_i).each do | percent | ratio = Rational(percent,100) stream = bres(ratio) count = stream.take(n = 100).count{|x| x} puts "%.2f %.2f %s" % [ ratio.to_f, count.to_f / n, stream.take(50).map{|x| x ? '*' : ' '}*'' ] end |
Outputs:
#\ ruby event-bres.rb 0.33 X * 0.33 * 0.33 * 0.33 X * 0.33 * 0.33 * 0.33 X * 0.33 * 0.33 * 0.33 X * 0.33 * 0.33 * 0.33 X * 0.33 * 0.33 * 0.00 0.00 0.10 0.10 * * * * * 0.20 0.20 * * * * * * * * * * 0.30 0.30 * * * * * * * * * * * * * * * 0.40 0.40 * * * * * * * * * * * * * * * * * * * * 0.50 0.50 * * * * * * * * * * * * * * * * * * * * * * * * * 0.60 0.60 ** * ** * ** * ** * ** * ** * ** * ** * ** * ** * 0.70 0.70 *** ** ** *** ** ** *** ** ** *** ** ** *** ** ** 0.80 0.80 **** **** **** **** **** **** **** **** **** **** 0.90 0.90 ********* ********* ********* ********* ********* 1.00 1.00 **************************************************