74 lines
2.7 KiB
Python
74 lines
2.7 KiB
Python
|
import timeit
|
||
|
|
import numpy as np
|
||
|
|
|
||
|
|
def fact_rec(n):
|
||
|
|
# y = fact_rec(n) berechnet die Fakultät von n als fact_rec(n) = n * fact_rec(n -1) mit fact_rec(0) = 1
|
||
|
|
# Fehler, falls n < 0 oder nicht ganzzahlig
|
||
|
|
if n < 0 or np.trunc(n) != n:
|
||
|
|
raise Exception('The factorial is defined only for positive integers')
|
||
|
|
if n <=1:
|
||
|
|
return 1
|
||
|
|
else:
|
||
|
|
return n*fact_rec(n-1)
|
||
|
|
|
||
|
|
def fact_for(n):
|
||
|
|
if n < 0 or np.trunc(n) != n:
|
||
|
|
raise Exception('The factorial is defined only for positive integers')
|
||
|
|
result = 1
|
||
|
|
for i in range(1, n + 1):
|
||
|
|
result *= i
|
||
|
|
return result
|
||
|
|
|
||
|
|
def test_same_value(maxn):
|
||
|
|
test_successful = True
|
||
|
|
for n in range(maxn + 1):
|
||
|
|
if(fact_rec(n)) != fact_for(n):
|
||
|
|
print("Test (same value) failed at: ", n)
|
||
|
|
test_successful = False
|
||
|
|
if test_successful:
|
||
|
|
print("Test (same value) successful. Max n: ", maxn)
|
||
|
|
return test_successful
|
||
|
|
|
||
|
|
def compaire_execution_times(n, execution_count):
|
||
|
|
print("Starting Test to comaire execution times:")
|
||
|
|
time_rec = np.mean(np.array(timeit.repeat("fact_rec(" + str(n) + ")", "from __main__ import fact_rec", number=execution_count)))
|
||
|
|
time_for = np.mean(np.array(timeit.repeat("fact_for(" + str(n) + ")", "from __main__ import fact_for", number=execution_count)))
|
||
|
|
factor = time_rec / time_for
|
||
|
|
print("time recursively: ", time_rec)
|
||
|
|
print("time with for loop: ", time_for)
|
||
|
|
print("execution with for loop is ", factor, " times faster.")
|
||
|
|
|
||
|
|
# mit einer For-Schleife ist die Ausführung etwa 9 mal schneller. Wenn die Fakultät rekursiv berechnet wird muss die Funktion n mal aufgerufen werden
|
||
|
|
# und es müssen entsprechend viele zwischenergebnisse gespeichert werden bis die Berechnung abgeschlossen ist.
|
||
|
|
# Mit einer For-Schleife kann jeweils das letzte zwischenergebnis verworfen / überschrieben werden.
|
||
|
|
|
||
|
|
def find_upper_limit_int(min_n, max_n):
|
||
|
|
print("Starting Test upper Limit with int:")
|
||
|
|
for n in range(min_n, max_n + 1):
|
||
|
|
try:
|
||
|
|
print(n, ": ", fact_for(n))
|
||
|
|
except Exception as e:
|
||
|
|
print("Failed at n = ", n, "Error Message:\n", str(e))
|
||
|
|
|
||
|
|
# Für Integer gibt es keine Obergrenze. Die Werte werden berechnet.
|
||
|
|
|
||
|
|
def find_upper_limit_float(min_n, max_n):
|
||
|
|
print("Starting Test upper Limit with float:")
|
||
|
|
for n in range(min_n, max_n + 1):
|
||
|
|
try:
|
||
|
|
print(n, ": ", float(fact_for(n)))
|
||
|
|
except Exception as e:
|
||
|
|
print("Failed at n = ", n, "Error Message:\n", str(e))
|
||
|
|
|
||
|
|
# Für Float gibt es eine Obergrenze. Wird diese überschritten können die Werte nicht mehr als Float ausgegeben werden.
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
test_same_value(50)
|
||
|
|
compaire_execution_times(500, 100)
|
||
|
|
find_upper_limit_int(190, 200)
|
||
|
|
find_upper_limit_float(170, 171)
|
||
|
|
|
||
|
|
|