In need of suggestion on how to reduce the number of iterations it takes to find

Question

In need of suggestion on how to reduce the number of iterations it takes to find the GCD for question 2b?

Question2 (b) Make changes to the algorithm given above: Figure Q2 shows Euclid's algorithm which finds the Greatest Common Denominator (GCD) For further details about Euclid's algorithm and mathematical considerations, you may Add a counter in the loop. The counter will count the number of iterations algorithm takes to output the ged. a program using the Reduce the number of iterations Reduce the number of iterations it takes to find the ged. For this change, you must make at least THREE (3) postings to a discussion group to engage efficiency of the algorithm. members in the group to arrive at the answer to improve the Your posting could be a suggestion, a caution, an elaboration, an agreement ete. Each positing should be accompanied with reasons, e.g., how your suggestion contribute to the solution or how someone's suggestion is erroneous, incomplete, helps etc. ( Study the discussion to arrive at your version of an improved flowchart for the required changes As usual, all solutions must be your personal effort, from your personal experimentation and conclusions. Submit your flowchart and the Python program (in text) that Flowgorithm generates ii) Cite the discussion you have engaged in, to prove your contribution to the solution. You should provide screenshots of your best THREE (3) (10 marks) (c List THREE (3) must-have features of a problem for group discussion. Justify postings Figure Q2 your answers using the online discussion. Propose discussion and problem solving for next semester a new problem that you think would be good to generate group (a) Using Figure Q2 employ Flowgorithm software to generate a program in Python and another in a programming language of your choice. (12 marks) Run both programs and verify whether they produce the same results, Use the screen capture of the traces to prove your result. You should have tested the programs sufficiently. Write comments on the program in another language to demonstrate your understanding of the semantic of the program and of Euclid's algorithm. (8 marks)

Explanation / Answer

Suppose we take 15 and 100 so if you keep subtracting 15 from 100 for 6 times you would reach 10 which would for obvious reasons be remainder of 100/15 this gives us a inspiration that using remainder might be a better approach. This is why to modify Euclidean algorithm we use % instead of-

To reduce the number of iterations a more efficient algorithm would be to replace the larger of the two numbers by its remainder when divided by the smaller of the two (stop when reaching a zero remainder and the other number is the GCD). Example:-

Using the unmodified algorithm

GCD =3

Using Modified Algorithm

(k=k%m when k is greater and m=m%k when m is greater)

GCD =3

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.