Re: Continued fractions for square roots

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

On Wed, Aug 02, 2017 at 04:28:20PM -0400, Charles Greathouse wrote:
> I'm working on a project where I compute the periodic part of the continued
> fraction of the square root of a (nonsquare) positive integer.
> 
> The obvious approach is to take the numerical square root, compute the
> continued fraction (dropping the last, say, two terms), and see if it ends
> in a periodic part with enough members to feel confident in the pattern,
> maybe three. If not, increase precision and try again.
> 
> But I was concerned about the possibility of numerical error, so I rolled
> my own implementation which avoids t_REALs. I think the algorithm is
> classic; I modified it slightly from Beceanu 2003
> 
> This works, but it's slow. Is there a better way to do this? Are there
> tight enough bounds so I could prove that the approximation is close enough
> that the apparent period is in fact the period? Any other comments on my
> idea or code?

In GP it is probably more natural to use Qfb instead of quadratic surds.
For example
Q = Qfb(1,0,-19);
Q1 = qfbred(Q,3)
Q2 = qfbred(Q1,3)

Cheers,
Bill.