4 ms·
It misses the math Haskell programmer using the closed form expression: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia
by wslh 13y ago
It misses the math Haskell programmer using the closed form expression: http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...
What is the best way to implement it in Haskell since Phi and Psi are real numbers?
Edit: as the user tome told me.... It was about the factorial function not about fibonacci. I blindly see fibonacci.
- freyrs3 13y agoNaive implementation might be: fib :: Integer -> Integer fib x = truncate $ ( 1 / sqrt 5 ) * ( phi ^ x - psi ^ x ) where phi = ( 1 + sqrt 5 ) / 2 psi = ( 1 - sqrt 5 ) / 2
- fhars 13y agoAlas, that version is only correct up to x = 25, because *Main> 1 / sqrt 5 * (((1 + sqrt 5) / 2) ^ 26 - ((1 - sqrt 5) / 2) ^ 26) 121392.99999999999 happens to be just on the wrong side of the truncate.
- tome 13y agoThat's not a Haskell question per se, but in any language you can implement it using two intergers (a, b) that represent the number a + b * sqrt(5).
- wslh 13y agoYes, it is a Haskell question more than you think ;-) since, for example, using types for fraction or other kind of patterns can work different in Haskell than in other languages. I think it's possible in Haskell to add symbolic manipulation as well like in http://christopherolah.wordpress.com/2012/06/01/hasksymb-an-experiment-in-haskell-symbolic-algebra/ http://christopherolah.wordpress.com/2012/06/01/hasksymb-an-... or http://homepages.inf.ed.ac.uk/wadler/realworld/docon2.html http://homepages.inf.ed.ac.uk/wadler/realworld/docon2.html Also, there are implementations in the list that can be implemented in the same way on non functional languages.
- tome 13y agoI think it would be neater doing it in Haskell than, say Java, but the fundamental idea would be the same in both.
- FreeFull 13y agoBut this is all about the factorial function, not the fibonacci sequence
- lelf 13y agoFor example like this (it provides exact result Edit—no matter how big n is). CReal is some magic. import Data.Number.CReal fib :: Integer -> Integer fib n = round $ (φ^^n - (-φ)^^(-n)) / sqrt 5 where φ = (1 + sqrt 5) / 2 :: CReal -- While we at it fib' n = fibs !! n where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
- carterschonwald 13y agoYeah, the constructive reals lib is really cool, and that's definitely an example where it really shines.
- Peaker 13y agoAnother one: fibs = map fst (iterate (\(cur,next)->(next,cur+next)) (0,1))
- wging 13y agoIt does miss a trivial optimization. For example, fac n = product [1..n] can be replaced with fac n = product [2..n] and will still do the right thing for n == 0, n == 1. Saves you a multiplication!
- lelf 13y agoYou are right! But let's do it the proper way {-# RULES "product/1" forall x. product [1..x] = product [2..x] #-} fac n = product [1..n]
- jfarmer 13y agoAlthough the original post wasn't about it, here's a version of exact arithmetic in the field extension containing phi. I wrote in Ruby a long time ago: https://gist.github.com/jfarmer/82500f2b52c540df5fbc https://gist.github.com/jfarmer/82500f2b52c540df5fbc You still have to implement the exponentiation algorithm, so you're never really going to get O(1). This is better than O(n), though. With those things implemented it becomes def fib_phi(n) ((PhiRational.new(0,1)**n - PhiRational.new(1,-1)**n)/PhiRational.new(-1, 2)).a.to_i end which is the explicit formula. I'd love to see the same thing in Haskell, which I imagine would look less crazy.
- nandemo 13y agoUnderstandable mistake, since fibonacci is the helloworld of functional programming. You might want to suggest something with the Sterling formula instead, but that would be trickier (it's an approximation, not an exact formula).