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 **************************************************