Hacker News Reader

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.ht...

View on HN

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.

You can implement matrix exponentiation recursively however.

> 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/t...

[2] Recursion to Iteration, Part 1: The Simple Method, secret features, and accumulators http://blog.moertel.com/posts/2013-05-11-recursive-to-iterat...

Reply on news.ycombinator.com