4 ms·
A program to compute the nth Fibonacci number
- deleted 15y ago[deleted]
- huggah 15y agoThis is neat, and a solution that I hadn't seen before. But the author doesn't seem to be aware that finding the nth Fibonacci number is an O(1) problem: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex... Even the page the author links to is doing a great deal too much work!
- deleted 15y ago[deleted]
- sp332 15y agoThat's probably faster, but it's not O(1). Calculating sqrt(5) to the needed precision, and raising phi to the n power, are not O(1).
- deleted 15y ago[deleted]
- ranit8 15y ago> Calculating sqrt(5) to the needed precision... I think this one could be optimized by precomputing and storing (1 + sqrt(5)) at the highest precision available.
- sp332 15y agoIf you want to find an arbitrarily high F(n), you will need an arbitrarily high precision of sqrt(5).
- drostie 15y ago(1) The whole point of that "O(1) algorithm" is that the n'th Fibonacci number has asymptotic size: F[n] ~= phi ** n / sqrt(5) But this means that it requires O(n) memory to store, which means that it is impossible to get an algorithm which scales better than O(n), asymptotically. You might be able to get better than O(n²); I don't know much about arbtitrary-precision exponentiation algorithms. (2) This is one of those nasty cases where CS folks are loose with the meaning of big-O, anyway. Strictly speaking the input size for the Turing machine scales like O(log n), and so the Fibonacci algorithms should probably be said to have exponential complexity, even though it's a linear recurrence relation. It depends how loose you are with what the 'n' means in O(n).
- huggah 15y agoMy apologies. You make a good point, and this is one of those cases where CS folks are loose with the meaning of big-O. I still might be confused, but AFAICT, the OP's solution and computation by rounding both require O( (log n) * M(log n) ) time, where M(n) is the time it takes to multiply an n-bit number.
- jlarocco 15y agoWay too much work. def fib_binet(n) a = (1+Math.sqrt(5))**n b = (1-Math.sqrt(5))**n c = (2**n)*Math.sqrt(5) return ((a-b)/c).truncate() end def fib2(n) a = Math.sqrt(5) return ((1/a)*(((1+a)/2)**n)).round() end (0..20).each do | i | puts fib_binet(i) puts fib2(i) end
- ch 15y agoThat is pure gold.
- raganwald 15y agoExpanding on my original answer to Huggah, either this answer or a naïve recursive answer are fine if the purpose of the question is a “fizz buzz” to demonstrate that someone really can write a trivial piece of code. If the objective is to generate an interesting conversation, I would go with this, with matrices, with memoization, or anything else that provides an opportunity to share experience. The only time this one wouldn’t be right is when the interviewer is specifically trying to get you to demonstrate the ability to handle recursion. I don’t have an opinion about that, but there are some people who believe that pointers and recursion are some kind of innate talents that should be verified in the interview process. Of course, if that’s what they want, they should probably pick a problem that only admits a recursive solution, but when you’re on the other side of the table it requires great tact to debug their interview process. p.s. Either way, thanks!
- hamidpalo 15y agoOptimal solution assuming that you've got perfectly accurate arbitrary precision arithmetic. Which is as likely as a unicorn that poops Haagen-Dazs.
- dubya 15y agoYou could work in the Euclidean domain of integers with sqrt(5) adjoined and avoid floating point completely. The matrix version is actually pretty efficient, and leads to the above if you diagonalize.
- asselinpaul 15y agoAnother good way: def fib(number): if number == 0: return 0 elif number == 1: return 1 else: return fib(number-1) + fib(number-2) print fib(10)