|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) Cheers, Bill.