Talk:Fibonacci sequence/Archive 4

Computation Time of n-th Fibonacci Number.

The article on Wikipedia writes the following: These last two identities provide a way to compute Fibonacci numbers recursively in O(log(n)) arithmetic operations and in time O(M(n) log(n)), where M(n) is the time for the multiplication of two numbers of n digits. I think this can be improved, using that M(2n) is at least 2*M(n), as the time is at least linear (in order to read all input bits). Thus M(n) < 1/2 M(2n) and so using the telescope sum property of this recursion formula, one would get O(M(n)) instead of O(M(n) * log(n)). Frank Stephan — Preceding unsigned comment added by 116.14.205.177 (talk) 00:53, 27 January 2021 (UTC)

This sounds right, but we need a published source with the correct time bound. Do you know of one? —David Eppstein (talk) 06:02, 27 January 2021 (UTC)

A little bit different, but the n-th Fibonnaci can be computed directly (no recursion or iteration). Bubba73 ^{You talkin' to me?} 06:10, 27 January 2021 (UTC)

You mean the formula involving taking the golden ratio to powers? I don't think it's correct to say that it can be computed any more directly that way. It gives a closed-form formula, but a closed-form formula and a computation are not the same thing. There are three problems with using that formula to compute: (1) you have to be able to exponentiate, and that is not generally a built-in machine operation, and (2) you need to compute irrational square roots to large numbers of digits, proportionally the same number of digits as you need for the Fibonacci number you are trying to compute, and again that is not generally a built-in operation, and (3) you have to worry about numerical accuracy of non-integer arithmetic being small enough that you get the right result when you round it to an integer. Instead, the recursion the IP is talking about can be expressed in a different way as a closed-form exponentiation of 2x2 integer matrices, still requiring (matrix) exponentiation but avoiding all the other numeric issues. The recursion is just what you get when you apply binary exponentiation to this matrix formula and simplify a little using the symmetry of the matrix. —David Eppstein (talk) 07:49, 27 January 2021 (UTC)

The "direct computation" using phi^n is exactly (one, but not the best method) which yields the log2(n) multiplications and squarings. Simply stated: Computing x^n is O(log n). — MFH:Talk 19:07, 11 September 2021 (UTC)

It is a logarithmic number of operations, but that is very different from saying that it takes logarithmic time. For this sort of computation, it is not reasonable to use a model of computation where arithmetic operations are assumed to take constant time; that's only good for problems where the numbers stay small, and here they don't. To compute the time properly, you have to take into account the length of the numbers involved and the time for arithmetic operations on numbers of that length. —David Eppstein (talk) 19:36, 11 September 2021 (UTC)

Comments:

• The complexity assertion quoted at the beginning of the thread is not in the reference, and thus not sourced. It is not an immediate consequence of the identities or of the content of the source. Moreover, it is incomplete as the space complexity is not considered.
• Using the golden ratio for estimating the complexity is not a good idea, as the requires to estimate the number of digits of the golden ratio that are needed, to compute them, and to do the whole computation with this number of digits.
• One of the standard way for computing $F_{n}$ is given at the beginning of § Matrix form: If ${\textstyle A={\begin{bmatrix}1&1\\1&0\end{bmatrix}},}$ then $F_{n}$ is the entry of the second row and first column of $A^{n-1}.$ So, $F_{n}$ can be computed by using exponentiation by squaring applied to $A^{n-1}.$ As squaring a 2×2-matrix needs 5 multiplications and 4 additions, the whole computation needs $5\lfloor \log _{2}(n-1)\rfloor$ multiplication, and at most the same number of additions. Moreover, as each square doubles the size of the integers, the whole computation takes at most twice the time of the last squaring, and needs an auxiliary space that is at most twice the size of the output. Thus, the time complexity is $O(M(n))$ for $O(\log n)$ arithmetic operations; this is exactly the claim of the first post of this thread, but with a much more simpler algorithm.
• I have no source under hands for these assertions, but the use of matrix form and exponentiation by squaring are standard. The estimation of the complexity when each step doubles the size is standard in other contexts. For example for proving that using Newton's method for computing the inverse or the square root of an integer gives a complexity of $M(n),$ where n is the number of desired digits.

So, I suggest to remove the paragraph quoted at the beginning, and to replace it by a section on the different sandard methods of computation, with complexity estimation. There are plenty of sources, as textbooks that present the different methods of implementation (recursive, recursive with memoization, iterative, ...) often takes Fibonacci sequence as an example because it is a simple case where the method of implementation may change dramatically the complexity. D.Lazard (talk) 08:46, 12 September 2021 (UTC)

A version of the claim can be found in Matoušek's "Thirty-three miniatures" (in fact it is Miniature 1): he uses exponentiation by squaring of the matrix to compute the nth Fibonacci number in at most 2 log(n) multiplications of 2-by-2 matrices. He then goes on to note that, because the Fibonacci numbers grow exponentially, the individual arithmetic operations are themselves slow (but does not attempt to quantify this, or to synthesize an overall bound). (Our present article frames this slightly differently -- in terms of the entries of the matrix rather than the matrices themselves -- but of course it's essentially the same procedure.) --JBL (talk) 13:46, 12 September 2021 (UTC)

There are lots of sources for the fast computation method itself, whether by powering matrices or (what amounts to the same thing) using the index-doubling recurrences. I think one of the earliest may be in one of the letters of Dijkstra. But what we need is not just that, but the detailed time analysis. —David Eppstein (talk) 19:26, 12 September 2021 (UTC)

Fibonacci's indexes differ by two (2!!) from ours

@TheMathCat and D.Lazard: It is really surprisingly strange. But:

1. The writing of Fibonacci is obviously not easy to read.
2. It is really extremely strange that he starts with index 0.

But there is no doubt about. Look at the "source (right of the page in the red rectangle)": More easily than the 0 to read is the index XII = 12 where Fibonacci places the value 377. We have $377=F_{14}$. So I reverted your edit. -Nomen4Omen (talk) 15:34, 15 September 2022 (UTC)

I think you're right, the index zero is a bit away at the top and the corresponding Fibonacci numbers are below the indices, so in that document, 1 is F_0, 2 is F_1, and so on. Well spotted (and sorry for reverting). TheMathCat (talk) 15:43, 15 September 2022 (UTC)

(edit conflict) OK, you reverted me just before my self revert. On the table on the right, there is a large vertical space between the first index and the first value (1). So, I guessed that it was a title or a caption, which it is not. By the way, it would be interesting to know which word is used for "zeroth". I am unable to decipher it. D.Lazard (talk) 15:49, 15 September 2022 (UTC)

Yes, the Latin word for zeroth would be really interesting. And more than that, I always thought that the Mayas had the zero and not the medieval Europeans. I do not have an idea why Fibonacci starts the indexing with 0, especially the indexing!!! If we have learnt Latin at school we may remember zero=nullus, but there is not known a roman numeral for zero. And for the ordinals we may remember 1st=primus, 2nd=secundus, 3rd=tertius, 4th=quartus, 5th=quintus, 6th=sextus, 7th=septimus, 8th=octavus, 9th=nonius, 10th=X, 11th=XI, 12th=XII. But 0th=?? This does not even exist in good English!

Every medieval guy would have well understood if Fibonacci had started with $F_{1}=1,F_{2}=1,F_{3}=2,...$. But there cannot be a doubt, because the higher indices are easier to read and even roman numerals and obviously he associates index XII = 12 with 377, whereas we have $377=F_{14}$. –Nomen4Omen (talk) 16:22, 15 September 2022 (UTC)

I can read "primus" from "${\mathfrak {p'm}}$" (last diacritic omitted), "secundus" from "${\mathfrak {scd's}}$", "tercio" or "tertio" from "${\mathfrak {tcio}}$" or "${\mathfrak {trio}}$". Similarly for most following ordinals. But I cannot read the first line of the table. Can someone do? D.Lazard (talk) 17:09, 15 September 2022 (UTC)

Very good! In my opinion, although we do not know the Latin word for zeroth, there is no doubt about the numbering. As good WP-editor you could enter your insights close to https://en.wikipedia.org/wiki/File:Liber_abbaci_magliab_f124r.jpg/Summary or similar. –Nomen4Omen (talk) 17:32, 15 September 2022 (UTC)

I guess, I found some answers for our questions above in that he describes the development of the rabbits in 1 year:

1. Our index 0th == present, the date he starts with. (This is not an ordinal.)
2. After the first == primus month the 1st birth occurs, yielding 2 pairs of rabbits.
3. Latin ordinals from here to the 9th month.
4. The next 3 months in Roman cyphers X, XI, XII.

–Nomen4Omen (talk) 16:29, 16 September 2022 (UTC)

https://www.math.utah.edu/~beebe/software/java/fibonacci/liber-abaci.html --SilverMatsu (talk) 04:41, 19 September 2022 (UTC)

Also, there is an article about 0 on the Latin language edition of Wikipedia. (See https://la.wikipedia.org/wiki/0). --SilverMatsu (talk) 05:12, 19 September 2022 (UTC)

Submarine?

@David Eppstein: How on Earth does WP:SUBMARINE apply? The link wasn't piped at all, let alone in a way which obscures the target. – Scyrme (talk) 20:57, 22 November 2022 (UTC)

It looked like you were piping a link targeted to Golden ratio § In nature to have the link text "Parastichy". But now I see that you are instead adding a separate link to Parastichy to the see-also link at the top of a section. So SUBMARINE is incorrect, but the link is still unhelpful, because Parastichy doesn't say anything about Fibonacci numbers. —David Eppstein (talk) 21:49, 22 November 2022 (UTC)

@David Eppstein: Parastichy is a stub and were the article to be expanded the occurrence of Fibonacci sequences would certainly be a relevant topic that would warrant inclusion. While it's true that the article presently lacks that coverage, that would only be a reason for not linking it as "further information". However, the opening sentence of the section in this article begins by listing several examples of parastichy, including one (that of pine cones) which is also explicitly also given at Parastichy. The connection sufficiently clear for a "see also". The link also encourages the addition of relevant content by making the stub easier to find; delinking it only encourages further neglect.

I added it as a "see also" in order to be less intrusive and avoid rewording the text, however, I don't object to incorporating the link into the text of the article more naturally, rather than tacking it on as a "see also", if that's what you'd prefer. Perhaps: In 1830, K. F. Schimper and A. Braun discovered that the parastichies of plants were frequently expressed as fractions involving Fibonacci numbers? – Scyrme (talk) 22:20, 22 November 2022 (UTC)

(As a sidenote, regarding being "helpful", I personally would've found it helpful. I was looking for parastichy earlier and it would've been nice if it were easier to find. That's why I added it to this article: I expected to find it here in the first place, but found that although it lists several examples it didn't actually name the topic it was referring to. I had to look somewhere else to find it.) – Scyrme (talk) 22:28, 22 November 2022 (UTC)

Wouldn't it be more helpful to incorporate that word into the actual text of the article rather than having the baffling "see also parastichy" at the top of a section? —David Eppstein (talk) 22:29, 22 November 2022 (UTC)

... I literally suggested that above. – Scyrme (talk) 22:33, 22 November 2022 (UTC)

The latest edit looks good to me. JBL (talk) 23:48, 22 November 2022 (UTC)

Requested move 1 March 2023

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: moved to Fibonacci sequence. In this discussion, both the current title and the proposed title proved to be controversial. The most hotly debated question was in the interpretation of WP:PLURAL – should this article be pluralized as a topic that is naturally the set or family of [numbers], or should it remain singular under the standard guidance? Both interpretations were supported by various participants, and neither side appeared to convince the other. For other angles of argument, the singular title was shown to be more WP:CONSISTENT with other articles about classes of numbers, while the plural title was shown to be a more common name than the singular. This prevented a consensus from forming as to whether "Fibonacci numbers" was preferable to "Fibonacci number"... but those two titles were not the only titles proposed in the discussion.

The title "Fibonacci sequence" was proposed early in the discussion, and attracted substantial support. Arguments in favor of "Fibonacci sequence" included its wide WP:RECOGNIZABILITY and its avoidance of problems with the other names (the "sequence" title means consistency with number articles becomes a non-issue, and sources use it with a similar frequency to the plural title). "Fibonacci sequence" was also identified as an acceptable compromise title by several users whose first preference was something different. Support for "Fibonacci sequence" was not perfectly unanimous – one user argued that the article is more WP:PRECISEly about the numbers rather than the sequence, and another argued that "Fibonacci sequence" was not sufficiently the WP:COMMONNAME – but the arguments against "Fibonacci sequence" were contested by other editors, and ultimately did not sway the overall tide of support. Consequently, I find a consensus for moving the article to Fibonacci sequence. (non-admin closure) ModernDayTrilobite (talk • contribs) 15:44, 10 March 2023 (UTC)

---

Fibonacci number → Fibonacci numbers – The plural makes more sense, because it is a sequence of numbers, not just one singular Fibonacci number, as the current title implies. The article mostly uses "Fibonacci numbers" or "Fibonacci sequence", not the singular "Fibonacci number". Mucube (talk • contribs) 00:41, 1 March 2023 (UTC)

• Oppose. Our articles in Category:Integer sequences can be named for the individual members, in singular (Catalan number), or in some cases named for the whole sequence, in singular (Sylvester's sequence). I don't see any justification among the exceptions listed in MOS:PLURAL for doing it differently, and we certainly shouldn't do it differently for just this one article than for the rest of the category. —David Eppstein (talk) 01:38, 1 March 2023 (UTC)
• Oppose What about prime number, Catalan number, perfect number, composite number, ...? Singular seems to be the way we've done it. —Quantling (talk | contribs) 01:40, 1 March 2023 (UTC)

  Prime, composite, and perfect are extremely different from Fibonacci. While it's true that one can place the prime or composite or perfect numbers in a sequence, their defining properties do not reference the existence of the sequence or the indexing of the sequence, it is not clear a priori that they are indexed by the natural numbers (there might only be finitely many perfect numbers). "Is 233 prime?" is a meaningful question; "Is 233 Fibonacci?" is not really. --JBL (talk) 18:41, 1 March 2023 (UTC)

  Sure it is. Just check whether $5\cdot 233^{2}\pm 4$ is a square. In this case $5\cdot 233^{2}-4=521^{2}$, so yes, it is Fibonacci. Or "it is a Fibonacci number", if you prefer that grammar. In any case, it's a question you can answer for individual numbers with no reference to the sequence or its recurrence. —David Eppstein (talk) 18:49, 1 March 2023 (UTC)

  Perhaps meaningful is in the eye of the beholder. Not only is 233 a Fibonacci number, it is a Fibonacci prime and a Ramanujan prime! —Quantling (talk | contribs) 18:49, 1 March 2023 (UTC)

  The sentence "233 is a Fibonacci number" is not the same sentence as "233 is Fibonacci"; the latter is stilted and artificial. While I hold David Eppstein's opinions with respect to encyclopedia editing in high regard, I think it's safe to say that no one has ever before written the sentence "We define a positive integer f to be Fibonacci if one of $5f^{2}\pm 4$ is a perfect square". This is entirely unlike the other examples here (prime, composite, perfect), and this renders the argument by analogy unpersuasive. "A Fibonacci prime" works because of an unrelated convention about special kinds of prime numbers, not because of anything to do with Fibonacci numbers. (I happen think that moving articles from one plausible title to another is generally a bad idea and a waste of time, except when it comes to a minor personal obsession with fake royalty, so I'm not going to cast a vote in this discussion. But the analogy offered here is not at all compelling.) --JBL (talk) 19:16, 1 March 2023 (UTC)

  So numbers named after people (like Fibonacci numbers and Bell numbers) should be given a plural article title while articles whose name is an adjective (like Catalan numbers and prime numbers) should be singular, because grammar? That makes even less sense than most of the arguments here. —David Eppstein (talk) 19:32, 1 March 2023 (UTC)

  Hmm, the index of a Fibonacci number in the sequence of Fibonacci numbers is mathematically meaningful in the sense that gcd(F_i, F_j) = F_{gcd(i, j)}. I guess that that could be construed as an argument that "Fibonacci number" is too isolating. —Quantling (talk | contribs) 19:42, 1 March 2023 (UTC)

  David, I don't recognize anything to do with my point in your restatement of it. I don't know if you're intending this or if it's just how the internet makes everything worse, but your comments toward me in this sub-thread seem to fall somewhere between "snarky" and "aggressive". I have advised other editors in the past that, while I do not always agree with you, I find your perspective to be always thoughtful and worth considering; I hope it is not too much to ask a degree of consideration in return. In any case, I don't have anything further substantive to add to this discussion. --JBL (talk) 20:21, 1 March 2023 (UTC)

• Moral support. Per WP:CONSISTENT, I wouldn't want to move just this one article right now, but I agree with the logic of the nomination. In my opinion, classes of numbers which are defined by some inherent property like Prime number, Perfect number, and Composite number (where the sequence is merely a trivial ordering of the numbers which happen to satisfy that property) should be singular, but sequences (i.e. ordered lists of numbers defined by their relation to previous elements or in terms of some index variable) like Catalan numbers should be plural. I recommend proposing this at WP:NCPL and advertising it on WP:NCNUM, MOS:MATH, and WP:WPMATH. If there are any edge cases which appear to fall in both camps, we should distinguish between which property is the definition and which property is the theorem. -- King of ♥ ♦ ♣ ♠ 04:59, 1 March 2023 (UTC)

  It is easy to write property-based rather than sequence-based definitions for the Fibonacci numbers (for instance, that they are the numbers $x$ for which one of $5x^{2}\pm 4$ is square) and sequence-based rather than property-based definitions for the prime numbers (for instance, they are the sequence one gets by applying the sieve of Eratosthenes). So I don't think this distinction is particularly meaningful. And in any case, if it were the sequence rather than the numbers that were most essential here, we already have a different convention for that: name the article for the (singular) sequence. —David Eppstein (talk) 06:44, 1 March 2023 (UTC)

  I've already addressed that concern in my last point - which one is the primary definition? That might be a little subjective at times, but we deal with subjectivity at RM all the time. In this particular case, Fibonacci sequence does work and is actually more common (count me as a support for the third option), but Catalan numbers are not as commonly referred to as the Catalan sequence. For that sequence I would prefer "Catalan numbers" over "Catalan number" for the reason I described. -- King of ♥ ♦ ♣ ♠ 08:46, 1 March 2023 (UTC)

• Third option -- move to "Fibonacci Sequence" instead. It's the sequence that is the object under study, not the individual numbers. Barring that, I still support the move. David Eppstein, if you don't see applicability in WP:PLURAL, you're not looking very hard. It even calls out this very type of article: Things like Maxwell's equations, Legendre polynomials, Chebyshev polynomials, [the] Cauchy–Riemann equations, etc. The topic is naturally the set or family of equations, although in some contexts they may be referred to in the singular. (That is, such a polynomial—for example—is of interest only because it is part of the polynomial sequence called the Chebyshev polynomials, and the sequence is thought of for most purposes as a unit.) Similarly, one is much more likely to mention Arabic numerals than a particular Arabic numeral. Indeed, a Fibonacci number is only of interest because it's one of the set of Fibonacci numbers. Still though, this sequence is traditionally defined as a sequence, and not as a property that some numbers possess and others don't (like prime numbers). Quantling's analogy fails for this very reason. 35.139.154.158 (talk) 06:47, 1 March 2023 (UTC)

  Those are collections of things that don't make sense to break out of the collection and study individually. Maxwell's equations only make sense as a whole. You wouldn't generally talk about something as being "one of Maxwell's equations", by itself. It is perfectly normal to talk about an individual number like 144 as being a Fibonacci number, though, as in fact we do on 144 (number), or to talk about the properties that an individual Fibonacci number might have, not based on its position in the sequence, as we do at Fibonacci prime. That is the distinction made at MOS:PLURAL: does it make sense to talk about these individually or are they primarily a collective set? —David Eppstein (talk) 07:09, 1 March 2023 (UTC)

• Oppose per WP:COMMONNAME. The plural makes no sense, as the phrase “the Fibonacci numbers” is rarely used, since when considered as whole, the Fibonacci numbers are called the Fibonacci sequence. This is a big difference with Legendre polynomials and Chebyshev polynomials polynomials ("Legendre polynomials sequence” and "Chebyshev polynomials sequence” seems, at least, pedantic). D.Lazard (talk) 10:25, 1 March 2023 (UTC)

(edit conflict)

• Support, per WP:COMMONNAME and the literature:

Google	Scholar	Books
"Fibonacci numbers"	36.700	96.800
"Fibonacci number"	18.700	41.900
"Fibonacci sequence"	31.200	83.500

Moving to Fibonacci sequence seems ok too. - DVdm (talk) 10:33, 1 March 2023 (UTC)

• Support, as the article is about the sequence, not about individual numbers. Being a "Fibonacci number" is hardly an interesting property of an individual number. JIP | Talk 10:38, 1 March 2023 (UTC)
• Support alternate move to Fibonacci sequence so there does not need to be any more back and forth as to whether it's plural or not. ᴢxᴄᴠʙɴᴍ (ᴛ) 12:21, 1 March 2023 (UTC)
• Oppose moving to the plural, for consistency with other Wikipedia articles. I don't think raw search-engine results are a meaningful test of "commonality", and I don't think picking "the common name" is actually a meaningful standard to follow in this case. It's not like we're having to decide whether to use "Fibonacci" or "Fibonacci–Pingala", for example; the decision isn't between different terms, but different grammatical forms of the same term. XOR'easter (talk) 15:50, 1 March 2023 (UTC)
• oppose per WP:PLURAL, no problems with moving to Fibonacci sequence—blindlynx 21:02, 1 March 2023 (UTC)
• Oppose The proposed name is no better than the current one, which is already ugly, and something I haven't encountered outside Wikipedia. The primary search term is far more likely to be Fibonacci Sequence. That's what we SHOULD be moving this to. HiLo48 (talk) 23:25, 1 March 2023 (UTC)
• Oppose. The presumption that titles should be singular is not overcome. A singular Fibonacci number is sensible and not comparable to, say, a singular Maxwell's equation or a singular Cauchy–Riemann equation. Also oppose Fibonacci sequence. A phrase like Fibonacci number and its plural should be counted together for WP:COMMONNAME purposes. Adumbrativus (talk) 05:10, 7 March 2023 (UTC)

  @Adumbrativus: A paper which mentions "Fibonacci number" is also very likely to mention "Fibonacci numbers" and vice versa. So you can't just add the numbers together because the mentions are not unique. -- King of ♥ ♦ ♣ ♠ 03:44, 8 March 2023 (UTC)

• Support move to Fibonacci sequence. Favonian (talk) 18:55, 7 March 2023 (UTC)
• Support since this is a "naturally plural" concept. Also support Fibonacci sequence as second choice (I think it's a more obscure term, and arguably not the WP:COMMONNAME, though it is probably WP:RECOGNIZABLE and COMMONNAME is primarily a restatement of RECOGNIZABLE in the first place).  — SMcCandlish ☏ ¢ 😼  01:40, 9 March 2023 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Opposition to "Fibonacci sequence" was never solicited

@ModernDayTrilobite: Of course there were very few comments posted that opposed the name "Fibonacci sequence" because that option was not on the table! If comments had been solicited on that then people would have commented and we would actually know whether it was a consensus decision. Please, if you want the title to be "Fibonacci sequence" then put it in an RfC. Yes, I know that you already renamed the page to something that wasn't under consideration, but you can reverse that. —Quantling (talk | contribs) 21:22, 10 March 2023 (UTC)

The title "Fibonacci sequence" was initially proposed on March 1, roughly nine and a half days before I closed the RM. After the initial proposition was made, virtually every participant in the RM expressed an explicit opinion on "Fibonacci sequence" as a title. In a case like this, where an alternate title is actively discussed over the course of an RM, it's very possible (and not uncommon) for that alternate title to achieve consensus. (Finally, I don't personally want any given title - it'd be a supervote if I did.) ModernDayTrilobite (talk • contribs) 14:48, 13 March 2023 (UTC)

Thank you @ModernDayTrilobite for your response. I apologize for my writing "if you want ..."; I stand corrected. Count me among those who responded before the suggestion of "Fibonacci sequence" and count me as one who would generally not get side-tracked to comment on something that wasn't solicited by the RfC. I can see value in allowing these discussions to evolve, but I'd like to see a better process for it. Perhaps one could officially amend the RfC, either at the top or in the comments at the time of its occurrence, in a highlighted, readily apparent way, to solicit comments on the new possibility. Ideally, only then should the new possibility become fair game. Thanks —Quantling (talk | contribs) 16:28, 13 March 2023 (UTC)