83 lines
2.6 KiB
Python
83 lines
2.6 KiB
Python
#Greatest Common Divisor First Method - Euclid's Algorithm - recurisive
|
|
def gcd1(a,b):
|
|
if a == 0 and b != 0:
|
|
return b
|
|
if a != 0 and b == 0:
|
|
return a
|
|
#check if the numbers are positive integers, if not raise an error
|
|
if a < 1 or b < 1:
|
|
raise ValueError("Both numbers must be positive integers")
|
|
return helper_gcd1(a,b)
|
|
|
|
def helper_gcd1(a,b):
|
|
#Euclid's Algorithm: If one number is 0, the other number is the GCD. If not, divide the larger number by the smaller number, then divide the divisor by the remainder, repeat until the remainder
|
|
if b == 0:
|
|
return a
|
|
if a == 0:
|
|
return b
|
|
if a > b:
|
|
return helper_gcd1(a%b, b)
|
|
else:
|
|
return helper_gcd1(a, b%a)
|
|
|
|
#Greatest Common Divisor Second Method - Repeat Subtraction
|
|
def gcd2(a,b):
|
|
#check if the numbers are positive integers, if not raise an error
|
|
if a == 0 and b != 0:
|
|
return b
|
|
if a != 0 and b == 0:
|
|
return a
|
|
if a < 1 or b < 1:
|
|
raise ValueError("Both numbers must be positive integers")
|
|
#Euclid's Algorithm: If one
|
|
while a != b:
|
|
if a > b:
|
|
a -= b
|
|
else:
|
|
b -= a
|
|
return a
|
|
|
|
#Greatest Common Divisor Third Method - Euclid's Algorithm
|
|
def gcd3(a,b):
|
|
#check if the numbers are positive integers, if not raise an error
|
|
if a == 0 and b != 0:
|
|
return b
|
|
if a != 0 and b == 0:
|
|
return a
|
|
if a < 1 or b < 1:
|
|
raise ValueError("Both numbers must be positive integers")
|
|
#Euclid's Algorithm: Divide the larger number by the smaller number, then divide the divisor by the remainder, repeat until the remainder
|
|
while b:
|
|
a,b = b,a%b
|
|
return a
|
|
|
|
#Time Function
|
|
import time
|
|
from tabulate import tabulate
|
|
def time_function(function):
|
|
#input values for gcd
|
|
input1 = [13, 18, 100, 252, 105, 625, 1000, 10000, 100000, 1000000, 3]
|
|
input2 = [5, 24, 75, 147, 200, 500, 2100, 20000, 200000, 2000200, 0]
|
|
#expected results for gcd
|
|
expected = [1, 6, 25, 21, 5, 125, 100, 10000, 100000, 200,3]
|
|
#results and times of running the gcd functions
|
|
ret = []
|
|
times = []
|
|
for i in range(len(input1)):
|
|
start = time.time() #start time
|
|
ret.append(function(input1[i], input2[i])) #run the function and append the result
|
|
end = time.time() #end time
|
|
times.append(end-start) #calculate the time taken
|
|
#print the results nicely
|
|
labels2 = ["Expected", "Results", "Times"]
|
|
table = [expected, ret, times]
|
|
print(tabulate(table, showindex=labels2, tablefmt="fancy_grid"))
|
|
|
|
|
|
def main():
|
|
time_function(gcd1)
|
|
time_function(gcd2)
|
|
time_function(gcd3)
|
|
|
|
if __name__ == "__main__":
|
|
main() |