☰ Contents · Computing

Local and global variables, the GCD (EKUB) function

Lessons 49–50 · 2 lessons · M. R. Fayziyeva, D. M. Sayfurov, N. S. Xaytullayeva. Informatics and Information Technologies, Grade 9. “Nashriyot uyi Tasvir”, Tashkent, 2020
50

Practical lesson: functions and Euclid’s algorithm

Textbook: pp. 98–99
GoalIn the practical lesson, finds the greatest common divisor (EKUB) of two numbers with the Euclidean algorithm, writes it as a function, and uses it to reduce a fraction and to find the least common multiple (EKUK).
New words
EKUB: the greatest common divisor of two numbers (gcd) · EKUBEuclidean algorithm: repeat (a, b) → (b, a % b) until b is 0 · Yevklid algoritmiEKUK: the least common multiple, which equals a * b // EKUB(a, b) · EKUKreducing a fraction: dividing numerator and denominator by their EKUB · kasrni qisqartirish
Explanation

Finding the greatest common divisor (EKUB) of two numbers by splitting them into prime factors is not handy for a computer; the Euclidean algorithm is short and fast. Its idea: divide a by b and take the remainder, then take (b, remainder) in place of (a, b); repeat until b equals zero, and at the end a is the EKUB. For example (84, 36) → (36, 12) → (12, 0), so EKUB = 12. In Python this is a loop of two lines: while b != 0: ⏎     a, b = b, a % b – both the swapping and the remainder are done in one line. Once the EKUB is found, reducing a fraction (dividing both parts by the EKUB) and finding EKUK = a * b // EKUB is very easy. The algorithm always stops, because the remainder gets smaller each time and finally reaches zero.

Worked examples
An EKUB function: def ekub(a, b): ⏎     while b != 0: ⏎         a, b = b, a % b ⏎     return a ⏎ print(ekub(84, 36)) ekub(84, 36) = 12.
Reducing a fraction: def ekub(a, b): ⏎     while b != 0: ⏎         a, b = b, a % b ⏎     return a ⏎ g = ekub(18, 24) ⏎ print(18 // g, 24 // g) the fraction 18/24 becomes 3/4 (EKUB = 6). EKUK: def ekub(a, b): ⏎     while b != 0: ⏎         a, b = b, a % b ⏎     return a ⏎ print(12 * 18 // ekub(12, 18)) the EKUK of 12 and 18 is 36.
Class activity

“Remainder chain”: pairs choose two numbers, write the chain (a, b) → (b, a % b) in the notebook and find the EKUB; then they check it in a program.

Practice
1
Find the EKUB of 48 and 18 (with the Euclidean algorithm).
2
Starting from (84, 36), write the chain: show the pair (a, b) at each step.
3
Reducing a fraction: find the numerator and the denominator of the fraction 45/60 reduced.
4
Why does the Euclidean algorithm always stop?