Torbjorn Granlund <t...@gmplib.org> writes:
> I realise that "Use a small table to get starting value" might not be
> easy to implement for root since one might need k tables. Other
> possibilities would be:
I think we discussed some months ago. IIRC, to get a starting value for
a^{1/k}, it should work fine to use a table indexed by low bits of a and
*low bits only* of k.
I think the underlying reason is that
\phi(2^m) = 2^{m-1},
hence
a^n (mod 2^m) = a^{n mod 2^{m-1}} (mod 2^m)
My implementation constructs a 4-bit starting value as
r0 = 1 + (((n << 2) & ((a0 << 1) ^ (a0 << 2))) & 8);
(here, a0 is the low input limb, r0 is the low output limb, and the
iteration computes a^{1/n-1} mod a power of two.
We should be able to get a 8-bit starting value using a table lookup on
at most 13 bits (18 KByte). But maybe it's not worth the effort; a
single iteration getting from 4 bits to 8 shouldn't be terribly
expensive.
BTW, for large n one ought to use n mod the right power of 2 for the
powering in the first few iterations, to avoid doing lots of useless
work in powering.
> (2) iterate single limb code before entering the mpn loop.
One should definitely have an initial single-limb loop. Similar to how
it's doen with binvert and binvert_limb.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
http://gmplib.org/mailman/listinfo/gmp-devel
