Re: Information PARI\GP

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Nov 16, 2017 at 06:55:16PM +0100, Karim Belabas wrote:
> * Francesca Sarti [2017-11-16 18:39]:
> > I would like to know which algorithm is implemented in PARI\GP for
> > sqrt(); where can I find the implementation?
> 
> A divide-and-conquer integral algorithm due to Paul Zimmermann: given a
> positive integer N, it returns integral R and S such that S^2 + R = N
> and 0 <= R <= 2S (see https://hal.inria.fr/inria-00072854/)
> 
> The integral implementation is src/kernel/none/mp.c:sqrtremi() in PARI sources.
> The (trivial) floating point wrapper is src/kernel/none/mp.c:sqrtr_abs() 

However, if gp is compiled with GNU GMP support, then it uses
mpn_sqrt from GMP. The algorithms used is documented at
<https://gmplib.org/manual/Square-Root-Algorithm.html#Square-Root-Algorithm>
To summary:
Square roots are taken using the “Karatsuba Square Root” algorithm by
Paul Zimmermann.

Cheers,
Bill