- **Ruby**
(*http://www.velocityreviews.com/forums/f66-ruby.html*)

- - **Fibonacci Benchmark Correction**
(*http://www.velocityreviews.com/forums/t820352-fibonacci-benchmark-correction.html*)

Fibonacci Benchmark CorrectionThe 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...nacci/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 |

Re: Fibonacci Benchmark Correction* jzakiya@mail.com (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);} |

Re: Fibonacci Benchmark CorrectionNikolai Weibull wrote:
> * jzakiya@mail.com (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 |

Re: Fibonacci Benchmark Correctionjzakiya@mail.com wrote:
> Nikolai Weibull wrote: > >>* jzakiya@mail.com (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 |

Re: Fibonacci Benchmark CorrectionOn Thu, 17 Mar 2005 09:19:46 +0900, jzakiya@mail.com <jzakiya@mail.com> 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. |

[OT] Re: Fibonacci Benchmark Correctionjzakiya@mail.com 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. |

Re: Fibonacci Benchmark Correction* jzakiya@mail.com (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);} |

Re: Fibonacci Benchmark CorrectionOn Thu, 17 Mar 2005 09:59:57 +0900, Nikolai Weibull
<mailing-lists.ruby-talk@rawuncut.elitemail.org> 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 |

Re: Fibonacci Benchmark CorrectionHello Jabari,
On Wed, 16 Mar 2005 22:34:50 +0900, jzakiya@mail.com <jzakiya@mail.com> 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. |

Re: Fibonacci Benchmark CorrectionDouglas Livingstone wrote: > On Thu, 17 Mar 2005 09:59:57 +0900, Nikolai Weibull > <mailing-lists.ruby-talk@rawuncut.elitemail.org> 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. |

All times are GMT. The time now is 12:37 AM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.