Possible gcd/hgcd/gcdext improvements

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

>    I just realized that one can probably make a more efficient hgcd_appr
>    also in this case, by gradually dropping low limbs from the
>    computation.

I've now written a hgcd_appr analogous to Lehmer's algorithm (i.e.,
iterating hgcd2), which works this way. Attaching the implementation and
(somewhat verbose) test code. To build it with gmp, one must first move
the function hgcd.c:hgcd_step to a separate file (together with
hgcd_hook), rename it to mpn_hgcd_step, and make it non-static.

Seems to work fine, even if I don't yet fully understand the pattern in
which n (current size) and s (current target size for the stop
condition) are updated, though.

Each time one discards some of the least significant bits, one loses one
bit of "precision" in the sense that the returned matrix will be roughly
one bit smaller, and the corresponding reduced numbers will be one bit
larger.

Currently, bits are discarded one limb at a time. We also get some extra
bits of precision for free compared to plain hgcd because the original
stop condition is defined in terms of limbs rather than bits, so in many
cases the return value will actually be identical to plain mpn_hgcd.
(You may need some deep meditation to make sense of this terse
description).

Regards,
/Niels

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: hgcd_appr.c
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20111005/230ee668/attachment.c>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: t-hgcd_appr.c
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20111005/230ee668/attachment-0001.c>
-------------- next part --------------

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.