3 ms·

Isn't there a constant time implementation using the Golden Mean? What is the advantage of these algorithms over the constant time one? (i.e. Binet's formula)

yaks_hairbrush 10y ago
There is no constant time implementation. Binet's formula uses exponentiation, which gives us log(n) time.
Practicality 10y ago
O(1)? Having all the answers pre-cached would be the only way to do that. Unless there is some kind of quantum computer algorithm that fits this problem well.
- stephencanon 10y ago
  The nth Fibonacci number has O(n) digits, so even reading a cached pre-computed result from memory is O(n).
ivan_ah 10y ago
The "compute the eigenvalues of Matrix([[1,1],[1,0]]) raised to the power N" approach to computing the Nth Fibonacci number is only constant time if you assume exponentiation is constant time, which it is not on any computer or realistic model of computation. I still think this is a really cool technique though, even if it only works in "math land." http://bit.ly/fib_using_eigenvals http://bit.ly/fib_using_eigenvals
jpfr 10y ago
Constant time fibonacci is derived as an example for linear basis change in the superb book "Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach". It's all contained in the sample pages http://matrixeditions.com/VC5.Chap2.219-221.pdf http://matrixeditions.com/VC5.Chap2.219-221.pdf However, even though the formula is O(1), the runtime of the algorithm might be larger. Simply because a standard 64bit integer might be too small. And the BigNum implementation needs more time to multiply all the bits.
- leephillips 10y ago
  I really like the style of that book! I want to get it, but I'm hesitating at the $87 pricetag. Looks very nice, though....
leephillips 10y ago
No, but I go into it a bit in https://lee-phillips.org/lispmath/ https://lee-phillips.org/lispmath/

yaks_hairbrush 10y ago

There is no constant time implementation. Binet's formula uses exponentiation, which gives us log(n) time.

Practicality 10y ago

O(1)? Having all the answers pre-cached would be the only way to do that. Unless there is some kind of quantum computer algorithm that fits this problem well.

stephencanon 10y ago
The nth Fibonacci number has O(n) digits, so even reading a cached pre-computed result from memory is O(n).

ivan_ah 10y ago

The "compute the eigenvalues of Matrix([[1,1],[1,0]]) raised to the power N" approach to computing the Nth Fibonacci number is only constant time if you assume exponentiation is constant time, which it is not on any computer or realistic model of computation. I still think this is a really cool technique though, even if it only works in "math land." http://bit.ly/fib_using_eigenvals http://bit.ly/fib_using_eigenvals

jpfr 10y ago

Constant time fibonacci is derived as an example for linear basis change in the superb book "Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach". It's all contained in the sample pages http://matrixeditions.com/VC5.Chap2.219-221.pdf http://matrixeditions.com/VC5.Chap2.219-221.pdf However, even though the formula is O(1), the runtime of the algorithm might be larger. Simply because a standard 64bit integer might be too small. And the BigNum implementation needs more time to multiply all the bits.

leephillips 10y ago
I really like the style of that book! I want to get it, but I'm hesitating at the $87 pricetag. Looks very nice, though....

leephillips 10y ago

No, but I go into it a bit in https://lee-phillips.org/lispmath/ https://lee-phillips.org/lispmath/