GMP 4.4 remaining tasks
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Mon Dec 7 22:37:36 CET 2009
> > The "adjustment step" I'm using now... is needed only for the last
> > iteration (the intermediate ones are adjusted by the next iteration),
> but
> > it is _not_ cheap.
>
> From the work on single-limb inverses (invert_limb, see Alg. 2 and 3 in
> http://www.lysator.liu.se/~nisse/archive/draft-division-paper.pdf), I
> suspect that it is very difficult to get an "exact" reciprocal
> floor((B^{2n} - 1) / X) without an expensive multiplication at the end.
>
> Define "expensive multiplication". For the single-limb case, an extra
> limb multiplication is "expensive". For the n-limb case, the result
> should be possible to adjust in time O(n).
We should try the "add a virtual limb" strategy... But if you have the
"exact or one unit too small" result and want to correct it... I suspect
that you need an expensive nxn multiplication...
> Getting mpn_invert to compute a slightly better value should not be
> hard. For example, including another limb from D (called A in MCA)
> should help. Also, one may avoid doubling the number of limbs in each
I did some tests, the "try mpn_inverse" test passed without any correction
with a code using "3/4" instead of "1/2" for the last iteration. Problems:
1) this does not mean that the code was correct for _any_ input (some
simulations I did with gp-pari suggest it was not)
2) that code was much _slower_, and this is obvious: the last step
required a (n*3n/4) and a (3n/4*3n/4) product instead of (n*n/2) and
(n/2*n/2)
> iteration. The basecase will surely be rather large, judging from
> mpn_binvert it will be over 500 limbs, which means an extra limb will
> imply a very little relative cost.
I did not collect timings very carefully, but my first attempt suggest a
smaller threshold, somewhere around 20 limbs, compared to the mpn_invert
currently available in the repository.
Regards,
Marco
--
http://bodrato.it/
More information about the gmp-devel
mailing list