Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 9b945cb

Browse files
StephenGeminpoyea
authored andcommitted
Iterative fibonacci with unittests from slash (TheAlgorithms#882)
* iterative and formula fibonacci methods Added two ways to calculate the fibonacci sequence: (1) iterative (2) formula. I've also added a timer decorator so someone can see the difference in computation time between these two methods. Added two unittests using the slash framework. * Update test_fibonacci.py * remove inline comments per Contributing Guidelines * Update sol5.py * Create placeholder.py * Update and rename maths/test_fibonacci.py to maths/tests/test_fibonacci.py * Delete placeholder.py * Create __init__.py * Update test_fibonacci.py * Rename Maths/lucasSeries.py to maths/lucasSeries.py * Update and rename Project Euler/Problem 01/sol5.py to project_euler/problem_01/sol6.py
1 parent 6e894ba commit 9b945cb

6 files changed

Lines changed: 164 additions & 8 deletions

File tree

‎Project Euler/Problem 01/sol5.py‎

Lines changed: 0 additions & 8 deletions
This file was deleted.

‎maths/fibonacci.py‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
# fibonacci.py
2+
"""
3+
1. Calculates the iterative fibonacci sequence
4+
5+
2. Calculates the fibonacci sequence with a formula
6+
an = [ Phin - (phi)n ]/Sqrt[5]
7+
reference-->Su, Francis E., et al. "Fibonacci Number Formula." Math Fun Facts. <http://www.math.hmc.edu/funfacts>
8+
"""
9+
import math
10+
import functools
11+
import time
12+
from decimal import getcontext, Decimal
13+
14+
getcontext().prec = 100
15+
16+
17+
def timer_decorator(func):
18+
@functools.wraps(func)
19+
def timer_wrapper(*args, **kwargs):
20+
start = time.time()
21+
func(*args, **kwargs)
22+
end = time.time()
23+
if int(end - start) > 0:
24+
print(f'Run time for {func.__name__}: {(end - start):0.2f}s')
25+
else:
26+
print(f'Run time for {func.__name__}: {(end - start)*1000:0.2f}ms')
27+
return func(*args, **kwargs)
28+
return timer_wrapper
29+
30+
31+
# define Python user-defined exceptions
32+
class Error(Exception):
33+
"""Base class for other exceptions"""
34+
35+
36+
class ValueTooLargeError(Error):
37+
"""Raised when the input value is too large"""
38+
39+
40+
class ValueTooSmallError(Error):
41+
"""Raised when the input value is not greater than one"""
42+
43+
44+
class ValueLessThanZero(Error):
45+
"""Raised when the input value is less than zero"""
46+
47+
48+
def _check_number_input(n, min_thresh, max_thresh=None):
49+
"""
50+
:param n: single integer
51+
:type n: int
52+
:param min_thresh: min threshold, single integer
53+
:type min_thresh: int
54+
:param max_thresh: max threshold, single integer
55+
:type max_thresh: int
56+
:return: boolean
57+
"""
58+
try:
59+
if n >= min_thresh and max_thresh is None:
60+
return True
61+
elif min_thresh <= n <= max_thresh:
62+
return True
63+
elif n < 0:
64+
raise ValueLessThanZero
65+
elif n < min_thresh:
66+
raise ValueTooSmallError
67+
elif n > max_thresh:
68+
raise ValueTooLargeError
69+
except ValueLessThanZero:
70+
print("Incorrect Input: number must not be less than 0")
71+
except ValueTooSmallError:
72+
print(f'Incorrect Input: input number must be > {min_thresh} for the recursive calculation')
73+
except ValueTooLargeError:
74+
print(f'Incorrect Input: input number must be < {max_thresh} for the recursive calculation')
75+
return False
76+
77+
78+
@timer_decorator
79+
def fib_iterative(n):
80+
"""
81+
:param n: calculate Fibonacci to the nth integer
82+
:type n:int
83+
:return: Fibonacci sequence as a list
84+
"""
85+
n = int(n)
86+
if _check_number_input(n, 2):
87+
seq_out = [0, 1]
88+
a, b = 0, 1
89+
for _ in range(n-len(seq_out)):
90+
a, b = b, a+b
91+
seq_out.append(b)
92+
return seq_out
93+
94+
95+
@timer_decorator
96+
def fib_formula(n):
97+
"""
98+
:param n: calculate Fibonacci to the nth integer
99+
:type n:int
100+
:return: Fibonacci sequence as a list
101+
"""
102+
seq_out = [0, 1]
103+
n = int(n)
104+
if _check_number_input(n, 2, 1000000):
105+
sqrt = Decimal(math.sqrt(5))
106+
phi_1 = Decimal(1 + sqrt) / Decimal(2)
107+
phi_2 = Decimal(1 - sqrt) / Decimal(2)
108+
for i in range(2, n):
109+
temp_out = ((phi_1**Decimal(i)) - (phi_2**Decimal(i))) * (Decimal(sqrt) ** Decimal(-1))
110+
seq_out.append(int(temp_out))
111+
return seq_out
112+
113+
114+
if __name__ == '__main__':
115+
num = 20
116+
# print(f'{fib_recursive(num)}\n')
117+
# print(f'{fib_iterative(num)}\n')
118+
# print(f'{fib_formula(num)}\n')
119+
fib_iterative(num)
120+
fib_formula(num)

‎maths/tests/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
from .. import fibonacci

‎maths/tests/test_fibonacci.py‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
"""
2+
To run with slash:
3+
1. run pip install slash (may need to install C++ builds from Visual Studio website)
4+
2. In the command prompt navigate to your project folder
5+
3. then type--> slash run -vv -k tags:fibonacci ..
6+
-vv indicates the level of verbosity (how much stuff you want the test to spit out after running)
7+
-k is a way to select the tests you want to run. This becomes much more important in large scale projects.
8+
"""
9+
10+
import slash
11+
from .. import fibonacci
12+
13+
default_fib = [0, 1, 1, 2, 3, 5, 8]
14+
15+
16+
@slash.tag('fibonacci')
17+
@slash.parametrize(('n', 'seq'), [(2, [0, 1]), (3, [0, 1, 1]), (9, [0, 1, 1, 2, 3, 5, 8, 13, 21])])
18+
def test_different_sequence_lengths(n, seq):
19+
"""Test output of varying fibonacci sequence lengths"""
20+
iterative = fibonacci.fib_iterative(n)
21+
formula = fibonacci.fib_formula(n)
22+
assert iterative == seq
23+
assert formula == seq
24+
25+
26+
@slash.tag('fibonacci')
27+
@slash.parametrize('n', [7.3, 7.8, 7.0])
28+
def test_float_input_iterative(n):
29+
"""Test when user enters a float value"""
30+
iterative = fibonacci.fib_iterative(n)
31+
formula = fibonacci.fib_formula(n)
32+
assert iterative == default_fib
33+
assert formula == default_fib
34+

‎project_euler/problem_01/sol6.py‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
a = 3
2+
result = 0
3+
while a < 1000:
4+
if(a % 3 == 0 or a % 5 == 0):
5+
result += a
6+
elif(a % 15 == 0):
7+
result -= a
8+
a += 1
9+
print(result)

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /