Josef 'Jupp' Schugt
3/18/2005 7:57:00 PM
Hi!
Jabari Zakiya wrote:
> This is an incorrect statement of the Fibonacci algotithm.
>
> The Fibonacci series is: 0, 1, 1, 2, 3, 5, 8, 13, 21, .....
>
> The first two terms in the series are: F(0)=0, F(1)=1
> from this F(n)= F(n-1)+F(n-2) for n>1
The above is an incorrect statement about the nature of mathematics.
Here we have one definition for the Fibonacci series:
.........................................................................
Definition A: Fibonacci series
Let F(0) = 1, F(1) = 1. For any natural number n > 1 define
F(n) = F(n-1) + F(n-2). The series F defined in such a way is called
"Fibonacci series".
.........................................................................
Here we have another one:
.........................................................................
Definition B: Fibonacci series
Let F(0) = 0, F(1) = 1. For any natural number n > 1 define
F(n) = F(n-1) + F(n-2). The series F defined in such a way is called
"Fibonacci series".
.........................................................................
From a mathematical point of view it simply makes no sense to say that
one of these definitions is 'correct' and the other one is 'incorrect'.
All one can say that one of these sequences is more commonly termed as
'Fibonacci series' then the other.
Addition 1:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 2
Addition 2:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
Both kinds of additions are used. Addition 1 for natural numbers and the
like and Addition 2 for the commutative associative division algebra
where multiplication can be seen as logical AND and addition can be seen
as logical XOR:
0 * 0 = 0 <-> false AND false = false
0 * 1 = 0 <-> false AND true = false
1 * 0 = 0 <-> true AND false = false
1 * 1 = 1 <-> true AND true = true
0 + 0 = 0 <-> false XOR false = false
0 + 1 = 1 <-> false XOR true = true
1 + 0 = 1 <-> true XOR false = true
1 + 1 = 0 <-> true XOR true = false
Robert Sedgewick, Algorithms in C++ has
1, 1, 2, 3, 5, 8, 13, 21, ...
Cormen, Leiserson, Rives, Algorithms has
0, 1, 1, 2, 3, 5, 8, 13, ...
Ottmann, Widmeyer, Algorithmen und Datenstrukturen again has
1, 1, 2, 3, 5, 8, 13, 21, ...
If I were to propose the definition I would use F(0) = 0. The reason is
the golden ratio f and its conjugate F:
f = (1.0 + sqrt(5.0)) / 2.0
F = (1.0 - sqrt(5.0)) / 2.0
With the definition F(0) = 0 the following holds:
F(i) == (f**i - F**i) / sqrt(5.0)
The whole issue is not worth a holy cursade. One should keep in mind
that a benchmark exists for one and only one reason: Benchmarking.
The true reason to give the test a name like 'Fibonacci series' is that
this is more mnemonic than "benchmarking series Nr. 4711".
Just my two Euro Cent,
Josef 'Jupp' Schugt
--
Dear President George Walker Bush,
the way in which it is tried to install a software patent directive
clearly shows that the EU not democratic. We urgently need brothers in
arms who help us establish democratic structures.