3 ms·

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

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

ch 15y ago
That is pure gold.
raganwald 15y ago
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!
hamidpalo 15y ago
Optimal solution assuming that you've got perfectly accurate arbitrary precision arithmetic. Which is as likely as a unicorn that poops Haagen-Dazs.
- dubya 15y ago
  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.
  - drostie 15y ago
    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.
  - dullcrisp 15y ago
    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
    - raganwald 15y ago
      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
pavpanchekha 15y ago
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.
- xyzzyz 15y ago
  Binet formula needs not to be implemented using floating point numbers: https://github.com/xyzzyz/FibBinet https://github.com/xyzzyz/FibBinet
robinhouston 15y ago
My take on computing Fibonacci numbers using Binet’s formula: http://bosker.wordpress.com/2011/07/27/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.

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

ch 15y ago

That is pure gold.

raganwald 15y ago

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!

hamidpalo 15y ago

Optimal solution assuming that you've got perfectly accurate arbitrary precision arithmetic. Which is as likely as a unicorn that poops Haagen-Dazs.

dubya 15y ago
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.
- drostie 15y ago
  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.
- dullcrisp 15y ago
  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
  - raganwald 15y ago
    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

pavpanchekha 15y ago

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.

xyzzyz 15y ago
Binet formula needs not to be implemented using floating point numbers: https://github.com/xyzzyz/FibBinet https://github.com/xyzzyz/FibBinet

robinhouston 15y ago

My take on computing Fibonacci numbers using Binet’s formula: http://bosker.wordpress.com/2011/07/27/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.