mpz_powm memory usage vs speed
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
> 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
> 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=
actually used in the exponent , using random 150000 bit exponents and tak=
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 =
of memory to get a bit of extra speed