Hacker News Reader

Comment by wb14123 | Hacker News Reader

I remember there is an equation that could get the Nth fibonacci number directly. (Maybe in the exercises of Concrete Mathematics by Knuth).

View on HN

https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_e...

If ever there was a way to impress an interviewer it is to bust out this baby when asked to make a fibonacci function.

Personally, I think the matrix powers method is more impressive. You're using the matrix as a state engine to get to whatever state you intend to reach. That has more applications than just the closed form, which a lot of people know about, and you most likely just happened to memorize.

Don't get me wrong, it'd still be impressive "Woah, he memorized this!" but seeing someone do the matrix trick would be even more impressive, to me.

The closed form is just the diagonalized version of the matrix power, though.

I honestly didn't know that until it was mentioned in another part of this thread. My point was that someone can memorize the formula. Chances are, they'll see the matrix form and actually know how to use that in other situations.

Now, if you derived the formula on the board from the matrix, that'd be incredibly impressive. The idea here is how the person's brain thinks. When I see them write an equation on the board, I think "Oh, they memorized it" when I see them step through the process of creating a matrix and doing matrix multiplication, I think "Wow, they /really/ know their stuff". If they just threw up the matrix and couldn't explain it, I wouldn't be as impressed. Same as if they wrote the equation and couldn't explain it.

At the end of the day, if they could explain either approach, I'd be impressed, I think the matrix form just lends itself to more likely be in a way that the person can explain it

fair enough.

It would be impressive if you could derive or prove it, not if you'd just memorized it.

not even a little bit impressed?

The closed form solution is not that difficult to derive at all if you put the problem as a reoccurrence equation with boundary conditions.

or just calculate the eigenvalues & eigenvectors of Q.

It's also in SICP, but depend on what you consider the basic step is, it's also O(logN). As someone else mentions, it requires arbitrary precision calculation, and exponential calculation is O(logN).

If you diagonalize the matrix in the problem, the formula pops out pretty quickly.

Nice catch, is that from Knuth's book?

Diagonalization is a fairly standard mathematical trick for doing matrix powers easily. If X is some matrix that can be diagonalised as

  X = P^(-1) D P

then

  X^n = (P^(-1) D P)^n = P^(-1) D^n P

It requires arbitrary precision arithmetic. It is known as Binet's formula.

Reply on news.ycombinator.com