import random

tests = [
  'degfg',
  'deguvqr',
]
coverage = {t:0 for t in tests}

def divstep(delta,f,g):
  kx = parent(f)
  x = kx.gen()
  if delta>0 and g[0]!=0:
    return 1-delta,g,kx((g[0]*f-f[0]*g)/x)
  return 1+delta,f,kx((f[0]*g-g[0]*f)/x)

def T(delta,f,g):
  kx = parent(f)
  x = kx.gen()
  M2kx = MatrixSpace(kx.fraction_field(),2)
  if delta>0 and g[0]!=0:
    return M2kx((0,1,g[0]/x,-f[0]/x))
  return M2kx((1,0,-g[0]/x,f[0]/x))

def S(delta,f,g):
  kx = parent(f)
  x = kx.gen()
  M2Z = MatrixSpace(ZZ,2)
  if delta>0 and g[0]!=0:
    return M2Z((1,0,1,-1))
  return M2Z((1,0,1,1))

def bezout(R0,R1):
  # sage gcd and xgcd fail to return monic for, e.g., (2*x,0)
  if R0 == 0 and R1 == 0: return 0,0,0
  if R1 == 0:
    return R0/R0.leading_coefficient(),1/R0.leading_coefficient(),0
  if R0 == 0:
    return R1/R1.leading_coefficient(),0,1/R1.leading_coefficient()
  return xgcd(R0,R1)

def sanedeg(f):
  if f == 0: return -Infinity
  return f.degree()

for loop in range(1000):
  q = random.choice([2,3,5,7,11,13,17,19,23,29])
  k = GF(q)
  kx.<x> = k[]
  coeffs1 = randrange(20)
  coeffs2 = randrange(1,100)
  coeffs3 = randrange(coeffs2)
  h = kx(sum(k.random_element()*x^i for i in range(coeffs1)))
  if h[0] == 0: continue
  R0 = h*kx(sum(k.random_element()*x^i for i in range(coeffs2)))
  if R0[0] == 0: continue
  R1 = h*kx(sum(k.random_element()*x^i for i in range(coeffs3)))
  
  M2kx = MatrixSpace(kx.fraction_field(),2)

  if R0.degree() > 0:
    if R0.degree() > R1.degree():
      G,U,V = bezout(R0,R1)
      assert G == U*R0+V*R1

      d = R0.degree()
      delta = 1
      f = kx(x^d*R0(1/x))
      g = kx(x^(d-1)*R1(1/x))

      deltan = {}
      fn = {}
      gn = {}
      Tn = {}
      Sn = {}

      P = M2kx(1)

      for n in range(2*d+10):
        deltan[n] = delta
        fn[n] = f
        gn[n] = g
        Tn[n] = T(delta,f,g)
        Sn[n] = S(delta,f,g)

        assert 2*sanedeg(fn[n]) <= 2*d-1-n+deltan[n]
        assert 2*sanedeg(gn[n]) <= 2*d-1-n-deltan[n]
        coverage['degfg'] += 1

        (u,v),(q,r) = P
        kx(x^n*(u*r-v*q))
        if n >= 1: kx(x^(n-1)*u)
        kx(x^(n-1)*v)
        kx(x^n*q)
        kx(x^n*r)

        if n >= 1: assert 2*sanedeg(kx(x^(n-1)*u)) <= n-3+deltan[n]
        assert 2*sanedeg(kx(x^(n-1)*v)) <= n-1+deltan[n]
        assert 2*sanedeg(kx(x^n*q)) <= n-1-deltan[n]
        assert 2*sanedeg(kx(x^n*r)) <= n+1-deltan[n]
        coverage['deguvqr'] += 1

        P = Tn[n]*P
        delta,f,g = divstep(delta,f,g)

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