6 ms·

My favourite trick in Julia using matrices is the following one liner: fib(n) = ((BigInt [1 1; 1 0])^n)[2,1] Which defines a fast, exact, Fibonacci function.

My favourite trick in Julia using matrices is the following one liner: fib(n) = ((BigInt [1 1; 1 0])^n)[2,1] Which defines a fast, exact, Fibonacci function. It's so far the easiest and only way I've managed to calculate the 10^9th Fibonacci number.

Double_Cast 11y ago
I was playing with the equation on a sheet of paper. From what I can tell, the [2, 1] figure at the end is unnecessary. The Fibonacci sequence is encoded directly in the [1 1; 1 0]^n figure. The only thing the [2, 1] figure does is fast-forward to the 2nd iteration. Fibonacci sequence = 0, 1, 1, 2, 3, 5, 8... if M = [1 1; 1 0], then M^1 = [1 1; 1 0] M^2 = [2 1; 1 1] M^3 = [3 2; 2 1] M^4 = [5 3; 3 2] M^5 = [8 5; 5 3]
- contravariant 11y ago
  The [2,1] is just there to pick the correct entry. You can pick another one but you'll have to change the power of the matrix.
ntenenz 11y ago
The following defines the Fibonacci recurrence relation (in matrix form): [F(n+1); F(n)] = [1 1; 1 0]^n * [F(n); F(n-1)] or [F(n+1); F(n)] = [1 1; 1 0]^n * [1; 0] if we define F(0) = 0 and F(1) = 1. However, we can diagonalize [1 1; 1 0] using its eigenvalues and eigenvectors (see here: http://www.wolframalpha.com/input/?i=eigenvectors+of+%7B%7B1%2C+1%7D%2C+%7B1%2C+0%7D%7D http://www.wolframalpha.com/input/?i=eigenvectors+of+%7B%7B1...). For any diagonalizable matrix A = PDP^-1 where P is the matrix of eigenvectors and D is the matrix of eigenvalues on the diagonal, A^n = PD^nP^-1. Try to expand the A^n if you don't believe it. Using this trick, you have simplified the power of a matrix to a power of two floats, namely the eigenvalues.
- gaze 11y ago
  From this you'll end up with the closed form in terms of the golden ratio. Might as well use that.
  - ntenenz 11y ago
    Yup, you will. It's nice to show where that comes from though. :)
- conistonwater 11y ago
  Floats have rather limited precision for this type of computation for large n (gp's post had n=1e9). If you were to go with big-floats instead, then the resulting arithmetic will be more expensive that the straightforward big-integer arithmetic.

Double_Cast 11y ago

I was playing with the equation on a sheet of paper. From what I can tell, the [2, 1] figure at the end is unnecessary. The Fibonacci sequence is encoded directly in the [1 1; 1 0]^n figure. The only thing the [2, 1] figure does is fast-forward to the 2nd iteration. Fibonacci sequence = 0, 1, 1, 2, 3, 5, 8... if M = [1 1; 1 0], then M^1 = [1 1; 1 0] M^2 = [2 1; 1 1] M^3 = [3 2; 2 1] M^4 = [5 3; 3 2] M^5 = [8 5; 5 3]

contravariant 11y ago
The [2,1] is just there to pick the correct entry. You can pick another one but you'll have to change the power of the matrix.

ntenenz 11y ago

The following defines the Fibonacci recurrence relation (in matrix form): [F(n+1); F(n)] = [1 1; 1 0]^n * [F(n); F(n-1)] or [F(n+1); F(n)] = [1 1; 1 0]^n * [1; 0] if we define F(0) = 0 and F(1) = 1. However, we can diagonalize [1 1; 1 0] using its eigenvalues and eigenvectors (see here: http://www.wolframalpha.com/input/?i=eigenvectors+of+%7B%7B1%2C+1%7D%2C+%7B1%2C+0%7D%7D http://www.wolframalpha.com/input/?i=eigenvectors+of+%7B%7B1...). For any diagonalizable matrix A = PDP^-1 where P is the matrix of eigenvectors and D is the matrix of eigenvalues on the diagonal, A^n = PD^nP^-1. Try to expand the A^n if you don't believe it. Using this trick, you have simplified the power of a matrix to a power of two floats, namely the eigenvalues.

gaze 11y ago
From this you'll end up with the closed form in terms of the golden ratio. Might as well use that.
- ntenenz 11y ago
  Yup, you will. It's nice to show where that comes from though. :)
conistonwater 11y ago
Floats have rather limited precision for this type of computation for large n (gp's post had n=1e9). If you were to go with big-floats instead, then the resulting arithmetic will be more expensive that the straightforward big-integer arithmetic.