Skip to content

Instantly share code, notes, and snippets.

View fibonacci.py
import numpy as np
import matplotlib.pyplot as plt
from timeit import *
def collect_results():
results = []
for i in range(1000, 2000001, 100000):
f = "fast_doubling_fibonacci_recursive"
t1 = Timer(f"{f}({i})",
f"from __main__ import {f}")
View fibonacci.py
def collect_results():
results = []
for i in range(1000, 2000001, 100000):
f = "fast_doubling_fibonacci_recursive"
t1 = Timer(f"{f}({i})",
f"from __main__ import {f}")
st1 = t1.timeit(number=10)
f = "matrix_fibonacci"
t2 = Timer(f"{f}({i})",
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Create timings
View fibonacci.py
from timeit import *
def collect_results():
results = []
for i in range(1000, 2000001, 100000):
f = "fast_doubling_fibonacci_recursive"
t1 = Timer(f"{f}({i})",
f"from __main__ import {f}")
st1 = t1.timeit(number=10)
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Fast Doubling Iterative
View fibonacci.py
def fast_doubling_fibonacci_iterative(n):
"""
Args:
n ():
Returns:
>>> fast_doubling_fibonacci_iterative(80)
23416728348467685
>>> fast_doubling_fibonacci_iterative(800)
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Fast Doubling Iterative
View fibonacci.py
def fast_doubling_fibonacci_iterative(n):
"""
Args:
n ():
Returns:
>>> fast_doubling_fibonacci_iterative(80)
23416728348467685
>>> fast_doubling_fibonacci_iterative(800)
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Fast doubling Fibonacci
View fibonacci.py
import functools
@functools.lru_cache()
def _fd_fib(n: int) -> tuple:
"""_fd_fib.
Args:
n (int): n
Returns:
tuple:
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Katasuba fast multiplication
View fibonacci.py
def karatsuba_fast_multiply(multiplier: int, multiplicand: int) -> int:
"""
Karatsuba fast multiplication, published in 1962
https://en.wikipedia.org/wiki/Karatsuba_algorithm
Args:
x ():
y ():
Returns: int
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Karatsuba fast multiplication
View fibonacci.py
def karatsuba_fast_multiply(multiplier: int, multiplicand: int) -> int:
"""
Karatsuba fast multiplication, published in 1962
https://en.wikipedia.org/wiki/Karatsuba_algorithm
Args:
x ():
y ():
Returns: int
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Karatsuba Fast Multiplication
View fibonacci.py
def karatsuba_fast_multiply(multiplier: int, multiplicand: int) -> int:
"""
Karatsuba fast multiplication, published in 1962
https://en.wikipedia.org/wiki/Karatsuba_algorithm
Args:
x ():
y ():
Returns: int
@raeq
raeq / fibonacci.py
Created Sep 5, 2020
Djisktra uses Lucas Powers to calculate Fibonacci
View fibonacci.py
def lucas_power(n: float):
"""lucas_power.
Args:
n (float): n
"""
if n == 1:
return (1, 1)
L, F = lucas_power(n // 2)
You can’t perform that action at this time.