Created
November 9, 2024 07:20
-
-
Save josephcsible/2523d098e40c2b1a11317f5daeb3d31b to your computer and use it in GitHub Desktop.
Closed-form Fibonacci numbers
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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