4 ms·

Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int. Also, you could have shown a method which is O(

by enedil 9y ago

Unfortunate, that your results for `n = 90` are completely useless, since F_90 > 2^32 which is the size of int. Also, you could have shown a method which is O(log n), namely [[F(n+1) F(n)], [F(n) F(n-1)]] equals [[1, 1] [1, 0]] raised to the power of n.

desio 9y ago
Actually F_90 < 2^64. Golang ints are minimum 32bits and can be 64bits so my results were not completely useless at all ;) Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion. Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...
- enedil 9y ago
  I suspect that computing Fibonacci numbers with Binet formula is slower than with matrix form - if mul(n) is the number of multiplications required to compute x^n, then matrix form will use 8 * mul(n) integer multiplications, while Binet's formula requires 2 * mul(n) floating point operations. I suspect the latter is slower.
- Retr0spectrum 9y ago
  You can implement matrix exponentiation recursively however.
  - tmoertel 9y ago
    > You can implement matrix exponentiation recursively however. And tail recursively, and – going full circle – you can convert that tail recursion into iteration (see [1] for example, using techniques described in [2]). [1] Iterative fast-power implementation in Python https://github.com/tmoertel/practice/blob/master/libraries/tomlib.py#L143 https://github.com/tmoertel/practice/blob/master/libraries/t... [2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...

by enedil 9y ago

desio 9y ago

Actually F_90 < 2^64. Golang ints are minimum 32bits and can be 64bits so my results were not completely useless at all ;) Indeed you can compute Fibonacci numbers (and other linear recurrences) with matrix exponentiation, or with a closed-form equation like the Binet Formula - but I limited the scope of this article to tail recursion. Binet Formula: http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.html http://mathworld.wolfram.com/BinetsFibonacciNumberFormula.ht...

enedil 9y ago
I suspect that computing Fibonacci numbers with Binet formula is slower than with matrix form - if mul(n) is the number of multiplications required to compute x^n, then matrix form will use 8 * mul(n) integer multiplications, while Binet's formula requires 2 * mul(n) floating point operations. I suspect the latter is slower.
Retr0spectrum 9y ago
You can implement matrix exponentiation recursively however.
- tmoertel 9y ago
  > You can implement matrix exponentiation recursively however. And tail recursively, and – going full circle – you can convert that tail recursion into iteration (see [1] for example, using techniques described in [2]). [1] Iterative fast-power implementation in Python https://github.com/tmoertel/practice/blob/master/libraries/tomlib.py#L143 https://github.com/tmoertel/practice/blob/master/libraries/t... [2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...