Talk:Fibonacci sequence

The task states

Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).

while the parenthetical comment is true, I'm wondering what to make of it. Is there any application of FIbonacci numbers where "computation time" is actually an issue? Do we care about computation time at all? If we do, I'd use neither an iterative nor a recursive approach but an analytic solution through phi (I added that to IDL, I see from a glance that at least the D solution has one of these as well).

I guess my question is: if we care about speed, why demand that the solution be iterative or recursive? Or, more generally, if performance is a concern, why demand any particular approach at all -- since the "best" approach for any one task is bound to be different for different languages. (Something with decent tail recursion might have recursive solutions faster than iterative ones and what-have-you).

And yet other way 'round: does performance matter here on RC? Almost all code samples I've ever contributed would have to be changed if I cared about speed of execution -- I've been trying to optimize for clarity of exposition instead. Is there some kind of guideline / a practical consensus / an ongoing discussion about this somewhere?Sgeier 14:16, 7 April 2008 (MDT)

I strongly doubt that the analytic version is actually faster than fast solutions using integer arithmetic (manipulating expression trees should be more expensive than manipulating integers). However, a fast solution wouldn't use the recursion formula directly, but use the fact that

    /1 1\ n    /F<sub>n+1</sub> F<sub>n</sub>  \
   (     )  = (                                 )
    \1 0/      \F<sub>n</sub>   F<sub>n-1</sub>/

together with a fast exponentiation algorithm to calculate F_n in O(log n) time (in comparison, the naive iterative solution has O(n) time).

According to the general question if clarity or performance should be more important: I'd say clarity always wins over "programming tricks" performance (e.g. in C and C++ always use n/2 instead of n>>1 if your goal is to calculate the half of an integer), however algorithmic performance should be considered, if it doesn't conflict with the goals of the task (e.g. if the goal of a task is to explicitly show how to write a recursive function, replacing it with a faster iterative version obviously isn't a good idea). However, clarity is important, so the algorithmic performance should be weighted against it (also, the complexity of an algorithm shouldn't get too high IMHO; if you want to present complicated algorithms, there are other sites like literateprograms for that). Of course ultimately it's always the task which sets the rules. --Ce 15:21, 7 April 2008 (MDT)

negative n errors

The task description contains: "Support for negative n errors is optional." Negative n isn't an error; while conventionally only the definition for positive n is given, the Fibonaccy sequence is actually defined for arbitrary n. You can rewrite the recursion formula F_n+1=F_n+F_n-1 as F_n-1=F_n+1-F_n and thus extend the recursive definition to negative values. This results in

$F₀=0$

$F_-n=(-1)ⁿ⁺¹F_n$

If the word "errors" is removed from the description, it becomes reasonable. --Ce 14:40, 7 April 2008 (MDT)

I've now fixed that. --Ce 08:35, 14 October 2008 (UTC)

Clarified?

In the task page there is the note "This task has been clarified. Its programming examples are in need of review...". I am not sure what exactly has been clarified, but at least the value of fibonacci(0) seems to be wrong in many language examples.

Should the language examples that have been fixed be marked somehow so that we will know when all the examples have been corrected? (Or perhaps mark all examples and then remove the mark when it has been checked.) --PauliKL 15:14, 14 April 2009 (UTC)

I just tried to fix what I could figure out based on that definition. Some of the iterative examples may still be partially wrong, but I think I got a lot of the recursive examples. --Mwn3d 18:17, 14 April 2009 (UTC)

Rules abuse!

Take a look at the third example under BASIC, Iterative. I stretched the meaning of generate and just predetermined all the numbers that can be handled by my chosen data type (LONG; 32-bit signed, without support for F_n where n < 0) and dumped them into an array. Bam! Almost instant results! :-) -- Eriksiers 20:48, 7 August 2009 (UTC)