Jacobi/Legendre/Kronecker

[Niels Möller]

Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:

> I'm glad you asked (on the AMD processor):
>
> frite% gcc -I$GMP/include -O2 -g e.c $GMP/lib/libgmp.a
> frite% ./a.out
> GMP: header 5.0.5, library 5.0.5
> mpz_jacobi:       408ms
> mpz_legendre:     412ms
> mpz_kronecker_ui: 240ms
> mpz_ui_kronecker: 508ms
>
> frite% gcc -I/tmp/include -O2 -g e.c /tmp/lib/libgmp.a
> frite% ./a.out
> GMP: header 5.1.0, library 5.1.0
> mpz_jacobi:       536ms
> mpz_legendre:     536ms
> mpz_kronecker_ui: 256ms
> mpz_ui_kronecker: 500ms
>
> Apparently we have a noticeable regression...

I don't have the time to investigate carefully right now, but some
comments:

The functions mpz_kronecker_ui and mpz_ui_kronecker have not been
updated in years. They call mpn_jacobi_base to do the main work.
mpn_jacobi_base is implemented in a couple of different ways, one new
and several older. Tuning should select the fastest one, via
JACOBI_BASE_METHOD, with 4 being the new and usually faster code.

mpz_jacobi and mpz_legendre are aliases for the same function. That has
been completely rewritten in 5.1, calling the new mpn_jacobi_n function
for larger operands, and mpn_jacobi_base directly if the smaller operand
fits in a limb. 20% difference for single-limb operands definitely is
disturbing, I don't see what that might come from.

Regards,
/Niels


-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.