News for hackers. Stuff that matters.
Re:A program to compute the nth Fibonacci number by jlarocco on Saturday April 28, 2012 @03:06PM (#3903747)
Way 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
Re:A program to compute the nth Fibonacci number by pavpanchekha on Saturday April 28, 2012 @04:14PM (#3903956)
1) You don't really need the (b) term. (1 - \phi) is on the order of .5, so if you round the result of ((a - b) / c) instead of truncating it, you can ignore that term.

2) How long are your floating point numbers? You code works for n up to 71, but no further. The linked example works for any n.

Every time Fibonacci is discussed, someone brings up the Binet formula. If I'm interviewing for a position that requires any sort of numeric coding, this is a reason not to hire -- it demonstrates you don't know the first things about floating point.

Re:A program to compute the nth Fibonacci number by xyzzyz on Saturday April 28, 2012 @05:13PM (#3904135)
Binet formula needs not to be implemented using floating point numbers:

https://github.com/xyzzyz/FibBinet

Re:A program to compute the nth Fibonacci number by raganwald on Saturday April 28, 2012 @03:20PM (#3903799)
Expanding 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!

Re:A program to compute the nth Fibonacci number by robinhouston on Saturday April 28, 2012 @04:32PM (#3904009)
My take on computing Fibonacci numbers using Binet’s formula: http://bosker.wordpress.com/2011/07/27/computing-fibonacci-n...

The short version: it's harder than people often think to do reliably (because you need arbitrary-precision floating-point operations); and, when you do, it turns out to be slower than integer methods.

Re:A program to compute the nth Fibonacci number by hamidpalo on Saturday April 28, 2012 @03:31PM (#3903832)
Optimal solution assuming that you've got perfectly accurate arbitrary precision arithmetic.

Which is as likely as a unicorn that poops Haagen-Dazs.

Re:A program to compute the nth Fibonacci number by dubya on Saturday April 28, 2012 @04:26PM (#3903994)
You 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.
Re:A program to compute the nth Fibonacci number by drostie on Saturday April 28, 2012 @05:05PM (#3904119)
Just to expand this for people who aren't familiar with this idea, which has a nice analogue with complex numbers, one can take the number a + b sqrt(5) and represent it as the matrix:

    [a, 5b]
    [b,  a]
This implements the multiplication rule for such numbers as a matrix multiplication. There is a straightforward generalization where you replace 5 with -1 and get complex numbers, which is one of the easiest ways to see that the complex numbers are scaled rotation matrices -- which is the easy way to see that a holomorphic function preserves angles and obeys the Cauchy Riemann equation ∂f/∂y = i ∂f/∂x.

It's very cute mathematics, but it's still not O(1). At the very least, exponentiating to the n requires log(n) matrix multiplications.

Re:A program to compute the nth Fibonacci number by dullcrisp on Saturday April 28, 2012 @05:32PM (#3904180)
I'm late to the party, but a quick and dirty implementation of this in ghci computes the 10,000,000th Fibonacci number for me in about 3 seconds, though it takes a lot longer to print to my terminal. It's pretty neat.

   newtype T = T (Rational,Rational) deriving Show
   :{
   instance Num T where { T (a,b) + T (c,d) = T (a+c,b+d);
                          T (a,b) * T (c,d) = T (a*c+5*b*d,b*c+a*d);
                          abs (T (a,b)) = T (a*a+5*b*b,0);
                          fromInteger n = T(fromInteger n,0);
                          signum (T (a,_)) = T (signum a,0);
                          negate (T(a,b)) = T(-a,-b) }
   instance Fractional T where { recip (T(a,b)) = T(a/(a^2-5*b^2),-b/(a^2-5*b^2));
                                 fromRational r = T(r,0)}
   :}
   let r5 = T(0,1)
   let phi = (1+r5)/2
   let psi = (1-r5)/2
   let fromT (T(a,b)) = (a,b)
   let fib n = floor . fst . fromT $ (phi^n-psi^n)/r5
   let x = fib 10000000
   x == 0
Re:A program to compute the nth Fibonacci number by raganwald on Saturday April 28, 2012 @05:42PM (#3904206)
It takes about nineteen seconds for the matrix implementation in Ruby:

    ruby-1.9.3 043 > x = Time.new.to_i; y = 10000000.matrix_fib; Time.new.to_i - x
      => 19
Re:A program to compute the nth Fibonacci number by ch on Saturday April 28, 2012 @03:15PM (#3903777)
That is pure gold.
Re:A program to compute the nth Fibonacci number by huggah on Saturday April 28, 2012 @02:59PM (#3903725)
This 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_ex...

Even the page the author links to is doing a great deal too much work!

Re:A program to compute the nth Fibonacci number by sp332 on Saturday April 28, 2012 @03:30PM (#3903826)
That'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).
Re:A program to compute the nth Fibonacci number by ranit8 on Saturday April 28, 2012 @04:29PM (#3903997)
> 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.

Re:A program to compute the nth Fibonacci number by sp332 on Sunday April 29, 2012 @07:41AM (#3905749)
If you want to find an arbitrarily high F(n), you will need an arbitrarily high precision of sqrt(5).
Re:A program to compute the nth Fibonacci number by drostie on Saturday April 28, 2012 @04:47PM (#3904058)
(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).

Re:A program to compute the nth Fibonacci number by huggah on Saturday April 28, 2012 @05:57PM (#3904245)
My 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.

Re:A program to compute the nth Fibonacci number by asselinpaul on Saturday April 28, 2012 @04:57PM (#3904088)
Another 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)