Re: Fast substitutions in Pari

[Franck MICHEL <Franck.Michel@univ.u-3mrs.fr>]

>I would do something like this:
>
>  /* h^degpol(P) P(x / h) */
>  rescale(P, h) =
>  { local(G,H, d);
>    d = poldegree(P); H = 1;
>    Pol( vector(d + 1, i, G = H; H = G * h; polcoeff(P, d-(i-1)) * G) );
>  }
>  h = taylor(denominator(phi), t);
>  z = subst(rescale(u, h), x, taylor(numerator(phi), t));
>  z / h^poldegree(u);   \\ not needed in most applications !!!
>
>On my slow PIII (1GHz), I get:
>
>(19:16) gp > taylor(subst(u,x,phi),t); \\ regression as above !!!
>time = 2,400 ms.
>(19:16) gp > subst(u,x,taylor(phi,t)); \\ slow
>time = 1,010 ms.
>
>(19:16) gp > h = taylor(denominator(phi), t);
>time = 0 ms.
>(19:16) gp > z = subst(rescale(u, h), x, taylor(numerator(phi), t));
>time = 10 ms.
>(19:16) gp > z / h^poldegree(u);  \\ fast
>time = 20 ms.
>
>If this operation is really crucial, a better approach could be to multiply
>by Mod(1, p) for some primes = 1 mod 4, not dividing any denominator in
>sight, and reconstruct using Chinese remaindering. But you'll need a priori
>bounds on the heights of the final coefficients.
>
>Hope this helps,
>
>    Karim.


Thank you, this will be very useful.

--
Franck