import random

tests = [
  'truncate0',
  'truncate',
  'sz',
]
coverage = {t:0 for t in tests}

def divstepsx(n,t,delta,f,g):
  assert t >= n and n >= 0
  f,g = f.truncate(t),g.truncate(t)
  kx = f.parent()
  x = kx.gen()
  u,v,q,r = kx(1),kx(0),kx(0),kx(1)

  while n > 0:
    f = f.truncate(t)
    if delta > 0 and g[0] != 0: delta,f,g,u,v,q,r = -delta,g,f,q,r,u,v
    f0,g0 = f[0],g[0]
    delta,g,q,r = 1+delta,(f0*g-g0*f)/x,(f0*q-g0*u)/x,(f0*r-g0*v)/x
    n,t = n-1,t-1
    g = kx(g).truncate(t)

  M2kx = MatrixSpace(kx.fraction_field(),2)
  return delta,f,g,M2kx((u,v,q,r))

def jumpdivstepsx(n,t,delta,f,g):
  assert t >= n and n >= 0
  kx = f.truncate(t).parent()

  if n <= 1: return divstepsx(n,t,delta,f,g)

  # j = n//2
  # "j can be taken anywhere between 1 and n-1"
  j = randrange(1,n)

  delta,f1,g1,P1 = jumpdivstepsx(j,j,delta,f,g)
  f,g = P1*vector((f,g))
  f,g = kx(f).truncate(t-j),kx(g).truncate(t-j)

  delta,f2,g2,P2 = jumpdivstepsx(n-j,n-j,delta,f,g)
  f,g = P2*vector((f,g))
  f,g = kx(f).truncate(t-n+1),kx(g).truncate(t-n)

  return delta,f,g,P2*P1

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))

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(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)))

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

  for n in range(20):
    deltan[n] = delta
    fn[n] = f
    gn[n] = g
    Tn[n] = T(delta,f,g)
    Sn[n] = S(delta,f,g)

    delta,f,g = divstep(delta,f,g)

  M2kx = MatrixSpace(kx.fraction_field(),2)

  for n in range(20):
    t = randrange(40)
    if n <= t:
      delta,f,g,P = divstepsx(n,t,deltan[0],fn[0],gn[0])
      assert delta == deltan[n]
      if n == 0:
        assert f == fn[n].truncate(t)
        coverage['truncate0'] += 1
      else:
        assert f == fn[n].truncate(t-(n-1))
        coverage['truncate'] += 1
      assert g == gn[n].truncate(t-n)
      assert P == M2kx(prod(Tn[i] for i in reversed(range(0,n))))
      assert (delta,f,g,P) == jumpdivstepsx(n,t,deltan[0],fn[0],gn[0])

  delta,f,g = deltan[0],fn[0],gn[0]
  s = 0 if -delta >= 0 else 1
  z = 0 if g(0)==0 else 1
  assert deltan[1] == 1+(1-2*s*z)*delta
  assert s*z in [0,1]
  assert fn[1] == f if s*z == 0 else g
  assert gn[1] == (1-2*s*z)*(f(0)*g-g(0)*f)/x
  coverage['sz'] += 1

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