Fibonacci sequence: Difference between revisions
Content deleted Content added
IDL -> recursive, iterative and analytic versions with comments about run-time |
→{{header|Haskell}}: Matrix exponentiation alternative |
||
| Line 185: | Line 185: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
=== With lazy lists === |
|||
This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers: |
This is a standard example how to use lazy lists. Here's the (infinite) list of all Fibonacci numbers: |
||
| Line 193: | Line 194: | ||
fib !! n |
fib !! n |
||
=== With matrix exponentiation === |
|||
With the (rather slow) code from [[Matrix exponentiation operator]] |
|||
<pre> |
|||
import Data.List |
|||
xs <+> ys = zipWith (+) xs ys |
|||
xs <*> ys = sum $ zipWith (*) xs ys |
|||
newtype Mat a = Mat {unMat :: [[a]]} deriving Eq |
|||
instance Show a => Show (Mat a) where |
|||
show xm = "Mat " ++ show (unMat xm) |
|||
instance Num a => Num (Mat a) where |
|||
negate xm = Mat $ map (map negate) $ unMat xm |
|||
xm + ym = Mat $ zipWith (<+>) (unMat xm) (unMat ym) |
|||
xm * ym = Mat [[xs <*> ys | ys <- transpose $ unMat ym] | xs <- unMat xm] |
|||
fromInteger n = Mat [[fromInteger n]] |
|||
</pre> |
|||
we can simply write |
|||
<pre> |
|||
fib n = last $ head $ unMat $ (Mat [[1,1],[1,0]]) ^ n |
|||
</pre> |
|||
So, for example, the ten-thousendth Fiboncacci number starts with the digits |
|||
<pre> |
|||
*Main> take 10 $ show $ fib (10^5) |
|||
"2597406934" |
|||
</pre> |
|||
=={{header|IDL}}== |
=={{header|IDL}}== |
||