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