Attempting to optimize a multiply
Torbjorn Granlund
tege at swox.com
Wed Feb 23 16:11:43 CET 2005
Karl Hasselström <kha at treskal.com> writes:
On 2005-02-18 22:40:30 +0100, Torbjorn Granlund wrote:
> "Richard Cavell" <richardcavell at mail.com> 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);
[cut]
> 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. :-/
Sorry.
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.
--
Torbjörn
More information about the gmp-discuss
mailing list