CoCoA » CoCoALib

Consider the following code excerpt:

  X = [twin-float];
  BigInt Y = floor(X);
  Y <= X; // could throw???

Assuming the first two lines do not throw InsuffPrec, may the last line throw?

JAA's instinct says it should not throw, but the current impl can throw (e.g. if X is 1+eps where eps is of the same size as the random variation added to the secondary component).

The critical step is comparing two twin-floats for equality. If the two values are quite different then it is easy to say which is larger. If the equality test says true then the outcome of the other inequality relations is clear.

The interesting case arises when the values are "quite similar". Exactly what conditions are required for two twin-floats to be considered equal? And when are they definitely unequal? In all other cases the comparison is unclear (e.g. must throw InsuffPrec when doing an equality test).

The basic idea behind the current impl is that each twin-float value corresponds to two nested (real) intervals: the outer interval, and the inner interval. The inner interval is much narrower than the outer interval (ratio of widths is at least 1000), and is centrally placed in the outer interval. The idea of the heuristic is that the true value very likely lies in the inner interval, and "certainly" lies in the outer interval (this is heuristic certainty, not the mathematical certainty of interval arithmetic).

The current equality test says "unequal" of the outer intervals are disjoint, "equal" if the inner intervals are not disjoint, and otherwise "uncertain". Furthermore, all comparisons conduct an equality test and throw "InsuffPrec" if the outcome was "uncertain".

A simpler idea would be to modify when comparisons throw InsuffPrec.

The model I have in mind is a fixed (non-zero) twin-float X, and a "sliding" twin-float value Y; we want to consider what happens as the value of Y becomes ever closer to that of X. We can probably just fix X = 1 without any loss of generality. We may also assume that Y tends to X from the right (i.e. Y is "larger than" X).

The definition of the comparison functions is to enable a "smooth transition" from "unequal" to "equal" via the intermediate "uncertain".

We must also consider cases where the outer intervals of X and Y are similarly wide, and where one is far wider than the other.

Variant A

We say that X and Y are definitely unequal if the primary component of X lies outside the outer interval of Y and the primary component of Y lies outside the outer interval of X; a single test suffices once we know which has the wider outer interval.

This would resolve the problem about floor(X) <= X throwing unexpectedly unless X has an unusually narrow outer interval (narrower than that of a newly created twin-float from an integer!)

Variant B

We could say that X and Y are definitely unequal if the outer interval of X is disjoint from the inner interval of Y and the outer interval of Y is disjoint from the inner interval of X; a single test suffices once we know which has the wider outer interval.

This is only very slightly different from Variant A since the inner interval is tiny compared to the outer interval. It does not fully resolve the issue of floor(X) <= X throwing unexpectedly, but presumably makes unexpected behaviour very rare (which could be a nightmare to debug!).

Variant C

Some other degree of overlap between the outer intervals could be allowed (but I'd need a justification for the chosen amount of allowed overlap).

NOTE I have just revised the variants to make them obviously symmetric.

The idea of changing operator>= and operator<= is trickier than I had originally thought (or hoped) because they are defined in ring.C based on the "universal comparison" member function myCmp which is expected to return -1,0,+1 depending on the comparison.

The change I was thinking of involved a "comparison function" (let's call it myCmp5) with 5 possible outcomes:

• +2 definitely greater
• +1 uncertain whether equal, if not equal then greater
• 0 definitely equal
• -1 uncertain whether equal, if not equal then less than
• -2 definitely less than

The classical myCmp could easily be adapted to be compatible with myCmp5 (essentially by multiplying its output by 2).

op= would throw if myCmp5 returns +1 or -1, otherwise true if myCmp5 gives 0, otherwise false.
op>= is a little more complicated: returns true if myCmp5 gives non-neg result, throws if myCmp5 gives -1, otherwise returns false.
op> returns true if myCmp5 gives +2, false if myCmp5 <= 0, and throws if myCmp gave +1.

So technically it is not that hard to adapt the comparison operators for RingElem as suggested; however, I'm not too happy about having to change all the myCmp functions.

NOTE There is also a myIsEqual mem fn which is used by op= (rather than calling myCmp which exists only for ordered rings, and which is hopefully compatible with myIsEqual!).

With the impl I have in mind for op>= and op<= via myCmp5, it is not possible to have values X and Y such that the equality test X==Y does not give true and yet both X>=Y and X<=Y give true. Since X==Y does not give true the result of myCmp5 is not zero, so exactly one of op<= and op>= will give false.

In RingTwinFloat if X==Y does not give true (i.e. throws or gives false) then the primary component of X is clearly either greater than or less than the primary component of Y; the result of this last comparison dictates the value which myCmp5 gives.

I have added a new "boolean" data member saying whether myIsEqualNZIgnoreSign should allow the outer intervals to overlap or not (i.e. Variant (A)). At the moment the setting is fixed at compile time, and there is no member fn to change the setting (but it should be a trivial matter to add such an operation).

All tests pass with either setting, so I have checked in the code.

I have not yet updated the doc for RingTwinFloat.

I have updated the documentation for RingTwinFloat.

In practice the current impl of myCmp deals first with the obvious cases, then calls myEqualNZIgnoreSign. If that fn returns uncertain3 then myCmp throws InsuffPrec. This means that if any comparison between two twin-float values X and Y throws, then all comparisons will throw.

The question about floor(X) <= X in comment 2 is valid. The problem arises because converting an integer to a twin-float does discard some information (an exact value has become approximate), and the comparison floor(X) <= X does implicitly convert the integer floor(X) to a twin-float.

If we implement member fns for comparisons between MachineInt, BigInt, BigRat and a ring-elem then the problem should go away. Is it worth it? I have opened issue #896 to discuss this.

I shall close this issue since its "spirit" has now been transferred to #896.