mini-gmp and mpq

[Marco Bodrato]

Ciao,

Il Mer, 2 Maggio 2018 3:05 pm, Torbjörn Granlund ha scritto:

>On 04/30/2018 04:06 AM, Marco Bodrato wrote:
>> Il Lun, 30 Aprile 2018 4:10 am, Bradley Lucier ha scritto:
>>> The important case is when a=b, but I just realized that the test
>>> can be refined to when the denominator of a is the denominator of b.
>> Interesting observation. But, do you think it's worth replacing

> I am not so sure.  I have no idea how often the denominators will be
> equal out there, but I'd expect that mpz_cmp would terminate in time
> O(1) on average when they are not.

I agree it is not worth for mini-, where we should not add inessential
code, but the idea can be used for the full library

In mpq/mul.c we currently have.

  if (op1 == op2)
    {
      /* No need for any GCDs when squaring. */
      mpz_mul (mpq_numref (prod), mpq_numref (op1), mpq_numref (op1));
      mpz_mul (mpq_denref (prod), mpq_denref (op1), mpq_denref (op1));
      return;
    }
  op1_num_size = ABSIZ(NUM(op1));
  op1_den_size =   SIZ(DEN(op1));
  op2_num_size = ABSIZ(NUM(op2));
  op2_den_size =   SIZ(DEN(op2));

We may write instead.

  op1_den_size =   SIZ(DEN(op1));
  op2_den_size =   SIZ(DEN(op2));
  if (op1_den_size == op2_den_size &&
      (op1 == op2 ||
       !mpn_cmp (DEN(op1)->_mp_d, DEN(op2)->_mp_d, op1_den_size)))
    {
      /* GCDs not needed when the denominators are equal,
         e.g. when squaring. */
      mpz_mul (mpq_numref (prod), mpq_numref (op1), mpq_numref (op2));
      mpz_mul (mpq_denref (prod), mpq_denref (op1), mpq_denref (op1));
      return;
    }
  op1_num_size = ABSIZ(NUM(op1));
  op2_num_size = ABSIZ(NUM(op2));

One may argue also that no GCDs are needed when numerators are equal...
I do not know if those conditions happen very often.

Ĝis,
m

-- 
http://bodrato.it/papers/