Euclid’s and Ä€ryabhaáąa’s Algorithms
Euclid’s and Ä€ryabhaáąa’s Algorithms
Last updated at October 28, 2026 by Teachoo
Transcript
Analysing These Algorithms In previous section, we improved the original GCD algorithm by: Finding common divisors directly. Checking only up to the smaller input. Storing only the greatest common divisor found so far. For positive integers 𝑚,𝑛, the resulting algorithm was: Set most-recent-common-divisor to 1. Examine each integer from 2 to min(𝑚,𝑛). Whenever a candidate divides both inputs, update the stored value. Report the final stored value. Now we another question How much work does it require? Work required by our current algorithms Now we another question How much work does it require? Work required by our current algorithms Increasing the input by a factor of 10 increases the number of checks roughly tenfold—even though it adds only one digit. This is similar to addition by counting dots: the work depends on the value, rather than mainly on the number of digits. Removing lists saved storage, but did not remove this long search. The next goal Can we find the GCD without examining every possible divisor? The next two alogirthms answer this by reducing the numbers themselves. Smaller input | Number of digits | Candidates checked from 2 onwards 100 | 3 | 99 1000 | 4 | 999 10000 | 5 | 9999 The next goal Can we find the GCD without examining every possible divisor? The next two algorithms answer this by reducing the numbers themselves.