Euclids Algorithm iş a veri good cha.pptx

İti

1. Euclid’s Algorithm Euclid’s Algorithm is an efficient process used to determine the highest common factor of two whole numbers. The step by step process is documented in Euclid’s “Elements”, written around 300BC. The algorithm is still in use today!

2. Euclid’s Algorithm Start with two lengths ...

3. Euclid’s Algorithm We want to divide both lengths into smaller pieces of equal length, and leave no remainder.

4. Euclid’s Algorithm The difference between their lengths will also be divisible by this common length.

5. Euclid’s Algorithm The difference between their lengths will also be divisible by this common length.

6. Euclid’s Algorithm The difference between their lengths will also be divisible by this common length.

7. Euclid’s Algorithm The revised problem is simpler. Now start the process again ...

8. Euclid’s Algorithm The difference between the lengths will also be divisible by the same quantity.

9. Euclid’s Algorithm The difference is now zero.

10. Euclid’s Algorithm This is the largest length that fits into both the original lengths.

11. Euclid’s Algorithm This is the largest length that fits into both the original lengths.

12. Euclid’s Algorithm Let’s try another example ...

13. Euclid’s Algorithm Start with two lengths ...

14. Euclid’s Algorithm In this example, we can duplicate the shorter length first.

15. Euclid’s Algorithm In this example, we can duplicate the shorter length first.

16. Euclid’s Algorithm Now check the difference (remainder)

17. Euclid’s Algorithm Now check the difference (remainder)

18. Euclid’s Algorithm Repeat the process.

19. Euclid’s Algorithm Repeat the process.

20. Euclid’s Algorithm Repeat the process.

21. Euclid’s Algorithm Find the difference.

22. Euclid’s Algorithm Find the difference.

23. Euclid’s Algorithm Find the difference.

24. Euclid’s Algorithm No difference ... algorithm or process stops.

25. Euclid’s Algorithm Now try with numbers. 200 72

26. Euclid’s Algorithm How many times does 72 divide 200? 72 200 2 x

27. Euclid’s Algorithm The remainder has the same highest common factor as 200 and 72. 72 200 2 x 56

28. Euclid’s Algorithm Repeat the algorithm ... 72 56

29. Euclid’s Algorithm 56 divides 72 just once...with a remainder of 16 72 56 16

30. Euclid’s Algorithm Repeat the algorithm. 56 16

31. Euclid’s Algorithm Repeat the algorithm. 56 16 3 x

32. Euclid’s Algorithm Repeat the algorithm. 56 16 3 x 8

33. Euclid’s Algorithm 8 divides 16 twice ... 16 8 2 x There is no remainder so the algorithm is complete.

34. Euclid’s Algorithm 8 is the highest common factor of 200 and 72. 8 200 72

35. Euclid’s Algorithm 8 is the highest common factor of 200 and 72. 8 200 72