Analysing These Algorithms - How Steps & Work Scale - Class 9 Maths - Euclid’s and Āryabhaṭa’s Algorithms

part 2 - Analysing These Algorithms - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Analysing These Algorithms - Euclid’s and Āryabhaṭa’s Algorithms - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo · Class 9 Explore Class 9

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.

CA Maninder Singh's photo - Co-founder, Teachoo

Made by

CA Maninder Singh

CA Maninder Singh is a Chartered Accountant qualified since 2010 and an educator teaching since 2006. At Teachoo, he draws on his accounting and tax experience to explain Accounts, Income Tax and GST through step-by-step lessons and practical examples.

For an uninterrupted learning experience, students can use Teachoo Black to remove ads and focus better.