Re: Jacobi/Legendre/Kronecker
Ciao Niels, ciao Paul! Il Lun, 17 Dicembre 2012 9:07 pm, Niels Möller ha scritto: Zimmermann Paul paul.zimmerm...@loria.fr writes: 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 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 Apparently we have a noticeable regression... I don't have the time to investigate carefully right now, but some comments: I tested some changes and I suggest the attached patch: unconditionally reduce modulo b. Niels, can you check if it makes sense? Paul, can you measure if it reduce the regression? Best regards, m -- http://bodrato.it/papers/diff -r 4b14ab8c899a mpz/jacobi.c --- a/mpz/jacobi.c Mon Dec 17 21:31:54 2012 +0100 +++ b/mpz/jacobi.c Thu Dec 20 09:19:49 2012 +0100 @@ -155,8 +155,7 @@ if (blow == 1) return JACOBI_BIT1_TO_PN (result_bit1); - if (asize 1) - JACOBI_MOD_OR_MODEXACT_1_ODD (result_bit1, alow, asrcp, asize, blow); + JACOBI_MOD_OR_MODEXACT_1_ODD (result_bit1, alow, asrcp, asize, blow); return mpn_jacobi_base (alow, blow, result_bit1); }___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: Jacobi/Legendre/Kronecker
ni...@lysator.liu.se (Niels Möller) writes: Zimmermann Paul paul.zimmerm...@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: I don't think we can draw significant conclusions about Paul's timing program as currently written. I tried removing the mpz_jacobi call from the 1st function, and it made very little difference. Clearly most of the time is spent in malloc and free. Perhaps there is slowdown from 5.0 to 5.1 anyway. Perhaps it is worse, if the memory overhead is subtracted. But I don't think we should block the release for this. Even if the slowdown turns out to be significant, we can fix it later. These tests exercise operands of up to something like 20 bits, which is not really GMP's home turf. -- Torbjörn ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Jacobi/Legendre/Kronecker
Hi, I wonder why there are some ui/si variants for mpz_kronecker, but not for the simpler functions mpz_jacobi and mpz_legendre. Assume one wants to compute the Legendre symbol (A/P) for P an unsigned long (and A too). What is more efficient? 1) use mpz_kronecker_ui, which forces to convert A to unsigned long 2) use mpz_ui_kronecker, which forces to convert P to unsigned long 3) use mpz_legendre, which forces to convert both A and P to unsigned long Paul Zimmermann ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: Jacobi/Legendre/Kronecker
Zimmermann Paul paul.zimmerm...@loria.fr writes: I wonder why there are some ui/si variants for mpz_kronecker, but not for the simpler functions mpz_jacobi and mpz_legendre. Ah, and one other comment. In GMP, mpz_kronecker, mpz_jacobi and mpz_legendre are all different names for the same function, so none is simpler than the other. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: Jacobi/Legendre/Kronecker
Niels, From: ni...@lysator.liu.se (Niels Möller) Date: Mon, 17 Dec 2012 16:53:52 +0100 Zimmermann Paul paul.zimmerm...@loria.fr writes: Assume one wants to compute the Legendre symbol (A/P) for P an unsigned long (and A too). What is more efficient? 1) use mpz_kronecker_ui, which forces to convert A to unsigned long 2) use mpz_ui_kronecker, which forces to convert P to unsigned long 3) use mpz_legendre, which forces to convert both A and P to unsigned long I think all three should end up in mpn_jacobi_base, where most of he time should be spent. unfortunately mpn_jacobi_base is not in the public interface... I haven't thought about the interface issues, I guess public functions with single limb (or unsigned long) inputs would make sense for both jacobi and gcd. agreed. Ah, and one other comment. In GMP, mpz_kronecker, mpz_jacobi and mpz_legendre are all different names for the same function, so none is simpler than the other. this is strange, since from the documentation mpz_jacobi(A,15) should work but mpz_legendre(A,15) should be undefined. If no check is done at all, I do not see why there are 3 different functions. Paul ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: Jacobi/Legendre/Kronecker
Zimmermann Paul paul.zimmerm...@loria.fr writes: by the way, here are some timings on a 2.27Ghz Intel Xeon L5640 with GMP 5.0.5: Note that large parts of the jacobi code is replaced in the imminent 5.1 release. So it might be interesting to benchmark also the latest code. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: Jacobi/Legendre/Kronecker
Niels, Note that large parts of the jacobi code is replaced in the imminent 5.1 release. So it might be interesting to benchmark also the latest code. 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... Paul ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: Jacobi/Legendre/Kronecker
Zimmermann Paul paul.zimmerm...@loria.fr writes: this is strange, since from the documentation mpz_jacobi(A,15) should work but mpz_legendre(A,15) should be undefined. If no check is done at all, I do not see why there are 3 different functions. To me, it would make sense to have only mpz_kronecker, and mention legendre and jacobi in the documentation (at least if we're talking about the mpz functions). That seems to be what pari/gp does. Except if there's some range (but I'm not aware of any) where mpz_legendre could be implemented more efficiently, e.g., via modular exponentiation. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
Re: Jacobi/Legendre/Kronecker
Zimmermann Paul paul.zimmerm...@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. ___ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel
