Re: Speed up RgX_mul, RgX_sqr, RgX_divrem over Z, Fp, FpXQ

[Peter Bruin <P.J.Bruin@math.leidenuniv.nl>]

Hi Bill,

One more thing: starting with commit 4a80b98, multiplication of FpX
(which moved from RgX_mul/RgX_sqr to the new functions RgX_mul_FpX/
RgX_sqr_FpX in that commit) removes the special case for Flx that was
introduced in commit b770112.  Was this intentional?  It does make a
noticeable difference, see below.  One way to fix this is as in the
attached patch; alternatively, one could of course try to speed up
FpX_mul/FpX_sqr.

Reusing the setup of an earlier example:

? g = x^11+t^13+3*x^7+(2*(t+1)^8+2*t)^7*x^6+(2*t^8+t^6+2*t)^45*x^3+(t+1)^5*t^4*(2*x+x)+t^12+2;
? f = Mod(g^2+x^4*(t+2)^4-t^12, 5);

Before applying the attached patch:

? r = polresultant(f, f', 'x);
? ##
  ***   last result computed in 1,381 ms.

After:

? r = polresultant(f, f', 'x);
? ##
  ***   last result computed in 781 ms.

Thanks,

Peter

>From 8c6300f27671d375ac30e7c2e017bffdf10d20d8 Mon Sep 17 00:00:00 2001
From: Peter Bruin <P.J.Bruin@math.leidenuniv.nl>
Date: Tue, 29 Aug 2017 12:15:56 +0200
Subject: [PATCH] use Flx functions in RgX_{mul,sqr}_FpX if possible

---
 src/basemath/RgX.c | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

diff --git a/src/basemath/RgX.c b/src/basemath/RgX.c
index ba2330f38..d900de19e 100644
--- a/src/basemath/RgX.c
+++ b/src/basemath/RgX.c
@@ -1574,7 +1574,15 @@ static GEN
 RgX_mul_FpX(GEN x, GEN y, GEN p)
 {
   pari_sp av = avma;
-  GEN r = FpX_mul(RgX_to_FpX(x, p), RgX_to_FpX(y, p), p);
+  GEN r;
+  if (lgefint(p) == 3)
+  {
+    ulong pp = uel(p, 2);
+    r = Flx_to_ZX_inplace(Flx_mul(RgX_to_Flx(x, pp),
+                                  RgX_to_Flx(y, pp), pp));
+  }
+  else
+    r = FpX_mul(RgX_to_FpX(x, p), RgX_to_FpX(y, p), p);
   if (signe(r)==0)
   { avma = av; return zero_FpX_mod(p, varn(x)); }
   return gerepileupto(av, FpX_to_mod(r, p));
@@ -1633,7 +1641,14 @@ static GEN
 RgX_sqr_FpX(GEN x, GEN p)
 {
   pari_sp av = avma;
-  GEN r = FpX_sqr(RgX_to_FpX(x, p), p);
+  GEN r;
+  if (lgefint(p) == 3)
+  {
+    ulong pp = uel(p, 2);
+    r = Flx_to_ZX_inplace(Flx_sqr(RgX_to_Flx(x, pp), pp));
+  }
+  else
+    r = FpX_sqr(RgX_to_FpX(x, p), p);
   if (signe(r)==0)
   { avma = av; return zero_FpX_mod(p, varn(x)); }
   return gerepileupto(av, FpX_to_mod(r, p));
-- 
2.13.5


Peter Bruin <P.J.Bruin@math.leidenuniv.nl> wrote:

> Hi Bill,
>
>> On Wed, Jun 07, 2017 at 09:12:55PM +0200, Bill Allombert wrote:
>>> Maybe it would be better to have functions RgX_mul_i etc.
>>> that does what RgX_mul is doing now, and change RgX_mul
>>> to do what you suggest.
>>
>> I implemented that. Furthermore I added a framework that allows
>> RgX_mul/RgX_sqr to add support for most types.
>>
>> Please check commit dcf58b3. 
>
> This solution looks very nice to me!
>
> Peter