gistfile1.hs

--type for the "collapsed" fibonacci matrices
type Fiblist = (Integer, Integer, Integer)
  
-- This data type wraps the double-return value needed by fibSum'
data PowerSum = PowerSum {
  curr_pow :: Fiblist,
  curr_sum :: Fiblist
}
 
i = (1,0,1)
b = (8,2,0)
m = (4,1,0)
 
-- misc helper functions
first :: Fiblist -> Integer
first (a, b, c) = a
 
(.+) :: Fiblist -> Fiblist -> Fiblist
(.+) (a1, a2, a3) (b1, b2, b3) = (a1+b1, a2+b2, a3+b3)
 
(.*) :: Fiblist -> Fiblist -> Fiblist
(.*) (a1, a2, a3) (b1, b2, b3) = (a1*b1 + a2*b2, a1*b2 + a2*b3, a2*b2 + a3*b3)
 
-- top-level, bootstrapping function
fibSum :: (Integral a) => a -> Integer
fibSum 0 = 0
fibSum 1 = 2
fibSum n = let sum_list = curr_sum (fibSum' (n-2))
           in first (b .* sum_list) + 2
 
--recursive function. Does the heavy lifting
fibSum' :: (Integral a) => a -> PowerSum
fibSum' n
  | n == 0 = PowerSum i i
  | odd n = let ps = fibSum' (floor (fromIntegral n/2))
                s = (curr_sum ps) -- sum as of floor(n/2)
                p = (curr_pow ps) -- m ^ floor(n/2)
                t = p .* m -- m ^ ceil(n/2)
                m_exp_n = t .* p -- m ^ n
             in PowerSum m_exp_n ((t .* s) .+ s)
  | even n = let ps = fibSum' ((n `div` 2) - 1)
                 s = (curr_sum ps) -- sum as of n/2 - 1
                 p = (curr_pow ps) -- m ^ (n/2 - 1)
                 t = p .* m -- m ^ n/2
                 m_exp_n = t .* t -- m ^ n
             in PowerSum m_exp_n ((t .* s) .+ s .+ m_exp_n)