Re: algorithm used in "quadunit"

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

On Fri, Oct 02, 2020 at 03:48:14PM +0200, Michael Hortmann wrote:
> "quadunit" provides a very efficient way to solve the Pell equation, much
> faster than any pari-implementations I know that use continued fractions.

quadunit uses exact continued fractions.
 
> Of course I could now try to analyze the Pari sources

Why not ? quadunit is in src/basemath/arith1.c and is rather short.

> , but maybe you know a
> link to a high level description of the algorithm used in quadunit?

> (Similar questions could be asked about the algorithms used in other Pari
> functions: I didn't see any such documentation on the Pari website. Maybe I
> didn't dig deep enough, or just overlooked it?)

Most of them are explained in Henri Cohen book GTM 138 (Springer).

quadunit is Algorithm 5.7.2 page 270.

Cheers,
Bill