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