Talk:Fibonacci sequence: Difference between revisions
→Alternative: Thanks - you caught the what I hope is one of the last of *many* formulae with Gerard accidentally made invisible :(
(added a comment concerning concern for speed. -- ~~~~) |
(→Alternative: Thanks - you caught the what I hope is one of the last of *many* formulae with Gerard accidentally made invisible :() |
||
| (23 intermediate revisions by 6 users not shown) | |||
Line 1:
==recursion too slow?==
The task states
Line 5 ⟶ 6:
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).
: Just for this <tt> RC </tt> task, speed shouldn't be an issue, I would think. As an aside, it would irk me to no end if I included an example that's slower than molassas in January. But many programmers who reuse (their) code
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).
Line 48 ⟶ 49:
== Alternative ==
<!-- Sorry for the "changing" of someone's comment, but I couldn't read the original formula, so I though an enlarged version would be beneficial to everyone. --- Gerard Schildberger. -->
Fibonacci sequence can also be calculated using this formula.
<big><big><math>Fib[n] = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}}</math></big></big>▼
▲<math>Fib[n] = \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n \sqrt{5}}</math>
Size of the floating-point type (float, double, long double etc..) will limit how high n can be calulated.
Line 118:
:It would also be good to maybe confirm some of the Lucas/Fibonacci identities mentioned in the Lucas wp article. --[[User:Paddy3118|Paddy3118]] 20:33, 24 May 2012 (UTC)
The name is from MathWorld. I doodled the following:
<lang python>>>> def fiblike(start):
Line 159:
:Gerard, I hope you like [[Fibonacci n-step number sequences]] and thanks for the inspiration! --[[User:Paddy3118|Paddy3118]] 21:59, 24 May 2012 (UTC)
:: Hell's-Bells, ahhh likes all kinds!! I have a handy-dandy, slicer-dicer, one-size-fits-all Swiss Army knife
::: As an aside, to quote someone long ago: the one language all programmers know is profanity. -- [[User:Gerard Schildberger|Gerard Schildberger]] 22:11, 24 May 2012 (UTC)
▲===trade mark===
Slightly off-topic, by what the hey!!
Line 179 ⟶ 178:
:: No, nobody asked. I understand domain names would be hard to add a trade-mark symbol, but RC uses/references/quotes that trademarked site a lot, and I thought it would be a show of "good faith" on RC's part to honor that site with at least a TM symbol. -- [[User:Gerard Schildberger|Gerard Schildberger]] 20:42, 25 May 2012 (UTC)
==ECMAScript 2015 (ES6) recursive implementations exploration==
I wrote this little exploration of various recursive takes on Fib generation a while ago: http://pastebin.com/ExTuYkAE Among other things it takes time consumption and multiple uses into account. Might look a bit foreign to many as it uses the new ES6 fat arrow syntax for pretty much everything.
If someone wants to incorporate it into the JavaScript section, be my guest!
== Ocaml matrix example remark ==
I notice someone edited the Ocaml matrix example to say 'actually O(n*n)'. I can't identify who that was now, but unless someone can explain/justify it I will remove it, as it seems to be incorrect. [[User:TobyK|TobyK]] ([[User talk:TobyK|talk]])
==Two formulae in SuperCollider Recursive contribution invisible to most browsers==
The two formulae in the preface to the Recursive section of the SuperCollider examples are invisible to most browsers. Perhaps they were edited and tested in FireFox ? The majority of browsers, including Chrome, IE/Edge, Safari etc, use the part of the HTML code which displays the server-side graphic file for each formula. Only a minority, which happens to include FireFox, locally process the MathML expression, and only then if requisite fonts are installed. As the MediaWiki processor generates separate code to support each approach, visibility of formulae in Firefox doesn't guarantee successful code compilation and visibility to the majority of browsers.
Redundant space inside <math> tags can be one source of this problem. Perhaps the author can experiment and check the result in in Chrome, IE/Edge or Safari ? [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 11:38, 15 October 2016 (UTC)
:OK; I'll take a look into it [[User:Telephon|Telephon]].
:I can reproduce it, yes. I had just tried and it worked on Firefox. Is there an alternative that would work on other browsers?--[[User:Telephon|Telephon]] ([[User talk:Telephon|talk]]) 14:12, 15 October 2016 (UTC)
:: Good question - for the set membership 'drawn from', we can use the HTML entity (ampersand '''isin''' semicolon), though it comes out smallish on its own <pre><big>∈</big></pre> In isolation, neither <pre><math>n</math></pre> nor <pre><math>\mathbb{N}</math></pre> choke the preprocessor, but it does seem to have difficulty with both <pre><math>\mathbb{N_0}</math></pre> and <pre><math>\mathbb{Z}</math></pre>
:: Would you be happy to fall back to English descriptions of the sets ? It's possible that these limitations will eventually be overcome in MediaWiki or the Math extension. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 14:59, 15 October 2016 (UTC)
Yes, a description in English is really easy here. Thank you for looking into it in detail! --[[User:Telephon|Telephon]] ([[User talk:Telephon|talk]]) 15:34, 15 October 2016 (UTC)
==Possibly misleading use of 'iterative' in Haskell subsection ?==
Hi [[User:WillNess|WillNess]] , I notice that the ('''fibonacci by folding''') Haskell example has just been moved under the heading 'Iterative'. I wonder if that doesn't risk confusing a little, or even possibly misleading ?
Folds are implemented recursively (either directly or indirectly) in the Prelude, and are generally understood as 'recursion schemes' in the sense of Meijer et al. (See, for example, http://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/ and the much-read paper which it references http://maartenfokkinga.github.io/utwente/mmf91m.pdf).
I also notice that other examples which have ended up in the 'Iteration' section might risk compounding a reader's confusion – they are either implemented by direct and immediate recursion on helper functions like '''go''' and '''next''', or are expressed in terms of '''zipWith''', '''scanl''' etc, which are also implemented as recursive functions.
Perhaps 'iteration' is not quite the clearest or best-fitting term to use here ?
[[User:Hout|Hout]] ([[User talk:Hout|talk]]) 19:31, 2 February 2017 (UTC)
FWIW, I would argue that if we need to subdivide, then the main distinction here is '''memoising vs not memoising'''. If we feel a need to subdivide further, and perhaps capture something like the category now labelled "Iterative", then perhaps what we really mean here is closer to ''direct and indirect recursion'' ? [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 19:44, 2 February 2017 (UTC)
| |||