Applying euclid's algorithm for gcd

From Computer Science
Revision as of 15:43, 29 August 2022 by Jkinne (talk | contribs) (Created page with "[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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.