Karim Belabas on Thu, 16 Nov 2017 18:55:29 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Information PARI\GP


* 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() 

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`