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.
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!
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.
Which is as likely as a unicorn that poops Haagen-Dazs.
[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.
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