me30

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