Skip to content

Instantly share code, notes, and snippets.

@aibrahim

aibrahim/fast fib

Created November 13, 2017 10:48
Show Gist options
  • Save aibrahim/f48b8d35eaa4e63013dd66e07fce47cc to your computer and use it in GitHub Desktop.
Save aibrahim/f48b8d35eaa4e63013dd66e07fce47cc to your computer and use it in GitHub Desktop.
Download ZIP
Raw
fast fib
(defn fast-fib [n]
(if (== n 0)
[0, 1]
(let [[a, b] (fast-fib (/ n 2))
c (* a (- (* b 2) a))
d (+ (* a a) (* b b))]
(if (zero? (mod n 2))
[c, d]
[d, (+ c d)]))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment