def shortgcd2(f,g):
  delta,f,g = 1,ZZ(f),ZZ(g)
  assert f&1
  m = 4+3*max(f.nbits(),g.nbits())
  for loop in range(m):
    if delta>0 and g&1: delta,f,g = -delta,g,-f
    delta,g = 1+delta,(g+(g&1)*f)//2
  return abs(f)

tests = ['shortgcd2']
coverage = {t:0 for t in tests}

for loop in range(300000):
  bits1 = randrange(300)
  bits2 = randrange(300)
  d = randrange(2**bits1)
  if not d&1: continue
  f = d*randrange(2**bits2)
  if randrange(2): f = -f
  if not f&1: continue
  g = d*randrange(2**bits2)
  if randrange(2): g = -g
  assert shortgcd2(f,g) == gcd(f,g)
  coverage['shortgcd2'] += 1

for t in tests:
  print coverage[t],t