﻿

# gcd.py

Nov 24th, 2020
569
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import math
2.
3. def my_gcd(a, b, verbose=False):
4.     if a < b:
5.         a, b = b, a
6.     #initialization m -> μ, l = λ, m_1 means μ₋₁ (\u03BC\u208b\u2081)
7.     #i = 0
8.     r_1 = a
9.     r0 = b
10.     l_1 = 1
11.     m_1 = 0
12.     l0 = 0
13.     m0 = 1
14.     #computation
15.     while(a * l0 + b * m0 == r0):
16.         q = r_1 // r0
17.         if(verbose):
18.             print(f'r_1 = {r_1}, r0 = {r0}')
19.             print(f'l_1 = {l_1}, l0 = {l0}')
20.             print(f'm_1 = {m_1}, m0 = {m0}')
21.             print(f'q = {q}\n----------')
22.         l_tmp = l0
23.         l0 = l_1 - q * l0
24.         l_1 = l_tmp
25.         m_tmp = m0
26.         m0 = m_1 - q * m0
27.         m_1 = m_tmp
28.         r_tmp = r0
29.         r0 = r_1 % r0
30.         if r0 == 0:
31.             return (l_1, m_1, a * l_1 + b * m_1)
32.         r_1 = r_tmp
33.
34. a = int(input('a = '), 10)
35. b = int(input('b = '), 10)
36. v = input('verbose? y/N: ')
37. verbose = False
38. if v == 'y':
39.     verbose = True
40. l, m, gcd = my_gcd(a, b, verbose)
41. real_gcd = math.gcd(a, b)
42. print(f'λ = {l}, μ = {m}, gcd({a}, {b}) = {gcd}, real gcd is {real_gcd}')
RAW Paste Data