To confuse two roots, the approximation error would have to be larger than the minimum distance between two roots. I'm using PolynomialRoots.jl to calculate roots, and it has the ability to calculate roots to very high precision (using BigFloats) but of course it's hard to *guarantee* precision. If Nemo.jl has guaranteed root isolation, that would be very helpful, and I'll look into using it. Thanks.
As for highly clustered roots, you can take the complexity of the polynomial to be the sum of the number of bits required to represent its coefficients, in which case my point stands - you need fairly complex polynomials to get roots clustered in a way that would trip up my implementation. Again, I'll look into using Nemo's root isolation methods. Cheers, On Thursday, July 14, 2016 at 10:35:23 AM UTC+12, Fredrik Johansson wrote: > > On Wednesday, July 13, 2016 at 10:18:06 PM UTC+2, Alireza Nejati wrote: >> >> Simplification and equality testing are *exact* operations as they work >> by distinctly specifying the roots of a minimal polynomial. Two algebraic >> numbers are distinct if their minimal polynomials are distinct. If their >> minimal polynomials are equal, then they can only be equal if they are the >> same in a small set of distinct roots, which can be exactly distinguished >> by calculating the smallest distance between roots (this is >> AlgebraicNumber.prec). I'm not sure what you mean by nonrigorous numerical >> approximations. >> > > If the roots are computed approximately, you can get wrong results when > you compare them without taking the approximation errors into account. > > >> The worst-case scenario would be if the minimal polynomial had two roots >> that were too close for the root-finding procedure to distinguish. If this >> happens in practice though, because of the restriction of polynomial >> coefficients to integers, you'd be dealing with a very, very complex >> polynomial, and at that point you'd have more problems (it's likely that + >> and * would exhaust system memory or at least take a *very* long time to >> process). >> > > Integer polynomials with highly clustered roots are not at all a rare > thing. Note that you don't even need high degree for this; large > coefficients suffice. > > Fredrik >
