3 ms·

A nitpick: > If we wanted to compute a single term in the sequence (e.g. F(n)), there are a couple of algorithms to do so, but some algorithms are much faster

A nitpick: > If we wanted to compute a single term in the sequence (e.g. F(n)), there are a couple of algorithms to do so, but some algorithms are much faster than others. If we wanted only a single term in the sequence, we would just use the closed-form equation, which takes O(1) bigint arithmetic operations, F(n) = (phi^n - (-phi)^-n) / sqrt(5) (Where phi is the golden ratio.) But if what's needed is the entire sequence F(0) up through a chosen F(n), then the algorithms in this article come in handy.

jfarmer 12y ago
That quickly fails due to the nature of floating point arithmetic.
andrewla 12y ago
To pick a little further at this nit; bigint is no good, right? The only way to compute phi^n with bigints is to do an O(log n) operations in the algebraic integers Z(5) (similar to exponentiating complex integers). Doing it with floats/doubles is a little more reasonable for an O(1) approach, but even that approach breaks down for large enough n.
nayuki 12y ago
Regarding the computation of a single term: No, the well-known Binet formula involving phi is unsuitable because it uses real numbers. See these detailed comments about handling quadratic surds properly, which is effectively the same as the fast doubling algorithm: - Chinjut: https://news.ycombinator.com/item?id=9316574 https://news.ycombinator.com/item?id=9316574 - xyzzyz: https://news.ycombinator.com/item?id=9316144 https://news.ycombinator.com/item?id=9316144 Regarding the computation of F(0) through F(n): No, this is not true either. The matrix method and fast doubling only compute O(log(n)) terms of the sequence, not the complete sequence from 0 to n.
- _delirium 12y ago
  Ah, right, I am wrong on both counts. Thanks for the pointers!
shasta 12y ago
As andrewla notes, big int operations aren't O(1) in an apples-to-apples comparison. In fact, if you work out all of the math for a Z(5) implementation, this approach is essentially the same as the fast matrix exponentiation approach from the article. As I recall, they differ only by an application of some Fibbonaci identity (because of these identities, there are many equivalent recurrence relations).

jfarmer 12y ago

That quickly fails due to the nature of floating point arithmetic.

andrewla 12y ago

To pick a little further at this nit; bigint is no good, right? The only way to compute phi^n with bigints is to do an O(log n) operations in the algebraic integers Z(5) (similar to exponentiating complex integers). Doing it with floats/doubles is a little more reasonable for an O(1) approach, but even that approach breaks down for large enough n.

nayuki 12y ago

Regarding the computation of a single term: No, the well-known Binet formula involving phi is unsuitable because it uses real numbers. See these detailed comments about handling quadratic surds properly, which is effectively the same as the fast doubling algorithm: - Chinjut: https://news.ycombinator.com/item?id=9316574 https://news.ycombinator.com/item?id=9316574 - xyzzyz: https://news.ycombinator.com/item?id=9316144 https://news.ycombinator.com/item?id=9316144 Regarding the computation of F(0) through F(n): No, this is not true either. The matrix method and fast doubling only compute O(log(n)) terms of the sequence, not the complete sequence from 0 to n.

_delirium 12y ago
Ah, right, I am wrong on both counts. Thanks for the pointers!

shasta 12y ago

As andrewla notes, big int operations aren't O(1) in an apples-to-apples comparison. In fact, if you work out all of the math for a Z(5) implementation, this approach is essentially the same as the fast matrix exponentiation approach from the article. As I recall, they differ only by an application of some Fibbonaci identity (because of these identities, there are many equivalent recurrence relations).