Attempting to optimize a multiply

Torbjorn Granlund tege at
Wed Feb 23 16:11:43 CET 2005

Karl Hasselström <kha at> writes:

  On 2005-02-18 22:40:30 +0100, Torbjorn Granlund wrote:
  > "Richard Cavell" <richardcavell at> writes:
  >   mpz_mul (c, a, b);
  >   mpz_setbit(a, 25);    // I know categorically that bit 25 is
  >                            clear before this line.
  >   mpz_mul (d, a b);
  >   mpz_mul (c, a, b);
  >   mpz_mul_2exp (b, b, 25);
  >   mpz_add (d, c, b);
  > With the syntax error fixed, the two code versions don't compute the
  > same function. You might need to redo your maths.
  I think you're missing something:
    * In the first case, c = a*b and d = (a + 2^25)*b = a*b + b*2^25
    * In the second case, c = a*b and d = c + b*2^25 = a*b + b*2^25
  (Using only the original values of a and b.)
Yes, I need to redo *my* maths.  :-/

I cannot explain why the variant with less multiplication runs
slower.  It surely would be faster, with large enough operands.

But if your operands are just a few limbs, the computation will
be dominated by function call and bookkeeping overhead.

I am willing to take a further look into this, if I get
more information, and a small test program that I can run.


More information about the gmp-discuss mailing list