Skip to content

Instantly share code, notes, and snippets.

@aljce
Created October 26, 2020 23:07
Show Gist options
  • Save aljce/9867198c67ac399c54034524adf14a01 to your computer and use it in GitHub Desktop.
Save aljce/9867198c67ac399c54034524adf14a01 to your computer and use it in GitHub Desktop.
data Extension a = Extension
{ real :: !a, extn :: !a } -- real + extn*sqrt(5)
deriving Show
instance Num a => Num (Extension a) where
(Extension a b) + (Extension c d) = Extension (a + c) (b + d)
(Extension a b) - (Extension c d) = Extension (a - c) (b - d)
(Extension a b) * (Extension c d) = Extension (a * c + 5 * b * d) (a * d + b * c)
negate (Extension a b) = Extension (negate a) (negate b)
fromInteger n = Extension (fromInteger n) 0
abs = error "why is this in this class"
signum = error "sad"
instance Fractional a => Fractional (Extension a) where
recip (Extension a b) = Extension (a / den) (- b / den)
where den = a * a - 5 * b * b
fromRational n = Extension (fromRational n) 0
phi :: Extension Rational
phi = Extension (1 / 2) (1 / 2)
sqrtFive :: Extension Rational
sqrtFive = Extension 0 1
fibonacci :: Integer -> Integer
fibonacci = numerator . real . closedForm -- the closed form always returns an integer
where
closedForm :: Integer -> Extension Integer
closedForm n = (phi ^ n - (1 - phi) ^ n) / sqrtFive
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment