Torbjorn Granlund tg at
Thu Apr 22 07:36:16 CEST 2010

nisse at (Niels Möller) writes:

  I've now pushed in some new Jacobi code.

  mpn_jacobi_lehmer: I think this is fairly solid, but with some code
  * div1 and div2 identical to those in hgcd2.c,
These are typically inlined, aren't they?  Then the only problem is
source code duplication.  (A comment in both places about where the
other copy lives is then proably a good idea.)

  * mpn_hgcd2_jacobi almost the same as mpn_hgcd2 (but for performance
    this makes some sense. Benchmarking of jacobi vs gcd in the Lehmer
    range would be of some interest).
Cannot speed already do that for us?

  * mpn_jacobi_subdiv_step almost identical to mpn_gcd_subdiv_step and
    mpn_gcdext_subdiv_step. Since these are not performance critical, they
    should most likely be unified. There's also code in hgcd.c:hgcd_step
    which does something very similar.

  * The basecase function mpn_jacobi_2 is longer and more complicated than
    I like. Maybe it can be simplified to eliminate some of the cases.
Is the JACOBI_BASE_METHOD stuff still relevant?

  mpz_jacobi: The new code currently #if:ed out, it probably handles
  jacobi of sizes n/1 and 1/n less efficiently than the old code.
Oh, so the new code is never used from mpz, currently?

  I think it makes sense to do some cleanup and polishing on this code
  before integrating the subquadratic jacobi variant.
  To try the new code, enable it in mpz/jacobi.c, and also enable the extended
  testing (check_large_quotients) in tests/mpz/t-jac.c.
Are here any tests of the new code now, at the mpn level?


More information about the gmp-devel mailing list