RealInterval Implementation Notes

This implementation does not take floating point errors into account, which of course is a serious shortcoming. Or changing the point of view slightly, it assumes that methods like exp or tan do not represent the mathematical functions e^x or tan(x), but they represent a function correctly described by its implementation that would work in the same cumbersome way eg on irrationals or rationals not correctly representable by Floats. This thought-trick often helps me understand an unexpected result of some calculation.

This is the main difference to other implementations, it is essentialy just a proof of concept or a toy experimentation kit, not a real implementation of interval arithmetic! Nevertheless from a practical point of view the results especially when using simple interval algorithms are often so good, that one tends to forget that mentioned thought-trick. One has to keep in mind though, that in Pharo the floating point error can occasionally become not negligible (see eg comment in RealInterval>>tan). Of course it would be possible to change the code so that floating point errors would be taken into account, but one problem here is speed, the algorithms would need too much time; and another problem is, one can not simply assume that normal Pharo results are correct up to one ulp. A third problem would be that one looses precision related to real implementations, because those implementations use the machine-internal up/down-rounding flags and those flags are not reachable from the outside. In other words, don't expect the impossible & keep the thought-trick in mind! By the way RealInterval works in general nicely together with ArbitraryPrecisionFloat, of course it will get really slow then.

General

For addition, difference, multiplication and division I followed "Interval Arithmetic: from Principles to Implementation" by T. Hickey, Q. Ju and M.H. van Emden: http://fab.cba.mit.edu/classes/S62.12/docs/Hickey_interval.pdf.

Additionally I occasionally followed "Vienna proposal for interval standardization" by Arnold Neumaier: http://www.mat.univie.ac.at/~neum/ms/1788.pdf.

Differences to the Vienna Proposal

Nonstandard intervals are not implemented at the moment (but it would not be complicated to change that, one could eg easily subclass kaucher's directed intervals).

Flags like possiblyUndefined and such are mentioned that make quite some sense to me and I implemented the possibility to use those flags via comments:, but implemented those flags only extremely sporadically and randomly, just to test how I could use them. In other words they are not implemented, but it would be simple to add this. Also no way to propagate those flags from one operation to the next is implemented, this would slow down computation as different flags would propagate in different ways.

I made no distinction between <phi> and <phi>hull (in the parlance of the ViennaProposal) and usually implemented simply <phi> (with a few exceptions in the truncation section), as this distinction is more or less unnecessary with the implementation of IntervalUnion. And then there is hull and hull:.

The inverses <phi>Inv and <circ>Inv are not implemented.

The ViennaProposal says: "In particular, isIn(x,xx) returns 0 when x is +-Inf or NaN and the interval is standard." I dont understand the rationale for this, hence includes: returns true if +-Float infinity is x and is a boundary.

Midpoints (and their use as cutpoints) are not necessarily implemented exactly according to the ViennaProposal, simply because I found that more practical; it seems to me that the usual implementation is just used, because it makes the written definition of a midpoint shorter. But then its easy to change that.

asNumber works differently to the usual Pharo or Smalltalk implementation insofar as, if a RealInterval is not reducable to a Number, it does not produce an Error but returns simply self. This is more practical for reducing results to a simple form.

isZero also does not work as expected, it always returns false. This is absolutely necessary for simple arithmetic operations to work. One can use isZeroInterval instead, which works as expected.

Problems

I had a problem with the functions min: and max: in so far as as I was unsure what one should do in the case of comparisons with Float infinity and its negated values. I took a completely inconsistent approach to try out what should be better, see the tests TestRealInterval>>testMin & testMax and TestIntervalUnion>>testMin & testMax. Perhaps the approach in IntervalUnion would be better (?) in general. Or probably not. Or perhaps it depends on the reason why you calculate something.

While raisedToInteger: works with Integer arguments and also with IntervalUnion from: anInteger to: anotherInteger, it does not accept intervals like eg RealInterval inf:1 sup:2.5, although it would make sense if in such a case the RealInterval would simply be transformed into an IntervalUnion of integers 1 and 2. Obviously this would not work with infinite intervals and would produce speed problems with big intervals. Of course I immediately thought about a heuristic like transforming only a part of big or infinite intervals and use raisedTo: for the rest, which would obviously envelop the result and insofar would not be wrong, but then the cutpoint as implemented would be highly ineffective and this transforming often would happen repeatedly, hence I simply did not allow arguments like this for the moment.

\\ does not allow intervals as argument, although it should. It looks like it would need more than a few seconds of cursory thinking to implement, hence lazy as I am I have not yet done it.

Although cutpoint is not exactly implemented like usual, in my opinion it still is relatively near to the normal way, in other words this should be no problem. I guess one could make the argument, that for efficiency reasons one would want the same relative error in the part under the cutpoint & over it (an ulp is smaller near 0 than near Float fmax). Then I guess one would want to use something like the geometric mean instead, although normally the arithmetic mean is used, as generally in this project. But then not only at the upper scale, near Float fmax, problems would occur earlier, the same problems would occur near the lower scale:

a:=1.0e-300.
b:=a predecessor predecessor.
 "9.999999999999997e-301"
a+b/2.
 "9.999999999999999e-301" "fine"
(a*b)sqrt.
 "0.0" "outside"

RealInterval fromNumber: Float infinity returns just an empty interval, hence it is not possible to really make such an interval. While it would be preferable to have such an interval, because then one could indeed make the implemented algos work on [Float infinity negated, Float infinity] with some small adjustments of cutpoint, but eg the problems would start with such simple calculations like Float infinity - Float infinity, which also in interval form would need to return a NaN. Therefore such an interval is not really possible.

Missing

In IntervalUnion these methods of RealInterval are at the moment not implemented, as they are not really needed to make both compatible and polymorphic:

• inflate
• comments
• between:and:
• isAnInteger
• isMixed
• negative
• positive

And although Numbers are generally polymorphic to RealIntervals some of these methods and a few others, that I considered to be unimportant, are also not implemented.

Back