Faster table compute in mpn_sec_powm
Bradley Lucier
lucier at math.purdue.edu
Tue Mar 20 22:03:11 UTC 2018
On 03/20/2018 11:02 AM, Torbjörn Granlund wrote:
> francisco delgado <frdelgado at yahoo.com> writes:
>
> For odd values of i
>
> Instead of this
> B^(2j+1) = (B^(j-1))*B
>
> Shouldn't be this?
> B^(2j+1) = (B^j)^2*B
>
> That's at least mathmatically correct, but this is what I meant:
>
> B^(2j) = (B^j)^2 (i.e., even values of i)
> B^(2j+1) = (B^(2j))*B (i.e., odd values of i)
>
> as that implies the algorithm. (For mpn_sec_powm, it will translate to
> doing one mpn_sqr_basecase call for even indices, one mpn_mul_basecase
> for odd.)
>
(I forgot to reply to the list the first time.)
If you're filling the entire table, I don't see how this would be
faster. (E.g., if B=10 and you're calculating the entries of a table
from 1 to 10,000.)
Brad
More information about the gmp-devel
mailing list