Anaconda and Applying euclid's algorithm for gcd: Difference between pages
m 1 revision imported |
m 1 revision imported |
||
| Line 1: | Line 1: | ||
[https://en.wikipedia.org/wiki/Euclidean_algorithm Euclid's algorithm] for the greatest common divisor is often among the first algorithms seen that has a significantly faster run time than the naive algorithm (exponentially faster, in fact). A traditional assignment is to ask you to work through the application of Euclid's algorithm on a pair of integers that are modestly large. | |||
=Example= | |||
Consider the integers 12345 and 67890. We let a=67890, b=12345, and apply the Euclidian algorithm in the following steps. | |||
* a = 5*b + 6165, so set a=12345 and b=6165 | |||
* a = 2*b + 15, so set a=6165 and b=15 | |||
* a = 441*b + 0, so gcd(a, b) = b | |||
We conclude that gcd(67890, 12345) = 15. Note that we could perform the divisions required by hand or used a calculator (or other means), but we have showed how we work through the algorithm until we have the gcd at the end (when we get a 0 remainder). | |||
= | =Assignment= | ||
You will be assigned values of a and b and asked to work out the gcd in the same way as above. | |||
'''Pass rating check''' You should follow the same steps as above, and include a similar amount of text as above so that you have clearly stated what you are doing, and someone can verify that you have applied Euclid's gcd algorithm correctly. | |||
You need to ''both'' hand in your work, and also check in with the help lab to demonstrate the algorithm. You can use your work that you hand in, and should talk the GA through the algorithm. The GA will make note if you are not able to do this, or if it seems you do not fully understand the process. | |||
''Note - the shared spreadsheet that GAs use for submitting information to Jeff Kinne's courses is [https://sycamoresindstate-my.sharepoint.com/:x:/g/personal/jeffrey_kinne_indstate_edu/ESbWO8QmBg9Jn9-ufDqR6_EBPzUbhzjVjyyzAPEAcjbMgg?e=XBpLEa this link], which should work only for the current term's GAs.'' | |||
Latest revision as of 13:22, 17 August 2025
Euclid's algorithm for the greatest common divisor is often among the first algorithms seen that has a significantly faster run time than the naive algorithm (exponentially faster, in fact). A traditional assignment is to ask you to work through the application of Euclid's algorithm on a pair of integers that are modestly large.
Example
Consider the integers 12345 and 67890. We let a=67890, b=12345, and apply the Euclidian algorithm in the following steps.
- a = 5*b + 6165, so set a=12345 and b=6165
- a = 2*b + 15, so set a=6165 and b=15
- a = 441*b + 0, so gcd(a, b) = b
We conclude that gcd(67890, 12345) = 15. Note that we could perform the divisions required by hand or used a calculator (or other means), but we have showed how we work through the algorithm until we have the gcd at the end (when we get a 0 remainder).
Assignment
You will be assigned values of a and b and asked to work out the gcd in the same way as above.
Pass rating check You should follow the same steps as above, and include a similar amount of text as above so that you have clearly stated what you are doing, and someone can verify that you have applied Euclid's gcd algorithm correctly. You need to both hand in your work, and also check in with the help lab to demonstrate the algorithm. You can use your work that you hand in, and should talk the GA through the algorithm. The GA will make note if you are not able to do this, or if it seems you do not fully understand the process.
Note - the shared spreadsheet that GAs use for submitting information to Jeff Kinne's courses is this link, which should work only for the current term's GAs.