Bill Allombert on Tue, 8 Oct 2002 16:11:05 +0200

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

Re: precision and contfrac()

On Tue, Oct 08, 2002 at 02:43:50PM +0200, Thomas Baruchel wrote:
> Brest, le mardi 8 octobre
> Hi, I wonder how I should set the precision \p in order to
> have n exact terms in the continued fraction expansion of
> sqrt(x) (x being exact).

It is a difficult question. The precision exhausted depend on the size of the
partial quotients, which are very hard to control.

> For instance, what precision is needed in order to be sure that I
> have 500 exact terms ? 2,000 ? 10,000 ?

You do not need to use reals for this computation:

Try this script, similar to examples/

cf(D,n) output the n first partial quotient of sqrt(D),
without relying on real numbers.

cf(D,n) =

  if (type(D) != "t_INT" || D < 2, return(-1));
  u = sqrtint(D); v = D-u^2;
  if (!v, return(0));
  r = u;  
    u = (r+u)\v * v - u;
    v = (D-u^2)\v;a