Made by: Jevan, and Juan
- Implement several algorithms related to computing the GCD(m, n) of two integers m and n.
- Empirically determine the run-time complexity for different kinds of input (average-case / worst-case).
- Write a short report summarizing the outcome of project in form of tables and scatter-plots.
- Built using python 3.7
- matplotlib is required (Version 3.0.2)
- matplotlib.pyplot
- matplotlib.patches
❗ Note to use 'Scatter plot mode', matplotlib must be installed! Below is our programs output for 'User testing mode'
[1] Enter 'User testing mode' [2] Enter 'Scatter plot mode' [3] Exit Option: 1 Mode: User testing [1] Task 1 [2] Task 2 [3] Task 3 [4] Go Back [5] Exit Option: 1 Task 1: Enter positive value for 'n': 4 Average number of Modulo Divisions GCD is: 1.25 Average number of Divisions GCD is: 2.75 Mode: User testing [1] Task 1 [2] Task 2 [3] Task 3 [4] Go Back [5] Exit Option: 2 Task 2: Enter positive value for 'k': 16 Fibonacci Sequence: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987] Total number of Modulo Divisions is: 92 Fibonacci value of k: 987 Number of Modulo Divisions for the value of k: 14 Time Taken to output result: 0.0 Mode: User testing [1] Task 1 [2] Task 2 [3] Task 3 [4] Go Back [5] Exit Option: 3 Task 3: Enter positive (m > 1) value for 'm': 15 Enter positive (n > 1) value for 'n': 9 Sieve's Algorithm based on 'm': [2, 3, 5, 7, 11, 13] Sieve's Algorithm based on 'n': [2, 3, 5, 7] Prime factors for 'm': [3, 5] Prime factors for 'n': [3, 3] Middle-school GCD(15,9) = 3 = 3