Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW
Created May 12, 2021 07:32
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 Hermann-SW/caa1c0c9c4564abf778b9d124bf773a5 to your computer and use it in GitHub Desktop.
Save Hermann-SW/caa1c0c9c4564abf778b9d124bf773a5 to your computer and use it in GitHub Desktop.
fast Fibonacci numbers / builtin µs timing code made platform independent (python[23] / Pico MicroPython)
from sys import platform
if platform=='rp2':
from time import ticks_us as default_timer
def delta(t0,t1):
return t1-t0
else:
from timeit import default_timer
def delta(t0,t1):
return int(1000000*(t1-t0)+0.5)
def calc(t, odd):
return ((t[1]**2 + t[0]**2 ), (t[1]**2 + 2*t[0]*t[1])) if odd\
else ((t[1]**2 - (t[1]-t[0])**2), (t[1]**2 + t[0]**2 ))
def fib(n):
if n==0:
return (0, 1)
elif n==1:
return (1, 1)
else:
return calc(fib(n//2), n%2 == 1)
def Ffast(n):
return fib(n)[0]
def F(n):
a=0
b=1
for i in range(0,n):
n=a+b
a=b
b=n
return a
def tst(N, pF=True):
for n in range(N-9, 1+N):
start=default_timer()
r=F(n)
stop=default_timer()
r2=Ffast(n)
stop2=default_timer()
print(r if pF else len(str(r)), delta(start,stop), r==r2, delta(stop,stop2))
print(delta(default_timer(),default_timer()))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment