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

31–40 of 46 posts

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

#31

Post by cperciva »

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.

More relevant than the above, my doctoral thesis was all about algorithms, and as an undergraduate student I published research in large integer arithmetic.

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

#32

Post by nealwu »

As mentioned, the actual number has O(N) bits and thus can't actually be computed in O(log N) time. So if you just want an approximation, you may as well use Binet's formula. [1]

However, one thing this algorithm can do that Binet's formula can't is compute the N-th Fibonacci number modulo some constant M in O(log N) time. So you could very efficiently compute, say, the last 12 digits of F_123456789. A lot of programming contests (TopCoder, Google Code Jam, etc.) will ask for the answer modulo some constant to take advantage of this trick.

[1] http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...

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

#33

Post by phireal »

antics wrote: post #30
phireal wrote: post #29

Earlier quoted context omitted.

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...

I appreciate that it's not magic and agree that it should be demystified.

Having said that, doing it once in the past in an undergrad class and remembering it 10 years later when a relevant article on some website is posted are two different things.

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

#34

Post by raverbashing »

antics wrote: post #30
phireal wrote: post #29

Earlier quoted context omitted.

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...

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

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

#35

Post by tomp »

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.

He's in cryptography, he also started university at age 13.

https://news.ycombinator.com/item?id=35076

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

#36

Post by nabb »

isani wrote: post #15

Factoring into powers of 2 seems to me like an unnecessary complication. It's possible to calculate an arbitrary power in O(log N) time without memoization. def __get_matrix_power(self, M, p): if p == 1: return M if p % 2 == 1: # odd power return self.__multiply_matrices(M, self.__get_matrix_power(M, p - 1)) else: # even power K = self.__get_matrix_power(M, int(p/2)) return self.__multiply_matrices(K, K)

Also working on pairs of consecutive fibonacci numbers (f_n, f_(n+1)) instead of the matrix [[f_(n+1) f_n] [f_n f_(n-1)]] makes this much simpler.

  def fib(n):
    def fib2(n):
      # returns (f_n, f_(n+1))
      if n == 0:
        return 0, 1
      if n % 2:
        a, b = fib2(n-1)
        return b, a+b
      a, b = fib2(n//2)
      return b*a + a*(b-a), a*a + b*b
    return fib2(n)[0]

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

#37

Post by switz »

raverbashing wrote: post #34
antics wrote: post #30

Earlier quoted context omitted.

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...

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?

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

#38

Post by nhaehnle »

nealwu wrote: post #32

As mentioned, the actual number has O(N) bits and thus can't actually be computed in O(log N) time. So if you just want an approximation, you may as well use Binet's formula. [1] However , one thing this algorithm can do that Binet's formula can't is compute the N-th Fibonacci number modulo some constant M in O(log N) time. So you could very efficiently compute, say, the last 12 digits of F_123456789. A lot of progra…

A really neat observation here is that Binet's formula and the matrix exponentiation trick are arguably the same thing.

How so? You can think of the operations of Binet's formula as happening in the field Q(sqrt{5}). Since sqrt{5} is a square root, every element of this field has a unique representation of the form a + b sqrt{5} with a and b rational, and so the field can be said to have dimension 2 over the rationals. When you squint at how the field operations work in this representation, you'll find that you end up doing something that looks very similar to the 2x2 matrix multiplications trick; with a bit of rearrangement, it's the same thing - except that the matrix multiplication trick is usually derived via dynamic programming, and Binet's formula is usually derived via power series.

The fact that things often fit together so nicely is perhaps the most beautiful aspect of mathematics.

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

#39

Post by tomp »

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…

Another similar "algorithm": sleep sort.

Basically, take a list of integers, and for each element n create a thread that sleeps n seconds, after which it appends n to the result list.

Assuming the original list is dense (there are no gaps between integers), we can sort it in O(n)!

:)

Post reply on HN