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

The Nth Fibonacci Number in O(log N)

kukuruku.co

Post reply on HN
Print view View original

41–46 of 46 posts

Re: The Nth Fibonacci Number in O(log N)

#41

Post by robinhouston »

cperciva wrote: post #11

It's easy to compute things quickly if you pretend that you can do arbitary-precision arithmetic in constant time. Want a quadrillion digits of Pi? Easy, just use the Brent–Salamin AGM algorithm and you'll get them in about 500 arithmetic operations. NP-complete problems? No problem at all, rephrase them as subset-sum problems and use the polynomial-integer-operations dynamic programming algorithm. I don't think you…

Even if the computation could be done by magic, simply writing the result to memory would take O(n) operations, since the nth Fibonacci number has O(n) bits.

Re: The Nth Fibonacci Number in O(log N)

#42

Post by lotyrin »

switz wrote: post #37
raverbashing wrote: post #34

Earlier quoted context omitted.

Yeah, but "kids these days" only want to know Java or Angular.js and bawl at the first sight of math.

Psh, who wants to learn Java?

I think "know" over "learn" used by the grandparent is important there; probably they were made to learn it for coursework, they want to be allowed to continue only having to know that much and not learn further.

Re: The Nth Fibonacci Number in O(log N)

#43

Post by lscharen »

This brings back some memories. I remember talking about the different ways of calculating the Fibonacci numbers in an old comp.lang.java usenet thread about recursion, memoization and dynamic programming from 2007,

http://coding.derkeiler.com/Archive/Java/comp.lang.java.prog...

The thread discusses the exponential, linear and logarithmic algorithms.

Re: The Nth Fibonacci Number in O(log N)

#44

Post by mmaldacker »

Fede_V wrote: post #24
hacknat wrote: post #6

Earlier quoted context omitted.

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.

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.

Re: The Nth Fibonacci Number in O(log N)

#45

Post by hacknat »

dagw wrote: post #17
hacknat wrote: post #6

Earlier quoted context omitted.

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.

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

not even a little bit impressed?

Re: The Nth Fibonacci Number in O(log N)

#46

Post by mytochar »

fdej wrote: post #21
mytochar wrote: post #7

Earlier quoted context omitted.

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 im…

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

Post reply on HN