Last active
June 21, 2023 13:35
-
-
Save ukBaz/72d690f36987b8b526a3c5a3d167686d to your computer and use it in GitHub Desktop.
Fibonacci Sequence using collections.deque
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from collections import deque | |
correct_values = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, | |
987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, | |
75025, 121393, 196418, 317811] | |
def get_item(request): | |
fib_seq = deque([0, 1], 2) | |
if request < 2: | |
return fib_seq[request] | |
else: | |
for i in range(1, request): | |
fib_seq.append(sum(fib_seq)) | |
return fib_seq[-1] | |
if __name__ == '__main__': | |
for pos in range(0, len(correct_values)): | |
print('{}: {} should be {}'.format(pos, get_item(pos), correct_values[pos])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Thanks to Matt Parker for this one using Binet Formula | |
# https://youtu.be/ghxQA3vvhsk | |
# | |
from math import sqrt | |
correct_values = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, | |
987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, | |
75025, 121393, 196418, 317811] | |
def get_item(request): | |
return round((((1+sqrt(5))/2)**request - ((1-sqrt(5))/2)**request)/sqrt(5)) | |
if __name__ == '__main__': | |
for pos in range(0, len(correct_values)): | |
print('{}: {} should be {}'.format(pos, get_item(pos), correct_values[pos])) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
correct_values = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, | |
987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, | |
75025, 121393, 196418, 317811] | |
def get_item(request): | |
if request < 1: | |
return 0 | |
if request <= 2: | |
return 1 | |
else: | |
return get_item(request - 1) + get_item(request - 2) | |
if __name__ == '__main__': | |
for pos in range(0, len(correct_values)): | |
print('{}: {} should be {}'.format(pos, get_item(pos), correct_values[pos])) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from timeit import timeit | |
for request in (4, 7, 10): | |
print(f"\nRequesting the {request}th number in the sequence:") | |
for module in ('fibonacci', 'fibonacci2', 'fibonacci3'): | |
fib_time = timeit(f'get_item({request})', | |
setup=f'from {module} import get_item', | |
number=1_000_000) | |
print(f"\tRequest took {fib_time:5.2f}\u03BCs for {module}") | |
# Example result: | |
# Requesting the 4th number in the sequence: | |
# Request took 0.91μs for fibonacci | |
# Request took 0.70μs for fibonacci2 | |
# Request took 0.83μs for fibonacci3 | |
# | |
# Requesting the 7th number in the sequence: | |
# Request took 2.49μs for fibonacci | |
# Request took 0.62μs for fibonacci2 | |
# Request took 3.22μs for fibonacci3 | |
# | |
# Requesting the 10th number in the sequence: | |
# Request took 1.69μs for fibonacci | |
# Request took 0.63μs for fibonacci2 | |
# Request took 13.94μs for fibonacci3 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment