gmp-devel Digest, Vol 1, Issue 89

[Paul Zimmermann]

   From: nisse at lysator.liu.se (Niels M?ller )
   Subject: Range for the coeffients returned by gcdext

   By the way, I think I've understood how to do binary gcdext (although
   in the context of Schönhage's algorithm, I can use that only for the
   one limb basecase):

   [algorithm skipped]

With a colleague, we are working on a binary variant of Scho"nhage's
algorithm that works in the general case. First results are encouraging
(a threshold of about 6500 limbs with mpz_gcd, and about 1800 limbs with
mpz_gcdext, with mpz-level implementation). The nice thing is that no
correction is needed: the "quotient" are always exact.

   (where we don't keep track of the v0 and v1). We initialize with

Niels, in your gcd-0.4 code, you have a comment somewhere saying that 
you may keep only the first column of the 2x2 cofactor matrix (i.e. u0 and 
u1). Can you do that in the recursive part of Scho"nhage's algorithm?

   From: Torbjorn Granlund <tege at swox.com>
   Subject: Re: Multi-limb inverse for mpn_divrem_1

   It would be possible to get the quotient almost always right, by
   including more bits to the reciprocal.

I suggest you first try your idea on Montgomery's multiplication, 
where you *always* get the right "quotient".

For the classical division, you could use the f-p unit to get a more
precise approximation of the quotient (on 32-bit machines). Also, the
next quotient limb mainly depends from the two top high limbs from the
mpn_submul_1, which may be computed apart.

Paul