Velocity Reviews > Ruby > Fibonacci Benchmark Correction

Fibonacci Benchmark Correction

Josef 'Jupp' Schugt
Guest
Posts: n/a

 03-18-2005
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.

Douglas Livingstone
Guest
Posts: n/a

 03-18-2005
On Sat, 19 Mar 2005 03:09:52 +0900, http://www.velocityreviews.com/forums/(E-Mail Removed) <(E-Mail Removed)> wrote:
>
> >
> >
> > It is a high visibility set of code samples which don't do what is
> > written on the box. Through a combination of lazyness and "I'm right
> > you're wrong" it probably won't get fixed... but that doen't make it
> > right

>
> Are you offering to fix all the programs and submit new versions?
>

No, that was somewhat my point

It isn't that big a deal, just change the "what these are" comments to
be correct. Here is a somewhat "authorative" reference:

http://www.research.att.com/cgi-bin/...i?Anum=A000045

Or more readable:

http://en.wikipedia.org/wiki/Fibonacci_number

Douglas

igouy@yahoo.com
Guest
Posts: n/a

 03-19-2005
(E-Mail Removed) wrote:
> The Great Computer Language Shootout Benchmarks
> http://shootout.alioth.debian.org/
> is using an incorrect fibonacci algorithm benchmark.

While acknowledging the comments of Josef, Michael, Nikolai, Joel,
Michael, and E, we'll probably change the code for the Fibonacci
programs for the simple reason that we refer to the Mathworld
definition which uses F(0)=0, so it's more than a little confusing when
we don't use that definition for the programs

The original Shootout referred to this definition
http://cubbi.org/serious/fibonacci.html

Meanwhile Tcl programmers have actually been contributing programs to
Shootout - no wonder Tcl now looks so much better than Ruby!

igouy@yahoo.com
Guest
Posts: n/a

 03-19-2005

Douglas Livingstone wrote:
> On Sat, 19 Mar 2005 03:09:52 +0900, (E-Mail Removed) <(E-Mail Removed)>

wrote:
> >
> > >
> > >
> > > It is a high visibility set of code samples which don't do what

is
> > > written on the box. Through a combination of lazyness and "I'm

right
> > > you're wrong" it probably won't get fixed... but that doen't make

it
> > > right

> >
> > Are you offering to fix all the programs and submit new versions?
> >

>
> No, that was somewhat my point

Then perhaps "lazyness" and "I'm right you're wrong" better describe
your attitude than ours

Douglas Livingstone
Guest
Posts: n/a

 03-19-2005
On Sat, 19 Mar 2005 10:14:52 +0900, (E-Mail Removed) <(E-Mail Removed)> wrote:
> Then perhaps "lazyness" and "I'm right you're wrong" better describe
> your attitude than ours
>

Quite possibly

jzakiya@mail.com
Guest
Posts: n/a

 03-19-2005
(E-Mail Removed) wrote:
> (E-Mail Removed) wrote:
> > The Great Computer Language Shootout Benchmarks
> > http://shootout.alioth.debian.org/
> > is using an incorrect fibonacci algorithm benchmark.

>
> While acknowledging the comments of Josef, Michael, Nikolai, Joel,
> Michael, and E, we'll probably change the code for the Fibonacci
> programs for the simple reason that we refer to the Mathworld
> definition which uses F(0)=0, so it's more than a little confusing

when
> we don't use that definition for the programs
>
> The original Shootout referred to this definition
> http://cubbi.org/serious/fibonacci.html
>
>
> Meanwhile Tcl programmers have actually been contributing programs to
> Shootout - no wonder Tcl now looks so much better than Ruby!

Great. Thanks.

I joined the Shootout list yesterday and was notified, and see,
the benchmark has been corrected to conform to the references.

Below is a Ruby benchmark which identifies a faster implementation.
================================================== =================

require 'benchmark'
include Benchmark

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

def fib2(n) n<2 ? n : fib2(n-1)+ fib2(n-2) end

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

def fib4(n) n>1 ? fib4(n-1)+ fib4(n-2) : n end

n=20
bmbm(12) do |x|
x.report("fib1") { n.times { fib1(25) } }
x.report("fib2") { n.times { fib2(25) } }
x.report("fib3") { n.times { fib3(25) } }
x.report("fib4") { n.times { fib4(25) } }
end
================================================== =================

The following times were generated from the above benchmark.
600Mhz Athlon K-7, 640MB, Mandrake 10.1 Official, Ruby 1.8.2

Rehearsal -----------------------------------------------
fib1 11.910000 0.010000 11.920000 ( 12.205975)
fib2 11.990000 0.000000 11.990000 ( 12.246299)
fib3 11.740000 0.000000 11.740000 ( 11.963777)
fib4 11.500000 0.000000 11.500000 ( 11.736313)
------------------------------------- total: 47.150000sec

user system total real
fib1 11.900000 0.000000 11.900000 ( 12.133921)
fib2 12.000000 0.000000 12.000000 ( 12.248496)
fib3 11.740000 0.000000 11.740000 ( 11.955820)
fib4 11.460000 0.000000 11.460000 ( 11.696977)

The following times were generated from the above benchmark.
600Mhz Athlon K-7, 640MB, Win98, Ruby 1.8.2

Rehearsal -----------------------------------------------
fib1 18.290000 0.000000 18.290000 ( 18.290000)
fib2 17.740000 0.000000 17.740000 ( 17.740000)
fib3 19.890000 0.000000 19.890000 ( 19.890000)
fib4 17.460000 0.000000 17.460000 ( 17.460000)
------------------------------------- total: 47.150000sec

user system total real
fib1 17.850000 0.000000 17.850000 ( 17.850000)
fib2 17.470000 0.000000 17.470000 ( 17.470000)
fib3 18.070000 0.000000 18.070000 ( 18.070000)
fib4 17.470000 0.000000 17.470000 ( 17.470000)

fib4 is fastest, which is faster than Shootout version fib1.
Note: These versions produce the correct fibonacci sequence
for all index values n (n=0,1,2,3,4,5...)

Jabari Zakiya

Glenn Parker
Guest
Posts: n/a

 03-19-2005
(E-Mail Removed) wrote:
>
> Meanwhile Tcl programmers have actually been contributing programs to
> Shootout - no wonder Tcl now looks so much better than Ruby!

There may be reasons why Tcl looks better than Ruby at the moment, but
it's not a lack of contributions.

I contributed three new Ruby benchmarks recently (via the mailing list
and the webform). I haven't seen any changes in the published Ruby
benchmarks list, nor have I received acknowledgement that my programs
were received and/or accepted. My mail to (E-Mail Removed) bounced.

Maybe they'll show up sometime soon? So far, it seems like a black hole
to me.

--
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/>

ES
Guest
Posts: n/a

 03-19-2005
Glenn Parker wrote:
> (E-Mail Removed) wrote:
>
>>
>> Meanwhile Tcl programmers have actually been contributing programs to
>> Shootout - no wonder Tcl now looks so much better than Ruby!

>
>
> There may be reasons why Tcl looks better than Ruby at the moment, but
> it's not a lack of contributions.
>
> I contributed three new Ruby benchmarks recently (via the mailing list
> and the webform). I haven't seen any changes in the published Ruby
> benchmarks list, nor have I received acknowledgement that my programs
> were received and/or accepted. My mail to (E-Mail Removed) bounced.
>
> Maybe they'll show up sometime soon? So far, it seems like a black hole
> to me.
>

Looks like quite a few programs are still missing[1]. Could these be
made into Ruby Quizzes (along with improving the existing ones and
correcting the erroneous ones), perhaps a few at a time?

E

[1]
http://shootout.alioth.debian.org/be...y&sort=fullcpu

Nikolai Weibull
Guest
Posts: n/a

 03-19-2005
* (E-Mail Removed) (Mar 19, 2005 19:10):
> While acknowledging the comments of Josef, Michael, Nikolai, Joel,
> Michael, and E, we'll probably change the code for the Fibonacci
> programs for the simple reason that we refer to the Mathworld
> definition which uses F(0)=0, so it's more than a little confusing
> when we don't use that definition for the programs

I don't want to be a dick, but I never said that the code shouldn't be
changed. I just figured that there are more important problems than
deciding the exact starting point of the Fibonacci series (which is, as
stated again and again in this thread to no avail it seems, arbitrary).

Anyway, consistency is great, so its good that you adhere to the
material you're quoting. Good luck with the shootout,
nikolai

--
::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
::: page: minimalistic.org :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

igouy@yahoo.com
Guest
Posts: n/a

 03-20-2005

Glenn Parker wrote:
> (E-Mail Removed) wrote:
> >
> > Meanwhile Tcl programmers have actually been contributing programs

to
> > Shootout - no wonder Tcl now looks so much better than Ruby!

>
> There may be reasons why Tcl looks better than Ruby at the moment,

but
> it's not a lack of contributions.
>
> I contributed three new Ruby benchmarks recently (via the mailing

list
> and the webform). I haven't seen any changes in the published Ruby
> benchmarks list, nor have I received acknowledgement that my programs

> were received and/or accepted. My mail to (E-Mail Removed) bounced.
>
> Maybe they'll show up sometime soon? So far, it seems like a black

hole
> to me.

Nothings appeared with you as author in this months mailing list
archive - maybe there's a problem with your mailing list subscription
(you did subscribe?)

Not igouy, but igouy2

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post dleecurt@cc.usu.edu C++ 28 06-05-2011 04:30 AM Brett Trost Perl 2 01-22-2004 02:04 PM Lance C++ 5 12-02-2003 09:17 AM Alex Vinokur C++ 0 10-29-2003 12:07 PM fighterman19 C++ 11 09-08-2003 02:30 PM

Advertisments