4 ms·
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 num
by 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 agoI 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 agoYou 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...