Re: gcd of large numbers.

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

> From: Louis.Granboulan@ens.fr
> Message-Id: <199802091302.OAA29249@pleurote.ens.fr>
> Subject: gcd of large numbers.
> To: pari-dev@list.cr.yp.to (Pari Workers)
> Date: 	Mon, 9 Feb 1998 14:02:23 +0100
> 
> We use "gerepile" in "mppgcd"'s internal loop.
> This is useful for integers of 10000 digits.

(But perhaps worthwhile _not_ to do for integers occupying just four
or five words?)

By the way, I have code here which will speed up PARI's integer
_extended_ gcd computations (bezout, inversemodulo) by a factor
of 2.5 ... 3.5 depending on operand size and platform, waiting
to be merged in after the 2.0.beta release if I understood Karim
correctly.  This is Lehmer-based, but often avoids divisions (and
multiplications) nonetheless, so how it compares to the binary-shift
algorithm in mppgcd() may depend on the underlying hardware.

It also does far fewer allocations.  I haven't tested it with 10^4
digits, but I'll bear this case in mind when I prepare the final
patch.

Enjoy, Gerhard