Skip to content

Instantly share code, notes, and snippets.

@friedbrice
Last active August 14, 2021 01:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save friedbrice/37df508994d1e07243ca75bb6d79c912 to your computer and use it in GitHub Desktop.
Save friedbrice/37df508994d1e07243ca75bb6d79c912 to your computer and use it in GitHub Desktop.
Constant-memory, log-time fibonacci numbers.
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
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
$
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment