Univariate Continued Fraction solver |
The family of methods based on continued fraction expansion proceed as follows:
Algorithm solve_continued_fraction(f,
Compute an integer lower
Shift
Compute the number
if
Split the polynomial
Apply reccursively the algorithm on
)
on the interval 
.
where 
is a
univariate polynomial expressed in the monomial basis
and 
is an homography such that
and and 
.
bound
of the positive roots of 
;
by :
;
of sign
changes of the coefficients of 
;
then output the
corresponding isolation interval and stop; if 
stop also;
in 
whose positive roots correspond to
the roots of in 
, 
whose positive
roots correspond to the roots of
in 
.
and 
.
where 
and 
are consecutive continued fraction
approximations of a root 
of 
and such that all roots of
of is in one of these intervals.
Such a solver computes the first terms of the continued fraction expansion of the roots of a univariate polynomial. Two variants are also available, depending wether we want to isolate or approximate the real roots.