marc.glisse at normalesup.org
Thu Feb 19 21:46:09 CET 2009
On Thu, 19 Feb 2009, Digital Parasite wrote:
> If I need to square a value many times in a loop, is using mpz_mul the
> fastest way in GMP to achieve this or is there another function that
> is better specifically for squaring?
mpz_mul already checks whether the 2 arguments are the same and uses a
special code in this case, so mpz_mul seems appropriate indeed.
> For example, some sample code below:
> // r = 6
> // q = 350000
> // p = 2^q so in this case 350000 bits
> for (j=1; j <= mpz_get_ui(q); j++)
Not crucial here, but it is better to avoid the function call here and do
it once before starting the loop.
> // t = r^2 - 2
> mpz_mul(t, r, r);
> mpz_sub_ui(t, t, 2);
> // r = t | p
> mpz_mod(r, t, p);
Note that there is a special version of mpz_mod for powers of 2.
I think the biggest issue here is to prevent gmp from computing more than
q bits in the product. Although it is doable, I don't know of a gmp
function that does this. Someone more familiar with the code may know
More information about the gmp-discuss