From: Joel VanderWerf <vjoel@...>
Date: 2005-03-17T09:52:49+09:00
Subject: [OT] Re: Fibonacci Benchmark Correction

jzakiya@mail.com wrote:
> The point is the stated code for every fibonacci benchmark algorithm
> DOES NOT PRODUCE THE CORRECT SERIES!!
> 
> Even if you want to start the series using N=1 as the first index
> value, the coded algorithms produce the following results:
> 
> index N:    benchmark F(N)       Correct F(N)
>     1           1                    1
>     2           2                    1
>     3           3                    2
>     4           5                    3
>     5           8                    5
>     6          13                    8
>     7          21                   13
> etc
> 
> Again, THE BENCHMARK CODE PRODUCES INCORRECT RESULTS!
> It doesn't even produce the sequence it says it should!
> 
> So while the coded algorithm does consistently produce the same
> answers, DON'T CALL IT THE FIBONACCI SERIES ALGORITHM!!
> 
> Would an algorithm that produces the factorial 0!=0 (and not 0!=1)
> be considered to be a correct factorial algorithm? I don't think so.
> 
> What is really dangerous is someone using the coded algorithms thinking
> that for a given index N the computed fibonacci F(N) value is correct.
> 
> This is not about the given code being a valid representation for some
> arbitrary benchmark, but about the misrepresentation of that code as
> producing the correct results for the fibonacce series, a fundamental
> mathematical algorithm that is used in many fields of math and science.

It's somewhat arbitrary how you index the sequence. IMHO the essence 
(the "Fibonacci nature", if you will) of the sequence is the recurrence 
relation, not the initial conditions. If you start at 5, 8, ... you 
still get the golden section (the limit of the ratio of successive 
terms), after all. And it is possible to define generalized Fib. seq. 
that start with two given values.

In any case, the algorithms are computationally equivalent in a very 
strong sense (you can obtain one from the other by incrementing or 
decrementing the input), and so for the purposes of benchmarking they 
can both be called "the Fibonacci algorithm".

What's _really_ dangerous is thinking that F(n) must have some absolute 
significance, like e or pi. There's probably _some_ author out there who 
wrote a paper defining F(0) and F(1) differently, possibly for a good 
reason. If I were writing a paper using F, I would feel compelled to 
define F(0) and F(1) to avoid ambiguity, but I'd feel silly defining pi.