# mpz_powm memory usage vs speed

**Jason Moxham
**
J.L.Moxham@maths.soton.ac.uk

*Sat, 16 Nov 2002 13:15:28 +0000*

On Saturday 16 Nov 2002 11:34 am, Torbjorn Granlund wrote:
>* I needed to run a Miller-Rabin test for a number of about 150000
*>* bits. That main computation for that is in mpz_powm with
*>* exponent and mod argument both 150000 bits.
*>*
*>* For this computation, mpz_powm allocates more than 70 MB of
*>* temporary memory. This memory is used for a table of 2048
*>* precomputed powers of my base.
*>*
*>* The actual exponentiation then takes (at least) 12 bits from the
*>* exponent per iteration, indexing the precomputed table for the
*>* right value to multiply into the result. And then it performs 12
*>* squarings.
*>*
*>* My question is:
*>*
*>* How was the table size vs execution speed determined for this
*>* code? If I understand correctly, for every extra bit we take
*>* from the exponent per iteration, the table allocation doubles.
*>* But once we take more than a few bits per iteration, the
*>* dominating work will be squarings.
*>*
*>* By my reckoning, going from 11 bits to 12 bits saves about 1% of
*>* the execution time, while it needs 36 MB extra space (for this
*>* particular computation).
*>*
*>* Time savings table (assuming a squaring cost 2/3 of a full
*>* multiplication):
*>*
*>* 1=3D>2 0% (only half of bits are set)
*>* 2=3D>3 16%
*>* 3=3D>4 9%
*>* 4=3D>5 6%
*>* 5=3D>6 4%
*>* 6=3D>7 3%
*>* 7=3D>8 2%
*>* 8=3D>9 2%
*>*
*>* Is my analysis correct? If it is, I'd suggest that we change
*>* this code to never take more than, say, 9 bits from the exponent.
*
One way to save a bit a space it to only store the precomputed powers tha=
t are=20
actually used in the exponent , using random 150000 bit exponents and tak=
ing=20
12 bits at a time I can get 2.43% memory saving on average.
Who is to say that 70Mb is a lot of memory ? , it only costs =A34 today.
Perhaps a configure switch ? to restrict those algorithms that can use a =
lot=20
of memory to get a bit of extra speed