From: jzakiya@...
Date: 2005-03-16T22:34:50+09:00
Subject: Fibonacci Benchmark Correction

The Great Computer Language Shootout Benchmarks
http://shootout.alioth.debian.org/

is using an incorrect fibonacci algorithm benchmark.

Yesterday I sent this comment to correct it.

I (unfortunately) have noticed this incorrect implementation
of the Fiboncacci algorithm permeated in many places now,
one being the book Teach Yourself Ruby in 21 Days.

Hoepfully, the GCLSB will make the correction, and others
will also.

Below is the message I sent the GCLSB.

Jabari Zakiya
jzakiya@mail.com
==============================================================

With regard to the Fibonacci algorithm benchmarks it states:

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

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


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

3524578

For more information see Eric W. Weisstein, "Fibonacci Number." From
MathWorld--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)=0, F(1)=1
from this F(n)= 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 the Lucas sequence, which can be viewed as a particular case of the
Fibonacci polynomials Fn(x) with Fn=Fn(1).
They are companions to the Lucas numbers and satisfy the same
recurrence relation,

Fn = Fn-2 + Fn-1

for n = 3, 4, ..., with F1=F2=1. The first few Fibonacci numbers are 1,
1, 2, 3, 5, 8, 13, 21, ... (Sloane's A000045). As a result of the
definition (1), it is conventional to define F0=0. Fibonacci numbers
are implemented in Mathematica as Fibonacci[n].
-----------------------------------------

As you can see, this does explicitly states F0=0 and NOT F0=1 as the
benchmark states.
It also explicitly defines F1 = F2 = 1. Their description starts the
series as 1, 1, 2,...
to show its relation to the Lucas sequence, from which they derive the
fibonacci sequence.
Thus, the mathworld fibonacci series/algorithm description is
consistent with the other references I provided, and when you account
for F0=0, the sequences are identical.

Thus for N = 32, F(32) = 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=1.

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)
  dup 2 < if drop 1 else 1- dup recurse swap 1- recurse + then
;

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

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

Ruby (1.8.2) example:
# Produces correct Fibonacci values and series
def fib(n)
  if n<2
    n
  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)
  if n>1 then fib(n-1)+fib(n-2)
  else n
  end
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)
  dup 1 > if 1- dup recurse swap 1- recurse + then
;

\ or even better (for gforth)

: fib (n-m) recursive
  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)=1, or equivalent, replace with
if n<2 then fib(n)=n, or equivalent.

I hope this helpfull.

Jabari Zakiya
jzakiya@mail.com