Skip to content

Instantly share code, notes, and snippets.

@en0

en0/fib_theory.py

Created February 16, 2020 21:28
Show Gist options
  • Save en0/567376daab613162559a6cb96249bc50 to your computer and use it in GitHub Desktop.
Save en0/567376daab613162559a6cb96249bc50 to your computer and use it in GitHub Desktop.
Download ZIP
A attempt at computing the nth fib number in O(1) - didn't work of course because phi is irrational and poor approximations gets me to about fib(70) before it becomes inaccurate.
Raw
fib_theory.py
# This is not computationally accurate due to a poor
# representation of root 5
root5 = 5 ** 0.5
phi = (1 + root5) / 2
fib = lambda n: int(round((phi ** n) / root5))
fib(70)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment