[Shootout-list] Fibonacci Benchmark Correction

[Jabari Zakiya]

With regard to the Fibonacci algorithm benchmarks it states:

-------------------------------------------------------------
about the fibonacci benchmark
Each program should calculate the Fibonacci function using the same na=EFve=
 recursive-algorithm

F(x)
  x =3D 0     =3D 1
  x =3D 1     =3D 1
  otherwise =3D F(x-2) + F(x-1)


Calculate F(N). Correct output N =3D 32 is:

3524578

For more information see Eric W. Weisstein, "Fibonacci Number." From MathWo=
rld--A Wolfram Web Resource.
http://mathworld.wolfram.com/FibonacciNumber.html
-----------------------------------------------------------------

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)=3D0, F(1)=3D1
from this F(n)=3D F(n-1)+F(n-2) for n>1

References:
http://goldennumber.net/fibonser.htm
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html

The reference site: http://mathworld.wolfram.com/FibonacciNumber.html
in fact, states the algorithm correctly, but it was apparently misread.

------------------------------------------
The Fibonacci numbers of the sequence of numbers Fn defined by the Un in th=
e Lucas sequence, which can be viewed as a particular case of the Fibonacci=
 polynomials Fn(x) with Fn=3DFn(1).=20
They are companions to the Lucas numbers and satisfy the same recurrence re=
lation,

Fn =3D Fn-2 + Fn-1

for n =3D 3, 4, ..., with F1=3DF2=3D1. The first few Fibonacci numbers are =
1, 1, 2, 3, 5, 8, 13, 21, ... (Sloane's A000045). As a result of the defini=
tion (1), it is conventional to define F0=3D0. Fibonacci numbers are implem=
ented in Mathematica as Fibonacci[n].=20
-----------------------------------------

As you can see, this does explicitly states F0=3D0 and NOT F0=3D1 as the be=
nchmark states.
It also explicitly defines F1 =3D F2 =3D 1. Their description starts the se=
ries as 1, 1, 2,...
to show its relation to the Lucas sequence, from which they derive the fibo=
nacci sequence.
Thus, the mathworld fibonacci series/algorithm description is consistent wi=
th the other references I provided, and when you account for F0=3D0, the se=
quences are identical.

Thus for N =3D 32, F(32) =3D 21708309 and NOT 3524578, which is F(33)
see list of F(N) at http://goldennumber.net/fibonser.htm

Thus, all the fibonacci benchmarks produce incorrect answers for each Fn,
except for F1=3D1.

Incorrect fibonacci benchmark code examples:

For Ruby:

def fib(n)
  if n<2 then
    1
  else
    fib(n-2) + fib(n-1)
  end
end

For Forth

: fib (n-m)=20
  dup 2 < if drop 1 else 1- dup recurse swap 1- recurse + then
;

Thus, when n=3D0 the benchmark algorithms produce Fib(0) =3D 1,
which is incorrect, and throws off all the correct values for n by 1.

The correct algorithms should account for Fib(0)=3D0.

Ruby (1.8.2) example:
# Produces correct Fibonacci values and series
def fib(n)
  if n<2
    n=20
  else
    fib(n-2) + fib(n-1)
  end
end

or

def fib(n)
  if n>1
    fib(n-1) + fib(n-2)
  else
    n
  end
end

# or

def fib(n)=20
  if n>1 then fib(n-1)+fib(n-2)=20
  else n=20
  end=20
end

# or as a oneliners

def fib(n) if n>1: fib(n-1)+fib(n-2) else n end end
def fib(n) if n>1 then fib(n-1)+fib(n-2) else n end end

Forth examples:
\ Produces correct Fibonacci values and series
: fib (n-m)
  dup 2 < if exit else 1- dup recurse swap 1- recurse + then
;

\ or better (ANSForth)

: fib (n-m)=20
  dup 1 > if 1- dup recurse swap 1- recurse + then
;

\ or even better (for gforth)

: fib (n-m) recursive=20
  dup 1 > if 1- dup fib swap 1- fib + then
;

To correct all the code examples, just fix the conditional expressions:

if n<2 then fib(n)=3D1, or equivalent, replace with
if n<2 then fib(n)=3Dn, or equivalent.

I hope this helpfull.

Jabari Zakiya
jzakiya@mail.com
--=20
___________________________________________________________
Sign-up for Ads Free at Mail.com
http://promo.mail.com/adsfreejump.htm