Re: [Axiom-math] POLY INT =\\= UP(x, INT)

[Dylan Thurston]

On Fri, Oct 10, 2003 at 12:15:22PM -0400, William Sit wrote:
> > For instance, suppose I have an algorithm that only works
> > if I can actually compare elements for equality (with the standard
> > mathematical definition of equality, not equality of representations,
> > which is only a vaguely useful heuristic approximation).  How can I tell
> > if it's safe to apply it to a particular group?
> 
> If the mathematical object has a (and it must have one if computation is to be
> done) representation, then your mathematical equality algorithm should be
> implementable in general based on that representation. In some cases, this may
> be a lazy comparison if the representation is only approximate for some of the
> elements: for example, for infinite precision reals using a decimal
> representation or continued fraction.

I don't understand what you're getting at here.  Yes, your mathematical
objects should have some well-defined notion of equality; but that
notion of equality need not be computable.  In the case of computable
reals, one can establish that two such reals are defintely not equal, or
are equal to within some bounds, but proving that they are actually
equal is undecideable.  Thus there is no useful function that fits the
signature of "=":

      "=": (%,%) -> Boolean    ++ x=y tests if x and y are equal.

or, at least, such a function could never (or only rarely) return True.

Such objects can be useful, despite the lack of an equality algorithm.

> On the other hand, for algebraic reals represented by root of a
> polynomial, there is no true equality because no one can tell sqrt(2)
> from - sqrt(2) (conjugates are indistinguishable, and in effect, the
> representation represents the SET of all roots, and these SETS can be
> compared). 

> > If I understand this code correctly, it's doing just what you suggested
> > was a bad idea, using _$streamCount$Lisp (which is a global variable,
> > right?) to control how many terms to print if you have a non-terminating
> > continued fraction.
> Yes, the _$streamCount$Lisp variable is global, and its use in the
> continued fraction package is strictly speaking poor design. What
> should be done is to define something like two print functions, one
> with a parameter for the length of the continued function, and the
> other in terms of the first using the default value of
> _$streamCount$Lisp. This first function then is domain specific (one
> of its exports) and the second is categorical.

Yes, that would be cleaner, though it still involves the arbitrary
cutoff.

For really top-notch output, there probably has to be a more general
mechanism for deciding when to terminate power series or continued
fractions or such, which depends on the available space.

Peace,
        Dylan

signature.asc
Description: Digital signature