Torbjorn Granlund
04 Aug 2003 18:36:44 +0200 (Larry Lambe) writes:

  Consider this segment from "aors.c" to which I've added some pointers:

    if (! MPZ_EQUAL_1_P (gcd))
        mpz_t t;

        mpz_divexact_gcd (tmp1, &(op2->_mp_den), gcd);
        mpz_mul (tmp1, &(op1->_mp_num), tmp1);

    |-->mpz_divexact_gcd (tmp2, &(op1->_mp_den), gcd);
    |   mpz_mul (tmp2, &(op2->_mp_num), tmp2);
    |   MPZ_TMP_INIT (t, MAX (ABS (tmp1->_mp_size), ABS (tmp2->_mp_size)) + 1);
    |   (*fun) (t, tmp1, tmp2);
    |-->mpz_divexact_gcd (tmp2, &(op1->_mp_den), gcd);

  It seems that it would save some time not to recompute denom(op1)/gcd twice
  by putting its value the first time around in another variable and using
  that when needed -- or am I missing something (always a tricky business to
  try to read someone elses code!)?

Yes, it seems we could apply some Common subexpression
elimination here.  Also, there are two redundant ABS invocations.
This code clearly isn't as good as it should be.

If somebody wants to work on this, please consider these issues:
 1. Keep temp allocation down.
 2. Try to avoid mpz_mul(a,b,a) or mpz_mul(a,a,b) since that
    causes temp allocation ond/or copying in mpz_mul.
 3. The gcd variable is usually small.  For random input it is 1
    with high probability.  It fits in a single limb almost
    always.  Consider using mpn_preinv_divrem_1 for that case.
    (Might not be worth the complexity.)