#include <NTL/ZZ_pX.h>
#include <flint/fmpz.h>
#include <flint/fmpz_mod_poly.h>
#include <cstdio>

NTL_CLIENT

struct FlintZZ {
   fmpz_t value;

   explicit
   FlintZZ(const ZZ& a)
   {
      long n = NumBits(a);
   
      fmpz_init(value);
   
      for (long i = 0; i < n; i++)
         if (bit(a, i)) fmpz_setbit(value, i);
   
      if (a < 0)
         fmpz_neg(value, value);

   }

   ~FlintZZ() { fmpz_clear(value); }

};

struct FlintModulus {
   fmpz_mod_ctx_t value;

   explicit FlintModulus(const ZZ& p)
   {
      FlintZZ f_p(p);
      fmpz_mod_ctx_init(value, f_p.value);
   }

   ~FlintModulus()
   {
      fmpz_mod_ctx_clear(value);
   }
};



struct FlintZZ_pX {
   fmpz_mod_poly_t value;
   const FlintModulus& mod;

   FlintZZ_pX(const ZZ_pX& a, const FlintModulus& _mod) : mod(_mod)
   {
      long da = deg(a);
      fmpz_mod_poly_init2(value, da+1, mod.value);

      for (long i = 0; i <= da; i++) {
         FlintZZ f_c(rep(a[i]));
         fmpz_mod_poly_set_coeff_fmpz(value, i, f_c.value, mod.value);
      }
   }

   explicit
   FlintZZ_pX(const FlintModulus& _mod) : mod(_mod)
   {
      fmpz_mod_poly_init(value, mod.value);
   }

   ~FlintZZ_pX() { fmpz_mod_poly_clear(value, mod.value); }
};

int main()
{
   setbuf(stdout, NULL);

   for (long l = 256; l <= 16384; l *= 2) {
      for (long idx = 0; idx < 13; idx ++) {
         long n  = 256*(1L << idx/2);
         if (idx & 1) n += n/2;

           SetSeed((ZZ(l) << 64) + ZZ(n));

	   ZZ p;

	   GenPrime(p, l);
	   ZZ_p::init(p);


	   ZZ_pX a, b, c;

	   random(a, n);
	   random(b, n);

	   long da = deg(a);
	   long db = deg(b);

	   double t;

	   GCD(c, a, b); 

	   long iter = 1;
	   do {
	      t = GetTime();
	      for (long i = 0; i < iter; i++) GCD(c, a, b); 
	      t = GetTime() - t;
	      iter *= 2;
	   } while (t < 3);
	   iter /= 2;

	   t = GetTime();
	   for (long i = 0; i < iter; i++) GCD(c, a, b); 
	   t = GetTime()-t;
	   double NTLTime = t;

           FlintModulus mod(ZZ_p::modulus());

	   FlintZZ_pX f_a(a,mod), f_b(b,mod), f_c(c,mod);


	   fmpz_mod_poly_gcd(f_c.value, f_a.value, f_b.value, mod.value);
	   t = GetTime();
	   for (long i = 0; i < iter; i++) 
              fmpz_mod_poly_gcd(f_c.value, f_a.value, f_b.value, mod.value);
	   t = GetTime()-t;
	   double FlintTime = t;

           printf("%8.2f", FlintTime/NTLTime);
      }

      printf("\n");
   }
}


