Ex 11.3, 2 - What about the last algorithm described above? What - Exercise Set 11.3

part 2 - Ex 11.3, 2 - Exercise Set 11.3 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Ex 11.3, 2 - Exercise Set 11.3 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Ex 11.3, 2 - Exercise Set 11.3 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo Β· Class 9 Explore Class 9

Transcript

Ex 11.3, 2 What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1? The last algorithm described above is Final improved algorithm for gcd Set most-recent-common-divisor to 1. For each number π‘˜ from 2 to min(π‘š,𝑛) : If π‘˜ divides both π‘š and 𝑛, set most-recent-common-divisor to π‘˜. Report most-recent-common-divisor as gcd(π‘š,𝑛) In the last algorithm, We store only the most recently found common divisor When scanning upwards, each new common divisor is greater than the previous one. When scanning downwards, each new common divisor is smaller Therefore, we must change how we use the result. The first common divisor found is the GCD. Stop immediately when it is found. Algorithm using a decreasing scan For each number π‘˜ from min(π‘š,𝑛) down to 1 : If π‘˜ divides both π‘š and 𝑛, report π‘˜ as the GCD and stop. There is no need to store or search for further common divisors. Example: Find 𝐠𝐜𝐝(𝟏𝟐,πŸπŸ–) Begin at: min(12, 18)=12 Example: Find 𝐠𝐜𝐝(𝟏𝟐,πŸπŸ–) Begin at: min(12, 18)=12 Candidate k | Does it divide both numbers? | Action 12 | No: it does not divide 18 | Continue 11 | No | Continue 10 | No | Continue 9 | No: it does not divide 12 | Continue 8 | No | Continue 7 | No | Continue 6 | Yes | Report 6 and stop Thus: gcd(12,18)=6 Why is the first successful candidate the greatest? We have already checked every larger possible candidate and rejected it. Therefore, no greater common divisor exists.

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.