The Nth Fibonacci Number in O(log N)
kukuruku.co
The Nth Fibonacci Number in O(log N)
1–10 of 46 posts
Re: The Nth Fibonacci Number in O(log N)
#2I remember there is an equation that could get the Nth fibonacci number directly. (Maybe in the exercises of Concrete Mathematics by Knuth).
Re: The Nth Fibonacci Number in O(log N)
#3I remember there is an equation that could get the Nth fibonacci number directly. (Maybe in the exercises of Concrete Mathematics by Knuth).
It requires arbitrary precision arithmetic. It is known as Binet's formula.
Re: The Nth Fibonacci Number in O(log N)
#4I remember there is an equation that could get the Nth fibonacci number directly. (Maybe in the exercises of Concrete Mathematics by Knuth).
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).
Re: The Nth Fibonacci Number in O(log N)
#5I remember there is an equation that could get the Nth fibonacci number directly. (Maybe in the exercises of Concrete Mathematics by Knuth).
If you diagonalize the matrix in the problem, the formula pops out pretty quickly.
Re: The Nth Fibonacci Number in O(log N)
#6I 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.
Re: The Nth Fibonacci Number in O(log N)
#7I 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.
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.
Re: The Nth Fibonacci Number in O(log N)
#8In 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')
def fib(n):
from math import sqrt
from decimal import Decimal
r5 = Decimal(sqrt(5))
x = pow((1 + r5) / 2, n)
x -= pow((1 - r5) / 2, n)
return x / r5
$ python fib.py 4
3.000000000000000242931577139
$ python fib.py 5
5.000000000000000607328942851
$ python fib.py 50000
1.077773489309106593392984005E+10449
$ python fib.py 50309230
8.147201098193506535089177522E+10514006
$ python fib.py 50309230390
decimal.Overflow: above Emax
Wolfram alpha verifies this is correct for Fib 50,000: http://www.wolframalpha.com/input/?i=Fib+50000
Re: The Nth Fibonacci Number in O(log N)
#9Earlier 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…
fair enough.