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

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

#11

Post by cperciva » Wed, Dec 17, 2014, 7:47 AM UTC

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 can solve PSPACE in a polynomial number of integer operations, but I can't see how to prove it immediately.

In "real" terms, computing the Nth fibonacci number takes O(M(N)) = O(N log N 2^(O(log* N))) operations.

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

#12

Post by dastbe » Wed, Dec 17, 2014, 7:47 AM UTC

An issue here is that the the nth Fibonacci number has O(N) bits, so once you move into arbitrary arithmetic calculations your +'s and *'s will become O(N) and O(N logN) respectively.

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

#13

Post by webo » Wed, Dec 17, 2014, 7:53 AM UTC

sillysaurus3 wrote: post #8

In Python: def fib(n): import math r5 = math.sqrt(5) x = pow((1 + r5) / 2, n) x -= pow((1 - r5) / 2, n) return x / r5 $ python fib.py 4 3.0 $ python fib.py 5 5.0 $ python fib.py 50 12586269025.0 $ python fib.py 5000 OverflowError: (34, 'Result too large') So we add arbitrary precision. Uglier, but supports any n: def fib(n): from math import sqrt from decimal import Decimal r5 = Decimal(sqrt(5)) x = pow((1 + r5) / 2,…

This shows nothing but one's ability to code-up a math formula. The blog post goes into much detail about how to solve the problem using matrices and memoization.

Edit: Looks like sillysaurus3 edited his comment.

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

#14

Post by obfuskater » Wed, Dec 17, 2014, 7:57 AM UTC

sillysaurus3 wrote: post #8

In Python: def fib(n): import math r5 = math.sqrt(5) x = pow((1 + r5) / 2, n) x -= pow((1 - r5) / 2, n) return x / r5 $ python fib.py 4 3.0 $ python fib.py 5 5.0 $ python fib.py 50 12586269025.0 $ python fib.py 5000 OverflowError: (34, 'Result too large') So we add arbitrary precision. Uglier, but supports any n: def fib(n): from math import sqrt from decimal import Decimal r5 = Decimal(sqrt(5)) x = pow((1 + r5) / 2,…

returning int(round(x)) could act as a bandaid for the slight error in the results.

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

#15

Post by isani » Wed, Dec 17, 2014, 7:59 AM UTC

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)

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

#16

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

webo wrote: post #13

sillysaurus3 wrote: post #8

In Python: def fib(n): import math r5 = math.sqrt(5) x = pow((1 + r5) / 2, n) x -= pow((1 - r5) / 2, n) return x / r5 $ python fib.py 4 3.0 $ python fib.py 5 5.0 $ python fib.py 50 12586269025.0 $ python fib.py 5000 OverflowError: (34, 'Result too large') So we add arbitrary precision. Uglier, but supports any n: def fib(n): from math import sqrt from decimal import Decimal r5 = Decimal(sqrt(5)) x = pow((1 + r5) / 2,…

This shows nothing but one's ability to code-up a math formula. The blog post goes into much detail about how to solve the problem using matrices and memoization. Edit: Looks like sillysaurus3 edited his comment.

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.

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

#17

Post by dagw » Wed, Dec 17, 2014, 8:03 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.

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

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

#18

Post by fdej » Wed, Dec 17, 2014, 8:04 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…

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

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

#19

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

webo wrote: post #13

sillysaurus3 wrote: post #8

In Python: def fib(n): import math r5 = math.sqrt(5) x = pow((1 + r5) / 2, n) x -= pow((1 - r5) / 2, n) return x / r5 $ python fib.py 4 3.0 $ python fib.py 5 5.0 $ python fib.py 50 12586269025.0 $ python fib.py 5000 OverflowError: (34, 'Result too large') So we add arbitrary precision. Uglier, but supports any n: def fib(n): from math import sqrt from decimal import Decimal r5 = Decimal(sqrt(5)) x = pow((1 + r5) / 2,…

This shows nothing but one's ability to code-up a math formula. The blog post goes into much detail about how to solve the problem using matrices and memoization. Edit: Looks like sillysaurus3 edited his comment.

Was the purpose of this post to help people prepare for interviews? Does code always have to show off one's ability? This code inspired me to learn about Binet's formula and for that reason I think it was valuable.

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

#20

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

sillysaurus3 wrote: post #16

webo wrote: post #13

Earlier quoted context omitted.

This shows nothing but one's ability to code-up a math formula. The blog post goes into much detail about how to solve the problem using matrices and memoization. Edit: Looks like sillysaurus3 edited his comment.

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.