The Nth Fibonacci Number in O(log N) • Hacker News Board

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

#21

Post by fdej » Wed, Dec 17, 2014, 8:11 AM UTC

mytochar wrote: post #7

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.

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.

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

#22

Post by sillysaurus3 » Wed, Dec 17, 2014, 8:12 AM UTC

obfuskater wrote: post #20

sillysaurus3 wrote: post #16

Earlier quoted context omitted.

I wasn't trying to one-up anyone. I thought it was interesting, so I figured others might find it interesting too. In particular, it was surprising to find that there's a closed-form solution for the Fibonacci sequence. Sorry.

Don't be sorry! I found your comment very interesting and was also surprised to find that there exists a closed-form solution.

The whole book is pretty fascinating, "Mathematics for Computer Science" by Lehman and Leighton: http://www.cs.princeton.edu/courses/archive/spring10/cos433/...

The formula came from section 17.3.2, which goes into detail about how to derive it.

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

#23

Post by cperciva » Wed, Dec 17, 2014, 8:15 AM UTC

fdej wrote: post #18

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…

Minor pedantry: the best proved bound for M(N) is O(N log N 8^(log* N)). You can easily pretend that log* N is constant, though...

Oops, forgot the O() inside the exponential. Fixed, thanks.

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

#24

Post by Fede_V » Wed, Dec 17, 2014, 8:16 AM UTC

hacknat wrote: post #6

wb14123 wrote: post #2

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

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.

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

#25

Post by obfuskater » Wed, Dec 17, 2014, 8:24 AM UTC

sillysaurus3 wrote: post #22

obfuskater wrote: post #20

Earlier quoted context omitted.

Don't be sorry! I found your comment very interesting and was also surprised to find that there exists a closed-form solution.

The whole book is pretty fascinating, "Mathematics for Computer Science" by Lehman and Leighton: http://www.cs.princeton.edu/courses/archive/spring10/cos433/... The formula came from section 17.3.2, which goes into detail about how to derive it.

Thanks. I like the way they introduce what a proof is in chapter 1, I feel like they have a good, subtle sense of humor. I don't have a mathematical background so it might be a tough read for me, but it seems like a great resource.

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

#26

Post by Spiritus » Wed, Dec 17, 2014, 9:05 AM UTC

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…

Out of curiosity, what line of work are you in given that you can seemingly pull this stuff from memory? All I read was "lorem ipsum..." until you got to Big O.

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

#27

Post by dbaupp » Wed, Dec 17, 2014, 9:11 AM UTC

hacknat wrote: post #10

msds wrote: post #5

Earlier quoted context omitted.

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

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

#28

Post by antics » Wed, Dec 17, 2014, 9:18 AM UTC

Spiritus wrote: post #26

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…

Out of curiosity, what line of work are you in given that you can seemingly pull this stuff from memory? All I read was "lorem ipsum..." until you got to Big O.

This is actually just standard theory. They teach this in every undergrad algorithms class. A lot of it is just getting good intuition for these sorts of problems.

For example, the nth Fibonacci number has n log_2 \phi bits, which means that to simply list the digits in the nth number, it takes O(n) time.

So from there it's pretty easy to see that actually this algorithm can't "really" operate in O(log n), or at least, something must be up that causes us to produce that analysis.

Another bit of intuition that might help you see where this bound comes from: what's actually true is that it takes O(log n) _matrix multiplications_ to get the result. So if you see that and you see that listing the digits of the nth number of the sequence is O(n), it starts to point at the fact that there's a hidden cost to the multiplications.

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

#29

Post by phireal » Wed, Dec 17, 2014, 9:21 AM UTC

Spiritus wrote: post #26

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…

Out of curiosity, what line of work are you in given that you can seemingly pull this stuff from memory? All I read was "lorem ipsum..." until you got to Big O.

It's Colin Percival: author of tarsnap, former BSD security officer and considered something of an authority on crytography. I presume his maths skills are therefore suitably well polished to be able to pull this stuff from memory.

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

#30

Post by antics » Wed, Dec 17, 2014, 9:26 AM UTC

phireal wrote: post #29

Spiritus wrote: post #26

Earlier quoted context omitted.

Out of curiosity, what line of work are you in given that you can seemingly pull this stuff from memory? All I read was "lorem ipsum..." until you got to Big O.

It's Colin Percival: author of tarsnap, former BSD security officer and considered something of an authority on crytography. I presume his maths skills are therefore suitably well polished to be able to pull this stuff from memory.

I want to dispel the rumor that this is magic. This is standard material in undergrad algorithms classes. See, for example, Jeff Erickson's algorithms notes here[1]. It's literally the first page of the chapter on dynamic programming.

[1] http://web.engr.illinois.edu/~jeffe/teaching/algorithms/note...