max planck institut
informatik

# Bit-Stream Descartes

## Introduction

This page reports on some first experiments with the Bit-Stream Descartes Method for root isolation of square-free polynomials whose coefficients can be approximated to within an arbitrarily small but positive error bound. The key to get this done for all inputs is to avoid interval endpoints close to complex roots, and to represent the polynomial in the Bernstein basis in order to exploit its good numerical properties. For a description of the algorithm, see the following article.

## Variants

We compare the following variants of the Descartes method.

• DescartesrndL:
We apply the Bernstein Descartes method on polynomials with approximate coefficients at increasingly higher precision. The choice of bisection point is randomized in each interval (that is, locally).
• DescartesrndLbias:
This is the same as DescartesrndL, but here we bias the choice of bisection points to those with small denominators.
• DescartesrndG:
We apply the Bernstein Descartes method on polynomials with approximate coefficients at increasingly higher precision. All bisections happen at interval midpoints, but we shift the polynomial by a random offset before starting the recursive bisection (that is, we randomize globally).
• Descartesinteger:
This is the usual deterministic Bernstein Descartes method implemented with exact integer arithmetic.

The four variants have been implemented by the same team in a straightforward fashion without any advanced optimized techniques. Hence our experiments give a valid first impression of the relative performance of our new approach compared to exact arithmetic, but they are not the final word.

## Experiments

We measured running times on an 1.2 GHz Pentium IIIM using LEDA-4.5 integer arithmetic, and averaged over 5 runs for each polynomial. The time for obtaining approximate power basis coefficients and converting to approximate Bernstein basis coefficients is included in the measurements. The initial interval enclosing all roots of anxn +...+ aixi +...+ a1x + a0 is obtained using the Lagrange-Zassenhaus bound 2 maxi<n (|ai|/|an|)1/(n-i).

### Random Polynomials

To generate random polynomials, we choose n+1 integer points from [-2L, +2L]×[-2L, +2L] at random, interpolate a polynomial through them, and clear denominators. This results in random polynomials with integer coefficients and many real roots (see table below). On these instances, we compared our three new variants against the usual Bernstein Descartes method implemented in exact arithmetic. The table reports the average bitlength of the longest coefficient in power basis (usually the constant term).
To show that our method is largely unaffected by irrationality of coefficients, the last column reports on an L=50 instance generated by taking a polynomial interpolating through n random points (as above) and multiplying it with the irrational factor x - (1231/5+3211/7). This results in polynomials with coefficients that are algebraic of degree 35.

n=30 n=60 L=10 L=30 L=50 ×(x-...) L=10 L=30 28.6 27.8 28.4 27.2 54.2 58.8 58.0 57.6 1370 10642 19752 n/a 2710 37339 73456 n/a 83 ms 86 ms 90 ms 84 ms 734 ms 799 ms 841 ms 801 ms 40 ms 44 ms 47 ms 41 ms 351 ms 379 ms 428 ms 356 ms 41 ms 45 ms 49 ms 42 ms 353 ms 384 ms 423 ms 362 ms 41 ms 143 ms 266 ms n/a 403 ms 3328 ms 7996 ms n/a

These measurements indicate that our Bit-Stream Descartes Method succeeds in avoiding the extra cost incurred by exact computation with complicated coefficients (very long integers, algebraic numbers): The cost doesn't grow with coefficient complicatedness as long as degree and root separation, the problem's natural analytic/geometric complexity parameters, stay the same.

### Special Polynomials

The Mignotte polynomial q(x) = x20 - 2(1030x - 1)2 has two very close roots. The recursion depth of the Descartes Method is large on this input, and our Bit-Stream variants require a high precision to separate the roots. Both for exact arithmetic and for the Bit-Stream variants, the bound on the coefficient bitlength is dominated by n log(1/sep(q)), hence there is not much to gain from approximate computation.

DescartesrndL 5920 ms 2920 ms 4970 ms 1280 ms