Re: [arndt@jjj.de: Re: bugfix for charpoly with finite fields]

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Karim Belabas [2008-08-01 02:42]:
>   I received an interesting test-case from Joerg Arndt (simplified version attached).
> 
>   "The used function gauss_poly2() calls only pari/gp internals, else it
>    does arithmetic with binary polynomials no more."
> 
> Some timings:
> 
>   ver 2.3.4:  11.9 s. / 11.8 s [GMP]
> 
>   ver 2.4.2:   360 s. / 356 s. [ GMP ]
> 
> \\ Anticipating a little bit on the semi-happy ending (the solution is awkward)
>   current svn: 12.5s /  11.9s [ GMP ]
> 
> A simpler example:
> {
>   a = x^1771 + x^82 + x^8 + x;
>   b = x^1449 + x^1448 + x^1446 + x^1412 + x^1411 + x^1408 + x^1406 + x^1403 + x^1366 + x^1362 + x^1360 + x^1317 + x^537 + x^500 + x^496 + x^494 + x^460 + x^459 + x^456 + x^454 + x^451 + x^411 + x^410 + x^408;
>   T = x^1861 + 1;
>   z = Mod(Mod(1,2), Mod(1,2)*T);
> }
> 
>   (z * a) * (z * b)
> 
> is about 50 times slower in 2.4.2 (and onwards) than in 2.3.*
[...]
> Timings do improve: 539ms --> 16ms in 2.4.2, vs 12ms for the original
> code in 2.3.4 (stable remains a little more efficient because Flx_rem
> does not use sparse representation but Newton/FFT-based arithmetic in
> this example; conversions are negligible)

A short addendum. The recent inefficiency discussed in my preceding mail only
concerned Euclidean division of *sparse* polynomials. For t_POLMODs with dense
moduli, svn is about as fast as stable, and much faster when we recognize a
"simple base ring".

rnd() = random(2^random(31)*2-1)*(-1)^random(2)
randpol(n) = 'x^n+Pol(concat(rnd(),vector(n-1,i,if(random(2),rnd()))))

test(N) =
{
  T = randpol(N+1)*Mod(1,2);
  a = Mod(randpol(N)*Mod(1,2), T);
  b = Mod(randpol(N)*Mod(1,2), T);
  for(i=1, 10^5/N, a * b);
}

svn:     (15:28) gp > test(10)
         time = 116 ms.
         (15:28) gp > test(100)
         time = 212 ms.
         (15:28) gp > test(1000)
         time = 300 ms.

stable:  (15:27) gp > test(10)
         time = 244 ms.
         (15:27) gp > test(100)
         time = 1,320 ms.
         (15:27) gp > test(1000)
         time = 6,977 ms.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`