Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A linear algebra trick for computing Fibonacci numbers fast

codeconfessions.substack.com

Post reply on HN
Print view View original

51–60 of 76 posts

Re: A linear algebra trick for computing Fibonacci numbers fast

#51

Post by margalabargala »

jonahx wrote: post #50
tromp wrote: post #7

> Another interesting thing to note here is the performance of fib_fast and fib_closed_form algorithms. Both of these algorithms essentially compute the nth power of an expression and therefore their complexities in terms of n are same. However, the golden ratio based algorithm is computing the nth power of a scalar value which can be done much faster than computing the nth power of a 2X2 matrix, thus the difference…

To clarify, you mean treat sqrt(5) as a symbolic constant, and then expand out repeated multiplications of "a + sqrt(5)*b" to arrive at an expression with addition and multplications involving powers of a, b, and sqrt(5)?

This is correct. All fibonacci numbers are integers, thus all instances of sqrt(5) must eventually cancel out.

Re: A linear algebra trick for computing Fibonacci numbers fast

#52

Post by [deleted] »

tromp wrote: post #7

> Another interesting thing to note here is the performance of fib_fast and fib_closed_form algorithms. Both of these algorithms essentially compute the nth power of an expression and therefore their complexities in terms of n are same. However, the golden ratio based algorithm is computing the nth power of a scalar value which can be done much faster than computing the nth power of a 2X2 matrix, thus the difference…

[deleted]

Re: A linear algebra trick for computing Fibonacci numbers fast

#53

Post by brian_cloutier »

dietrichepp wrote: post #4

I think the proof for the closed-form version is accessible to people with a background in linear algebra. The matrix is diagonalizable (not all matrixes are diagonalizable, but this one is): M = P Δ P^-1 Here, P is some invertible matrix and Δ is a diagonal matrix. The powers of M reveal how useful this is: M^N = (P Δ P^-1) * … * (P Δ P^-1) If you adjust the parentheses, you’ll see N-1 terms of (P^-1 P), which can b…

If anyone wants to read this in book form, Linear Algebra Done Right includes it as an exercise at the end of a very short and readable chapter 5.C on eigenspaces and diagonal matricies.

The treatment in thirty-three miniatures describes the steps you take but doesn't mention what you are actually doing (finding eigenvalues) or leave you with any intuition for why this was a natural thing to have tried

Re: A linear algebra trick for computing Fibonacci numbers fast

#54

Post by asdftemp »

I really like this analysis, which also discusses the “fast doubling” method: https://extratricky.com/blog/fibonacci-complexity

it points out that the bit complexity of the traditional algorithm is actually quadratic. and apparently, restricted to fixed width integers, there is a constant time method.

Re: A linear algebra trick for computing Fibonacci numbers fast

#55

Post by gjm11 »

asdftemp wrote: post #54

I really like this analysis, which also discusses the “fast doubling” method: https://extratricky.com/blog/fibonacci-complexity it points out that the bit complexity of the traditional algorithm is actually quadratic. and apparently, restricted to fixed width integers, there is a constant time method.

There's less to the "constant time method" thing than meets the eye.

If you work modulo M for some fixed M, then the Fibonacci sequence is periodic with period at most M^2 (because if two consecutive numbers are known, so is the whole rest of the sequence), which is a constant. Therefore, for any particular M, you can just write down the at-most-M^2 repeating sequence and what the actual period is (call that p), and then for any n the algorithm goes: reduce n mod p, and then look up the result in your big lookup table.

(Actually, this isn't constant-time, because if n is large then reducing it mod p isn't constant-time. For that matter, no algorithm can possibly be constant-time, because unless you pick a modulus for which the period is a power of 2 you always need to look at all the bits of n.)

Re: A linear algebra trick for computing Fibonacci numbers fast

#56

Post by vitus »

The only logarithmic algorithm here is fib_closed_form because floating-point multiplication is a fixed-cost operation (and yields a progressively imprecise result, as other commenters have pointed out).

The other approaches use arbitrary precision integers, as you've noted, so additions and multiplications are not actually fixed-cost, but scale with the number of digits you're operating on (addition scales linearly; multiplication in Python uses Karatsuba for sufficiently large N, so it scales like n^1.58).

In fact, you can't get a sublinear result with a lossless approach, since the number of digits in Fib(n) scales linearly with n, and so you need O(n) operations to just write out the digits.

This is pretty straightforward to explain with the closed-form solution: Fib(n) is roughly 1.618^n / 2.236; by taking the binary logarithm, you can see this requires about 0.7n bits to represent. (Equivalently, 0.2n decimal digits.)

Re: A linear algebra trick for computing Fibonacci numbers fast

#57

Post by reginaldo »

abhi9u wrote: post #23
reginaldo wrote: post #12

For the initiated, this is SICP[1] Exercise 1.19. That exercise walks you through a proof without explicitly using linear algebra. I remember having a blast solving this back in the day. [1] https://web.mit.edu/6.001/6.037/sicp.pdf => page 61

I just read the exercise. That's very clever. Makes me want to sit and go through the book.

I skimmed your substack, and it seems to me that you would like SICP. Give it a try.

Re: A linear algebra trick for computing Fibonacci numbers fast

#58

Post by jfarmer »

abhi9u wrote: post #20
kragen wrote: post #18

Earlier quoted context omitted.

what if you use the closed-form answer, but without any floating-point or other approximations i mean it all comes out to an integer in the end, all the radicals cancel i see tromp already suggested a form of this

But that seems to be computationally same amount of work as the matrix form, so we get similar performance?

I did this years ago to demonstrate to my students that the "exact solution" can still be written in code. There are implementations in Ruby and Python, with some benchmarking code: https://github.com/jfarmer/fib-bench/

Code winds up looking like:

  def fib_phi(n)
    ((PhiRational(0,1)**n - PhiRational(1,-1)**n)/PhiRational(-1, 2)).a.to_i
  end
The exponentiation operation uses basic exponentiation by squaring for performance: https://en.wikipedia.org/wiki/Exponentiation_by_squaring

(Technically implemented arithmetic over Q(ϕ) not Q(√5) because it simplifies the code a bit.)

Re: A linear algebra trick for computing Fibonacci numbers fast

#59

Post by mahalex »

nimish wrote: post #19

It's easier to treat these as linear difference equations with constant coefficients and use the ansatz of λ^{n}. This is morally the same thing but without the need for matrix manipulation. Knuth, Oren and Patashnik's Concrete Mathematics is full of these and is required reading for discrete math.

Note that “Oren and Patashnik” is one person named Oren Patashnik.

Re: A linear algebra trick for computing Fibonacci numbers fast

#60

Post by kccqzy »

eutectic wrote: post #46
abhi9u wrote: post #10

Earlier quoted context omitted.

(Author of the article here) Thanks for writing this up, it's much much more intuitive than what I've read everywhere else. I primarily looked up Knuth (TAOCP Vol 1) for this part, and he showed a longish proof using generating functions which looked too long to show in the article, and I would not have done a better job than him. The thirty three miniatures book showed a more abstract proof, which would have been ac…

The generating function proof is also really beautiful! I think I maybe like it even more than the linear algebra proof.

The generating function approach is the standard way of solving recurrences. In that sense, it isn't beautiful, just routine. But yes the first time I'd seen it I felt my body shudder at that sorcery.
Post reply on HN