Constant-memory, log-time fibonacci numbers.

fibonacci.hs

import Data.Semigroup

data Fib =
  Fib Integer Integer Integer

instance Semigroup Fib where
  Fib a1 b1 c1 <> Fib a2 b2 c2 =
    Fib (a1*a2 + b1*b2) (a1*b2 + b1*c2) (b1*b2 + c1*c2)

  stimes =
    mtimesDefault

instance Monoid Fib where
  mempty =
    Fib 1 0 1

fibonacci n =
  let
    Fib _ y _ = stimes n (Fib 1 1 0)
  in
    y

main =
  print . fibonacci . read =<< getContents

gistfile1.txt

daniel@newport:~/Desktop
$ ghc -O2 fibonacci.hs
[1 of 1] Compiling Main             ( fibonacci.hs, fibonacci.o )
Linking fibonacci ...
daniel@newport:~/Desktop
$ echo 1000000000 | time ./fibonacci > fib-1000000000.txt
       88.41 real        85.37 user         2.52 sys
daniel@newport:~/Desktop
$ ls -l fib-1000000000.txt
-rw-r--r-- 1 daniel staff 200M Aug 13 18:25 fib-1000000000.txt
daniel@newport:~/Desktop
$

RE: https://www.reddit.com/r/math/comments/p3rgp9/ever_wondered_what_the_100000th_fibonacci_number/