Karim Belabas on Tue, 09 Sep 2014 21:04:31 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Specialize bivariate FpXY (C library)


* Dan Nichols [2014-09-09 19:43]:
> Given an FpXY f(x,y) with main variable x and secondary variable y, I want
> to get the specialization f(r,y) for some r in Fp. It seems like the
> function I should use is:
> 
>    GEN FpXY_evaly(GEN Q, GEN y, GEN p, long vy)
[...]

Yes.

> When I try to call this function, the return value is always 1. For
> example, the following code

> 
>    #include "stdio.h"
>    #include <pari/pari.h>
> 
>    int main()
>    {
>         pari_init( 400000000, 0 );
> 
>         int y = fetch_user_var( "y" );
>         GEN p = utoi( 7 );
> 
>         GEN f = gp_read_str( "x^2 + y^2 + x*y + 1" );
>         pari_printf( "f(x,y) = %Ps\n", f );
>         printf( "gvar( f ) = %li\n", gvar( f ) );
> 
>         GEN fx0 = FpXY_evalx( f, gen_0, p );
>         pari_printf( "f(x,0) = %Ps\n", fx0 );
> 
>         GEN f0y = FpXY_evaly( f, gen_0, p, y );
>         pari_printf( "f(0,y) = %Ps\n", f0y );
> 
>    }

Your code is correct. There is a bug in FpXY_evaly when evaluating at 0
(and the degree is not 1).

I just pushed a fix to 'master' (commit 5f7a0ee9)

> Produces this output:
> 
>    f(x,y) = x^2 + y*x + (y^2 + 1)
>    gvar( f ) = 0
>    f(x,0) = x^2 + 1
>    f(0,y) = 1
> 
> 
> The last line should be y^2 + 1. Am I using the function correctly?

Yes. Please update from master :-)

> Alternatively, I know I could use the functions gsubst or poleval and then
> reduce mod p, but wouldn't that be slower? p may be very large and f
> may have high degree.

Possibly much slower, due to intermediate expression swell.
Somewhat analogous to the (simplest) example:
  setrand(1); b = 100000;
  y = random(1<<b);
  x = random(1<<b) % y;
  n = 100;

  Mod(x,y)^n; \\ 120ms
  x^n % y;    \\ 4,709ms


Cheers,

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