Skip to content

Instantly share code, notes, and snippets.

@josephcsible
Created November 9, 2024 07:20
Show Gist options
  • Save josephcsible/2523d098e40c2b1a11317f5daeb3d31b to your computer and use it in GitHub Desktop.
Save josephcsible/2523d098e40c2b1a11317f5daeb3d31b to your computer and use it in GitHub Desktop.
Closed-form Fibonacci numbers
import Data.Maybe (fromJust)
import Data.Ratio ((%), numerator, denominator)
data FibHelper = FibHelper Rational Rational deriving(Eq,Read,Show)
compareFibHelperWithZero :: FibHelper -> Ordering
compareFibHelperWithZero (FibHelper a b) = (a * abs a) `compare` (-5 * b * abs b)
instance Ord FibHelper where
x `compare` y = compareFibHelperWithZero (x - y)
instance Num FibHelper where
FibHelper xa xb + FibHelper ya yb = FibHelper (xa + ya) (xb + yb)
FibHelper xa xb - FibHelper ya yb = FibHelper (xa - ya) (xb - yb)
FibHelper xa xb * FibHelper ya yb = FibHelper (xa * ya + 5 * xb * yb) (xa * yb + xb * ya)
negate (FibHelper a b) = FibHelper (negate a) (negate b)
abs x = case compareFibHelperWithZero x of
LT -> negate x
_ -> x
signum x = case compareFibHelperWithZero x of
LT -> -1
EQ -> 0
GT -> 1
fromInteger a = FibHelper (fromInteger a) 0
instance Fractional FibHelper where
recip (FibHelper a b) = FibHelper (a / d) (-b / d) where d = a*a - 5*b*b
fromRational a = FibHelper a 0
fibHelperToInteger :: FibHelper -> Maybe Integer
fibHelperToInteger (FibHelper a b) = if denominator a == 1 && b == 0 then Just (numerator a) else Nothing
fib :: Integer -> Integer
fib x = fromJust . fibHelperToInteger $ (FibHelper (1 % 2) (1 % 10)) * (FibHelper (1 % 2) (1 % 2)) ^^ x + (FibHelper (1 % 2) (-1 % 10)) * (FibHelper (1 % 2) (-1 % 2)) ^^ x
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment