GMP 4.4 remaining tasks

[bodrato at mail.dm.unipi.it]

>   > 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/