Fibonacci Benchmark Correction

Discussion in 'Ruby' started by jzakiya@mail.com, Mar 16, 2005.

  1. Guest

    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

    ==============================================================

    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
    , Mar 16, 2005
    #1
    1. Advertising

  2. * (Mar 16, 2005 14:40):
    > The Great Computer Language Shootout Benchmarks
    > http://shootout.alioth.debian.org/
    > is using an incorrect fibonacci algorithm benchmark.


    I really don't see where you're going with this. The sequence is either

    0 1 1 2 3 5 8 13 ...

    or

    1 1 2 3 5 8 13 ...

    Of course, the first makes more sense, but both are almost equally
    quoted as the Fibonacci sequence. The first is, as I said, more right,
    as you also point out, but it doesn't really matter as far as the
    benchmark goes. If everyone implements the algorithm that the benchmark
    states, then it really won't matter where the sequence begins,
    nikolai

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

  3. Guest

    Nikolai Weibull wrote:
    > * (Mar 16, 2005 14:40):
    > > The Great Computer Language Shootout Benchmarks
    > > http://shootout.alioth.debian.org/
    > > is using an incorrect fibonacci algorithm benchmark.

    >
    > I really don't see where you're going with this. The sequence is

    either
    >
    > 0 1 1 2 3 5 8 13 ...
    >
    > or
    >
    > 1 1 2 3 5 8 13 ...
    >
    > Of course, the first makes more sense, but both are almost equally
    > quoted as the Fibonacci sequence. The first is, as I said, more

    right,
    > as you also point out, but it doesn't really matter as far as the
    > benchmark goes. If everyone implements the algorithm that the

    benchmark
    > states, then it really won't matter where the sequence begins,
    > nikolai
    >
    > --
    > ::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
    > ::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
    > ::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
    > main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}



    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.

    Jabari Zakiya
    , Mar 17, 2005
    #3
  4. ES Guest

    wrote:
    > Nikolai Weibull wrote:
    >
    >>* (Mar 16, 2005 14:40):
    >>
    >>>The Great Computer Language Shootout Benchmarks
    >>>http://shootout.alioth.debian.org/
    >>>is using an incorrect fibonacci algorithm benchmark.

    >>
    >>I really don't see where you're going with this. The sequence is

    >
    > either
    >
    >> 0 1 1 2 3 5 8 13 ...
    >>
    >>or
    >>
    >> 1 1 2 3 5 8 13 ...
    >>
    >>Of course, the first makes more sense, but both are almost equally
    >>quoted as the Fibonacci sequence. The first is, as I said, more

    >
    > right,
    >
    >>as you also point out, but it doesn't really matter as far as the
    >>benchmark goes. If everyone implements the algorithm that the

    >
    > benchmark
    >
    >>states, then it really won't matter where the sequence begins,
    >> nikolai
    >>
    >>--
    >>::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
    >>::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
    >>::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
    >>main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}

    >
    >
    >
    > 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.


    OK, OK, the world will come to an end. It'll be fixed, I'm sure.
    Geez.

    > Jabari Zakiya


    E
    ES, Mar 17, 2005
    #4
  5. On Thu, 17 Mar 2005 09:19:46 +0900, <> wrote:

    > The point is the stated code for every fibonacci benchmark algorithm
    > DOES NOT PRODUCE THE CORRECT SERIES!!


    Consider it the fibonacci series with an (added/missing) element.

    The point of the exercise is to benchmark HOW it's done, and how
    various languages compare. The output is a side-effect, and long as
    it's consistent across languages.
    Michael Campbell, Mar 17, 2005
    #5
  6. [OT] Re: Fibonacci Benchmark Correction

    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.
    Joel VanderWerf, Mar 17, 2005
    #6
  7. * (Mar 17, 2005 01:30):
    > 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.


    Well, it's only "by convention" really. You could define 0! = 0 if you
    so wished. It wouldn't make much sense, but you could.

    > 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.


    Eh, since when did the GLS become authoritative on algorithm
    implementation?

    > 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.


    Worthy of a crusade?,
    nikolai


    --
    ::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
    ::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
    ::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
    main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}
    Nikolai Weibull, Mar 17, 2005
    #7
  8. On Thu, 17 Mar 2005 09:59:57 +0900, Nikolai Weibull
    <> wrote:

    > > 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.

    >
    > Eh, since when did the GLS become authoritative on algorithm
    > implementation?
    >


    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 ;)

    Just tack "These are implementations of a modified fibonacci series,
    don't steal them if you want a real fibonacci series" at the top and
    all will be fine. Except for the guy who wrote the first sample code.
    He'll look quite silly. Shame he's probably the guy who would have to
    put up the message...

    Douglas
    Douglas Livingstone, Mar 17, 2005
    #8
  9. Hello Jabari,

    On Wed, 16 Mar 2005 22:34:50 +0900, <> wrote:
    > 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


    Nowhere in this text F(x) is defined as the x-th Fibonacci number. [*]

    I'm sure the author would be glad to add a small note stating that
    "F(x) is the (x+1)-th Fibonacci number", though. Did you notice that
    the choice of defining F(x) to be the (x+1)-th Fibonacci number is
    similar to choosing a[n] to be the (n+1)-th element of the array a?

    Hope that helps,
    Michael

    [*] Note that I'm talking about Fibonacci numbers.
    Michael Walter, Mar 17, 2005
    #9
  10. Guest

    Douglas Livingstone wrote:
    > On Thu, 17 Mar 2005 09:59:57 +0900, Nikolai Weibull
    > <> wrote:
    >
    > > > 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.

    > >
    > > Eh, since when did the GLS become authoritative on algorithm
    > > implementation?
    > >

    >
    > 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?


    > Just tack "These are implementations of a modified fibonacci series,
    > don't steal them if you want a real fibonacci series" at the top and
    > all will be fine. Except for the guy who wrote the first sample code.
    > He'll look quite silly. Shame he's probably the guy who would have

    to
    > put up the message...


    Actually we inherited this particular set of programs from the original
    Shootout. The author of the original Shootout noted that he'd seen both
    referred to as the Fibonacci sequence.
    , Mar 18, 2005
    #10
  11. 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.
    Josef 'Jupp' Schugt, Mar 18, 2005
    #11
  12. On Sat, 19 Mar 2005 03:09:52 +0900, <> 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/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000045

    Or more readable:

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

    Douglas
    Douglas Livingstone, Mar 18, 2005
    #12
  13. Guest

    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!
    , Mar 19, 2005
    #13
  14. Guest

    Douglas Livingstone wrote:
    > On Sat, 19 Mar 2005 03:09:52 +0900, <>

    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 :)
    , Mar 19, 2005
    #14
  15. On Sat, 19 Mar 2005 10:14:52 +0900, <> wrote:
    > Then perhaps "lazyness" and "I'm right you're wrong" better describe
    > your attitude than ours :)
    >


    Quite possibly ;-)
    Douglas Livingstone, Mar 19, 2005
    #15
  16. Guest

    wrote:
    > 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
    , Mar 19, 2005
    #16
  17. Glenn Parker Guest

    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 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/>
    Glenn Parker, Mar 19, 2005
    #17
  18. ES Guest

    Glenn Parker wrote:
    > 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 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/benchmark.php?test=all&lang=ruby&sort=fullcpu
    ES, Mar 19, 2005
    #18
  19. * (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);}
    Nikolai Weibull, Mar 19, 2005
    #19
  20. Guest

    Glenn Parker wrote:
    > 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 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
    , Mar 20, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brett Trost

    Fibonacci problem

    Brett Trost, Jan 22, 2004, in forum: Perl
    Replies:
    2
    Views:
    1,006
  2. fighterman19
    Replies:
    11
    Views:
    800
    Karl Heinz Buchegger
    Sep 8, 2003
  3. Fibonacci numbers

    , Oct 10, 2003, in forum: C++
    Replies:
    28
    Views:
    1,358
    yousafzai
    Jun 5, 2011
  4. Alex Vinokur
    Replies:
    0
    Views:
    451
    Alex Vinokur
    Oct 29, 2003
  5. Lance

    STL for Fibonacci Heap??

    Lance, Dec 1, 2003, in forum: C++
    Replies:
    5
    Views:
    1,338
    Dietmar Kuehl
    Dec 2, 2003
Loading...

Share This Page