Niels Möller nisse at lysator.liu.se
Mon Dec 17 21:07:15 CET 2012

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

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.


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

More information about the gmp-devel mailing list