Talk:Fibonacci sequence/Archive 4

Archive 1

Archive 2

Archive 3

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)