Bill Allombert on Wed, 02 Aug 2017 23:05:47 +0200

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

Re: Continued fractions for square roots

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)