import random

tests = [
  'T',
  'S',
  'decomposition',
  'scaleddecomposition',
  'rho',
  'rhodecomposition',
  'u1',
  'uk',
]
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 scaleddivstep(delta,f,g):
  kx = parent(f)
  x = kx.gen()
  if delta>0 and g[0]!=0:
    return 1-delta,g,kx((f-(f[0]/g[0])*g)/x)
  return 1+delta,f,kx((g-(g[0]/f[0])*f)/x)

def rhostep(delta,rho):
  kx = parent(f)
  x = kx.gen()
  if delta>0 and rho(0)!=0:
    return 1-delta,(1/rho-1/rho(0))/x
  return 1+delta,(rho-rho(0))/x

def condswap(delta,f,g):
  if delta>0 and g[0]!=0: return -delta,g,f
  return delta,f,g

def rhocondinv(delta,rho):
  if delta>0 and rho(0)!=0:
    return -delta,1/rho
  return delta,rho

def elimination(delta,f,g):
  kx = parent(f)
  x = kx.gen()
  return 1+delta,f,kx((f[0]*g-g[0]*f)/x)

def rhoelimination(delta,rho):
  kx = parent(rho)
  x = kx.gen()
  return 1+delta,(rho-rho(0))/x

def scaledelimination(delta,f,g):
  kx = parent(f)
  x = kx.gen()
  return 1+delta,f,kx((g-(g[0]/f[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))

for loop in range(20000):
  q = random.choice([2,3,5,7,11,13,17,19,23,29])
  k = GF(q)
  kx.<x> = k[]
  coeffs1 = randrange(100)
  coeffs2 = randrange(100)
  delta = randrange(-9,10)
  h = kx(sum(k.random_element()*x^i for i in range(coeffs1)))
  if h[0] == 0: continue
  f = h*kx(sum(k.random_element()*x^i for i in range(coeffs2)))
  if f[0] == 0: continue
  g = h*kx(sum(k.random_element()*x^i for i in range(coeffs2)))

  delta1,f1,g1 = divstep(delta,f,g)

  assert vector((f1,g1)) == T(delta,f,g)*vector((f,g))
  coverage['T'] += 1

  assert vector((1,delta1)) == S(delta,f,g)*vector((1,delta))
  coverage['S'] += 1

  deltac,fc,gc = condswap(delta,f,g)
  assert elimination(deltac,fc,gc) == (delta1,f1,g1)
  coverage['decomposition'] += 1

  delta1s,f1s,g1s = scaleddivstep(delta,f,g)
  assert delta1s == delta1
  assert scaledelimination(deltac,fc,gc) == (delta1s,f1s,g1s)
  coverage['scaleddecomposition'] += 1

  rho = g/f
  delta1r,rho1 = rhostep(delta,rho)
  assert delta1r == delta1
  assert rho1 == g1s/f1s
  coverage['rho'] += 1

  deltacr,rhoc = rhocondinv(delta,rho)
  assert rhoelimination(deltacr,rhoc) == (delta1r,rho1)
  coverage['rhodecomposition'] += 1

  u = kx(sum(k.random_element()*x^i for i in range(30)))
  if u[0] != 0:
    u /= u[0]
    assert divstep(delta,u*f,u*g) == (delta1,u*f1,u*g1)
    coverage['u1'] += 1

  u = k.random_element()
  if u != 0:
    if delta>0 and g[0]!=0:
      assert divstep(delta,u*f,g) == (delta1,f1,u*g1)
    else:
      assert divstep(delta,u*f,g) == (delta1,u*f1,u*g1)
    if delta>0 and g[0]!=0:
      assert divstep(delta,f,u*g) == (delta1,u*f1,u*g1)
    else:
      assert divstep(delta,f,u*g) == (delta1,f1,u*g1)
    coverage['uk'] += 1
  
for t in tests:
  print coverage[t],t