[Melbourne-pm] Retry/Attempt

[Sam Watkins]

On Tue, May 18, 2010 at 03:26:56PM +1000, Daniel Pittman wrote:
> Sam Watkins <sam at nipl.net> writes:
> > On Tue, May 18, 2010 at 11:16:12AM +1000, Daniel Pittman wrote:
> >> > I'm jealous, a genuine opportunity to use Fibonacci in a real-world program!
> >> 
> >> Heh.  Despite my bikeshedding ^W encouragement, this just doubles the delay
> >> every time, rather than using a Fibonacci back-off strategy.  Alas. :)
> >
> > What advantage would there be to using Fibonacci numbers instead of
> > exponential backoff?
> 
> It retries faster in the early stages, and grows a little less quickly, so
> tends to give better recovery faster than you would otherwise see.
> 
> > IIRC the Fibonacci series is approximately exponential anyway.
> 
> Er, no, not really.  Exponential grows enormously more quickly than Fibonacci
> does; starting at 1, at 10 steps you have 34 vs 256, at 15 steps 377 vs 8192.

The Fibonacci series does grow exponentially, there is a closed-form formula
for F(n) and it is approximated by an exponential of base 1+sqrt(5)/2 or about
1.618

The base is lower than 2, so the series grows more slowly than the powers of 2.

  http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression

  F(n) ~= (1+sqrt(5)/2) ^ n / sqrt(5)

i.e.

  F(n) ~= 1.618 ^ n / sqrt(5)

I guess it's potentially simpler to use Fibonacci numbers (addition) compared
to multiplying by 1.618, so Fibonacci might be good for hardware if you want a
slower growth rate than the powers of 2.  There's some "natural balance" or
beauty or something about the Fibonacci numbers, too, something to do with the
golden ratio.

Or you might like to use e^x for faster growth and some different benefits /
mathematical qualities!

Sam