#! /usr/bin/python

import sys
from math import gcd
from random import randint

"""
With main() calling function receive_arguments(): run script giving two integer
numbers, and it will output their gcd written as a linear combination of both of
them.
With main() calling function test(): compute gcd of randomly generated integers,
and compare it with the gcd() function from Python's math module.
"""

def xgcd(a, b):
  if a == 0 and b == 0:
    raise Exception("gcd(0, 0) is not defined!")
  elif a == 0:
    return (abs(b), 0, 1 if  b > 0 else -1 )
  elif b == 0:
    return (abs(a), 1 if a > 0 else -1, 0)
  if a == b: return (abs(a), 1 if a > 0 else -1, 0)

  r0 = None # r_i
  r1 = None # r_{i + 1}
  r2 = None # r_{i + 2}

  q = [] # List of quotients.

  r0_negative = False
  r1_negative = False

  # By default, r0 = a and r1 = b. But we must have r0 > r1, so a swap may be in
  # order... hence this variable.
  r0_r1_swapped = False

  if a < 0:
    r0 = abs(a)
    r0_negative = True
  else:
    r0 = a

  if b < 0:
    r1 = abs(b)
    r1_negative = True
  else:
    r1 = b

  # Now both r0 and r1 are positive.

  if r0 < r1:
    # Swap them...
    aux = r0
    r0 = r1
    r1 = aux

    # ... as well as information about their sign.
    aux = r0_negative
    r0_negative = r1_negative
    r1_negative = aux

    r0_r1_swapped = True

  # Now r0 > r1, with both values positive, and so we can begin the compute the
  # gcd proper...

  cl = None # Low coefficient (i.e., of r0).
  ch = None # High coefficient (i.e., of r1).

  r2 = r0 % r1

  if r2 == 0:
    cl = 0
    ch = 1
  else:
    while r2 != 0:
      q.append(r0 // r1)
      r0 = r1
      r1 = r2
      r2 = r0 % r1

    # r1 now contains gcd(a, b).

    cl = 1
    ch = - q.pop()

    while q:
      cl_orig = cl
      cl = ch
      ch = cl_orig + q.pop() * (- ch)

  # Full gcd computation (including coefficients) finished. gcd is still stored
  # on variable r1. Now we compute the coefficients corresponding to the
  # arguments passed to this function, viz. a and b (we only have the
  # coefficients corresponding to r0 and r1 (cl and ch respectively)).

  if r0_r1_swapped == False:
    # r0 = a and r1 = b -- and hence ca = cl and cb = ch.

    if r0_negative:
      ca = -cl
    else:
      ca = cl

    if r1_negative:
      cb = -ch
    else:
      cb = ch
  else:
    # r0 = b and r1 = a -- and hence ca = ch and cb = cl.

    if r1_negative:
      ca = -ch
    else:
      ca = ch

    if r0_negative:
      cb = -cl
    else:
      cb = cl

  # Sanity check.
  if not r1 == a*ca + b*cb:
    print("Error: %d NOT EQUAL TO %d * %d + %d * %d!" % (r1, a, ca,
                                                         b, cb))

  return (r1, ca, cb)


def test():
  for i in range(10000):
    a = randint(1000, 10000) * [-1, 1][randint(0, 1)]
    b = randint(1000, 10000) * [-1, 1][randint(0, 1)]

    mygcd = xgcd(a, b)[0]
    pgcd = gcd(a, b)

    if mygcd != pgcd:
      print("Error: my gcd(%d, %d) is %d, but Python's is %d!" % (a, b, mygcd,
                                                                  pgcd))
      break

    print("a=%6d, b=%6d, gcd(%6d, %6d) =%4d" % (a, b, a, b, mygcd))


def receive_arguments():
  a = int(sys.argv[1])
  b = int(sys.argv[2])

  gcd, ca, cb = xgcd(a, b)
  print("gcd(%d, %d) = %d = %d * %d + %d * %d" % (a, b, gcd, a,
                                                  ca, b, cb))

def main():
  # receive_arguments()

  test()


if __name__ == '__main__':
  main()