Last active
February 28, 2020 21:15
-
-
Save Solonarv/28beb95ffc9e69c7cbc0d55921d06909 to your computer and use it in GitHub Desktop.
Overengineered fast fibonacci
This file contains 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
{-# LANGUAGE UnboxedTuples #-} | |
{-# LANGUAGE MagicHash #-} | |
module FastFibo where | |
import GHC.Exts | |
type Mat2x2 = (# Int#, Int#, Int#, Int# #) | |
type Vec2 = (# Int#, Int# #) | |
( #+# ) :: Mat2x2 -> Mat2x2 -> Mat2x2 | |
(# x11, x12, x21, x22 #) #+# (# y11, y12, y21, y22 #) = (# x11+#y11, x12+#y12, x21+#y21, x22+#y22 #) | |
{-# INLINE ( #+# ) #-} | |
( #*# ) :: Mat2x2 -> Mat2x2 -> Mat2x2 | |
(# x11, x12, x21, x22 #) #*# (# y11, y12, y21, y22 #) | |
= (# x11*#y11 +# x12*#y21, x11*#y12 +# x12*#y22 | |
, x21*#y11 +# x22*#y21, x21*#y12 +# x22*#y22 | |
#) | |
{-# INLINE ( #*# ) #-} | |
( #*^ ) :: Mat2x2 -> Vec2 -> Vec2 | |
(# x11, x12, x21, x22 #) #*^ (# a, b #) = (# a*#x11 +# b*#x12, a*#x21 +# b*#x22 #) | |
mpow :: Word -> Mat2x2 -> Mat2x2 | |
mpow 0 mat = (# 1#, 0#, 0#, 1# #) | |
mpow 1 mat = mat | |
mpow n mat = let | |
n' = n `div` 2 | |
mat' = mpow n' mat | |
in if even n | |
then mat' #*# mat' | |
else mat #*# mat' #*# mat' | |
fastFib :: Int -> Int -> Word -> Int | |
fastFib (I# x) (I# y) n = case mpow n fibMat #*^ (# x, y #) of | |
(# res, _ #) -> I# res | |
where fibMat = (# 1#, 1#, 1#, 0# #) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
ew