GMP 4.4 remaining tasks
Niels Möller
nisse at lysator.liu.se
Mon Dec 7 22:22:38 CET 2009
Torbjorn Granlund <tg at gmplib.org> writes:
> The wrapping multiplication for mpn_invert and mpn_binvert are of the
> kind 2n x n. Using mulmod_bnm1 for that is not that great.
But not so bad, either, is it?
The multiplication is 2n (input) x n (previous iterate). Product is of
size 3n, where n limbs at the most significant end (for mpn_invert) are
known a priori to be all ones (or, since we don't quite converge from
below due to truncation at this step in the algorithm, they can be
either B^n or B^n-1, so one needs an extra limb to figure out which one
it is). Hence one can use mulmod_bnm1 with rn = 2n + 1, an = 2n, bn = n.
(Also, we don't care about the least significant n limbs of the product,
which is why mulmid is useful, but as far as I see, we can't exploit
"don't care"-limbs with wraparound arithmetic).
In the FFT range, wraparound arithmetic should save roughly 30% of the
work compared to a full multiplication, but it's not clear to me what
saving one can expect for smaller sizes.
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list