========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970723.150625.209@yktvmv.watson.ibm.com> Date: Wed, 23 Jul 1997 19:06:25 GMT References: Craig Burley wrote: >Yep, availability of interval arithmetic in Fortran would indeed speed >up conversion of existing non-IEEE systems to ones that do support >IEEE 754 or equivalent. (IEEE 754 apparently was designed with >interval arithmetic in mind, so I guess the question is, given that >we've *already* been "paying" for this investment for the past 10 >or so years, why not actually start using interval arithmetic?) Perhaps because putting interval arithmetic support into IEEE 754 was a mistake (as shown by the fact that nobody uses it). Putting interval arithmetic into Fortran would be a case of throwing good money after bad. Craig Burley also posted: >Yet, interval arithmetic is the *only* new feature I've seen added >to Fortran that has such promise for giving people *correct* >answers to their engineering problems, and perhaps, in the end, >more quickly, once intervals are standardized and used widely enough >to encourage a few silicon vendors to offer specific support for >them (which I'd like to see happen *after* real apps that use them >have existed long enough for everyone to know what they're doing; >ref my concerns about putting GC or even things like BCD support >in silicon). > >So, looking at the situation objectively, given what I know, I have >to ask, "is it more important for bridges, airplanes, skyscrapers, >and so on to be built using tools that produce *correct* answers, >or to behave just as *existing* programmers and hardware designers >prefer?" It's a tought question, but since it seems unlikely that >only *existing* programmers and hardware are likely to build the >Dangerous Machines of the Future, I'd prefer the industry offer >tools that produce the correct answers, and make worrying about >complexity (especially in the sense of portability) secondary. Someone has sold you a bill of goods. "Correct answers" like (-inf,inf) are not much help in designing bridges, airplanes, skyscrapers etc. I am unaware of any epidemic of bridge etc. failures due to incorrect computer computations using current tools, but even if there were such a problem interval arithmetic would not fix it. Interval arithmetic is a failed idea with a cult following which unfortunately appears to have some influence on standards committees. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970728.145246.248@yktvmv.watson.ibm.com> Date: Mon, 28 Jul 1997 18:52:46 GMT References: Craig Burley posted: >I do think, however, that intervals *could* help a *substantial* >portion of the Fortran-using population get more correct answers >in the sense that they'll see *right away* that their algorithm >is unstable (assuming a quality implementation of intervals, e.g. >one that delivers sharp results in the realm of 1 ULP), that their >results have fewer digits of precision than they might otherwise >have thought, and so on. > >That is, it seems to me that it's a fairly large audience of >Fortran that would *learn* something if, instead of getting >output such as the following from some typical Fortran code they >wrote > > 1.995438218532022E-6 > 9.667522032954925E+2 > -3.123321588412381E+8 > >they got, simply by using intervals properly, output such as > > 1.995E-6 > 9.667522E+2 > -3.E+8 > >without having to make lots of hairy I/O changes. > >Intervals can provide that kind of change in output, showing just >how many decimal digits of precision your *code* (and thus the >implementation of your *algorithm*) yields in a particular run >on a particular data set. > >And, yes, in some cases, the string (whatever it is) for +Inf,-Inf >will be printed over and over again... > >...but if I were a betting man, I'd make substantial bets at pretty >much any odds that the sets of "people who know their algorithms >would, when recoded with intervals, print uesless answers" and >"people who, after recoding their algorithms with intervals, got >useless answers" will *not* be identical. You are rather seriously misinformed. Interval arithmetic can not do this. An interval of -inf, inf does not mean that your algorithm was producing useless answers. It may mean instead that interval arithmetic is producing useless error estimates. The problem with interval arithmetic is that it does not produce tight intervals, an algorithm can in fact be very accurate and still generate intervals of -inf, inf when coded with intervals. The basic reason for this is that errors in different variables are not independent and may be correlated in such a way that they largely cancel as the computation proceeds. Interval arithmetic is unable to account for this. For example suppose you are computing z=x/y. Suppose x and y are intervals (0>1), then the error in y is correlated with the error in x in such a way that it almost entirely cancels when computing x/y. Interval arithmetic has no way of keeping track of this and must assume the worst case which can be far too pessimistic. This may seem like a contrived example but many commonly used numerical methods (such as I believe Gaussian elimination) depend on errors offsetting in this way and would not work if they didn't. Interval arithmetic does not accurately estimate the error in such methods. This is kind of like expecting that putting a device in a car which says "warning slow down!" whenever the car exceeds 10 mph will make people better drivers. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970728.161210.925@yktvmv.watson.ibm.com> Date: Mon, 28 Jul 1997 20:12:10 GMT References: <19970723.150625.209@yktvmv.watson.ibm.com> I posted (regarding Craig Burley's posts on interval arithmetic): >> Someone has sold you a bill of goods. "Correct answers" >> like (-inf,inf) are not much help in designing bridges, airplanes, >> skyscrapers etc. I am unaware of any epidemic of bridge etc. >> failures due to incorrect computer computations using current tools, >> but even if there were such a problem interval arithmetic would not >> fix it. Interval arithmetic is a failed idea with a cult following >> which unfortunately appears to have some influence on standards >> committees. Craig Burley replied (in part): >I'll promise you this though: nobody sold *me* a bill of goods, >as I won't be paying anything for interval arithmetic myself. > ... Maybe you aren't paying in money, however you are paying in terms of your reputation for knowing what you are talking about (at least in my eyes). Craig Burley continued (in part): >So, are you *absolutely* convinced that, even once interval arithmetic >has been added to the standard (or a pending one) and is available in, >say, two or three popular industry Fortran compilers, that *nobody* >will find a use for it that couldn't have been just as easily handled >(and inspired) without intervals? (And I mean using fair judgements >that allow for the fact that the personal computer, spreadsheets, the >Macintosh, and so on all *did* inspire new uses indicating their >"necessity", even though nothing they did for people couldn't have >been done using existing, older technology, had it simply been >"properly" used by "experts".) A small fraction of fortran users will probably find some specialized uses for intervals. (Btw these will be experts not the naive users you keep invoking. The naive users will be bugging you with questions about why interval arithmetic gives them error estimates of -inf, inf when in fact their answers are accurate to 12 decimal digits.) This does not make interval arithmetic a worthwhile addition to fortran. Lots of things would benefit a few fortran users but are not worth the cost. Craig Burley continued (in part): >If you are, and you appear to be, that's great, I almost certainly >have far less knowledge with which to contradict you. But I am >curious whether you'd really say intervals will turn out to be >the "pet rock" (or worse) of Fortran -- something that catches on >quickly and widely but fizzles shortly thereafter -- or do you >entertain any possibility that it might turn out to be the IBM PC >of Fortran -- something that's clearly unnecessary and obsolete >the moment it goes out the door, but due to reasons unrelated to >its technical superiority, catches on like wildfire and becomes >the standard for well over a decade? I think it will be like the non-nearest rounding modes in IEEE arithmetic, poorly supported by vendors, ignored by most users. As for knowledge, try going to a university library. Find the section on numerical methods. Pick out a few books at random. Look up interval arithmetic or interval analysis in the index. See what they have to say. I believe that (making allowances for academic conventions of politeness) you will find little support for your extremely favorable view of the value of interval arithmetic for general purpose computations. Craig Burley continued: >Note that I won't even pick on you for being at IBM. Almost all >of us are aware of now-infamous statements made by IBM luminaries >about the uselessness of several proposed technologies IBM was >not interested in, maybe wanting to discourage its customers from >trying out -- such as total number of computers the world would >have need for, or local-area networks -- but I for one have >little information on the now-dead technologies IBM'ers accurately >predicted *would* fail, as it's the sort of thing people don't >trumpet, so I assume there are many of those as well. So I >don't think simply working for IBM in any way disqualifies you >as having sufficient expertise to claim that interval arithmetic >is a solution looking for a problem it will never find (if that's >what you're saying). (This paragraph is for the benefit of those >who should think twice before flaming you for being at IBM and >downplaying the usefulness of emerging technologies, of course.) There is a problem, generating reliable automatic error estimates. Interval arithmetic is not a solution. Actually Microsoft gets most of the flames these days. Flames for working at IBM would probably be a good sign. Obviously my position is my own and not IBM's. In fact IBM once devoted considerable resources (including specialized hardware support) to ACRITH (an interval arithmetic variant based on a super accurate dot product operation). It was somewhat less sucessful than the IBM PC. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970729.181618.170@yktvmv.watson.ibm.com> Date: Tue, 29 Jul 1997 22:16:18 GMT References: <19970728.145246.248@yktvmv.watson.ibm.com> <33e1c231.5850482@news.demon.co.uk> Brian Drummond writes: >Then in many cases, recoding the algorithm taking this into account >(using x + z in place of y) will preserve the computational semantics >and eliminate the excessive intervals. Craig's point that users will see >such instability from the large intervals is correct here, and it will >then be up to the programmers to pay attention to the quality of their >code. This is not true. What does x/(x+z) mean in interval arithmetic? It means compute the interval, call it y, which is the sum of the intervals x and z (using the rules for arithmetic with intervals) and then compute the interval w which is the quotient of the intervals x and y (again using the rules for arithmetic with intervals). There is no provision for keeping track of any correlations which may exist between operands. My point is large intervals do not necessarily indicate any instability or other problem with the code, they may just indicate that interval arithmetic is not providing a tight bound. This is the fault of interval arithmetic not the programmer. Brian Drummond continued: >At least the problems will be visible. It does not follow from that, >that there will be adequate support for debugging interval arithmetic >problems, or that the outcome will be as fast as the original. However, >if the quality of the result is important, interval arithmetic will >uncover coding "errors" that remain hidden today. Interval arithmetic detects coding errors in the same sense that a fire alarm which rings continously detects fires. Most people do not find this useful. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970730.144402.064@yktvmv.watson.ibm.com> Date: Wed, 30 Jul 1997 18:44:02 GMT References: <19970723.150625.209@yktvmv.watson.ibm.com> <19970728.161210.925@yktvmv.watson.ibm.com> Craig Burley writes (in part): >As far as how people react when they see "<-Inf,+Inf>", all we have >to do is explain that it's computerese for "does not compute" or >"insufficient information to produce an answer". They'll understand >that, if they've ever watched Star Trek and other shows like that; >certainly they'll *understand* that their answers are invalid better >than they will if the computer prints "5.1959324" instead. (Or do >you claim otherwise?) I certainly do claim otherwise. The problem with interval arithmetic is it does not produce tight bounds. It can and does produce intervals of -inf, inf when the user is using a completely valid algorithm and his 5.1959324 is accurate to 8 places as printed. People ignore warnings which give an excessive number of false alarms (as interval arithmetic will). Compare this to redoing the computation in extended precision. Now if the answer becomes say 6.2498263 this is a reliable indication that something is wrong. On the other hand if the answer remains 5.1959324... it is likely that these digits are reliable. This sort of rule of thumb procedure will be much more valuable for the average user even though one can contrive examples where it fails to work. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970804.141635.393@yktvmv.watson.ibm.com> Date: Mon, 4 Aug 1997 18:16:35 GMT References: <19970723.150625.209@yktvmv.watson.ibm.com> <19970728.161210.925@yktvmv.watson.ibm.com> <33DE07F5.59E2@maths.nott.ac.uk> Andy Walker posted: >Or perhaps IA will still be a turkey. But it would be nice to know >whether it can be made to fly. How much effort are you prepared to force (by putting IA in the fortran standard) people to expend proving beyond any doubt that IA is a turkey? What proof would you accept? In my opinion the IA support in the IEEE standard is already more support than IA deserves. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970804.142703.955@yktvmv.watson.ibm.com> Date: Mon, 4 Aug 1997 18:27:03 GMT References: <19970723.150625.209@yktvmv.watson.ibm.com> <19970728.161210.925@yktvmv.watson.ibm.com> <19970730.144402.064@yktvmv.watson.ibm.com> Craig Burley writes: >So you claim it is better to deny these users the choice of *also* >easily trying the interval-arithmetic versions of their algorithms, >thereby forcing them to continue use only single- and double-precision >versions, as well? And that it is better for users who, by some >miracle, happen to *not* have stable algorithms, to see "5.195324" >than "<-Inf,+Inf>" or "*****"? > >Amazing. It'll be interesting to see how a judge and jury take this >if it ever comes up in a liability suit. ("We didn't provide a >simple means to test whether the result was accurate because we >decided too few people needed it, and everyone uses valid algorithms >accurate to 8 places anyway. The 300 people who died in that crash did >so because the culpable algorithm was simply a rare example of one that >gave the same output in single- and double-precision, both of which >were wrong, and which interval arithmetic would have at least caught >as <-Inf,+Inf>. We decided nobody would be smart enough to investigate >why their algorithm didn't produce sharp results using intervals, >so we campaigned successfully against giving them the choice of using >intervals in an economically effective way.") What easy way of trying interval arithmetic versions of algorithms are you proposing? Are you claiming it is feasible to offer an option analogous to the autodbl (or similarly named) option, which automatically increases the precision of a fortran program, which automatically converts a program to use interval arithmetic? Btw, wishful thinking to the contrary, in most cases there is no economically effective way to use intervals for large real computations so a campaign against such giving users such a choice would be like a campaign against teaching pigs to fly, pointless. As far as legal liability goes, do you feel users should be allowed to use optimizing compilers? After all these are notoriously unstable and full of bugs? Craig Burley continued: >I guess it shouldn't be surprising to me anymore that there'll >always be some people fighting tooth and nail against giving people >*more* choices. Maybe they're too stupid to cope with having >interval arithmetic as another choice; how such people came up >with valid algorithms accurate to 8 decimal places that wouldn't >pass a simple-minded conversion to interval arithmetic is a puzzle, >but I find many things puzzling. I am not objecting to giving people choices, I am objecting to forcing people to support useless features by placing them in a standard. Nothing is preventing you or any other compiler writer from implementing interval arithmetic as an extension to the standard. I see no reason this would be any harder than adding extended precision types which many have done. The relative lack of interval arithmetic extensions indicates to me that most people believe it is less useful than extended precision arithmetic. Why should a standards committee take it upon itself to overrule the collective judgement of the fortran community by including interval arithmetic in the standard. You are pretty quick to throw around words like "stupid" considering you have conceded you don't really know anything about the subject being discussed. Most users do not invent algorithms, they implement algorithms found in a textbook or other source. These algorithms are designed to compute valid answers (where possible) using standard computer arithmetic. They are not designed to work well when converted to intervals (a much harder problem) and often will not. Craig Burley continued (in part): >What I do know is that, as a language designer and compiler provider, >I'd rather give people more choices, especially good, clean tools >like IA that might or might not work for them in a particular situation. Well, of course, as a compiler writer, you could try giving your users what they want. However you don't appear to have much respect for fortran users so you might find that painful. In my case I would rather that compiler writers concentrated on efficient implementation of the core language rather than waste time implementing esoteric extensions. For example you keep mentioning complex arithmetic. Complex arithmetic would be more useful if compilers could be counted upon to do a decent job of optimizing it. Until then many users will simulate it in real arithmetic. Craig Burley continued (in part): >Clearly there's not even agreement on something as fundamental as >interval arithmetic, something invented in the late '50s, widely >agreed upon in terms of its implementation, somewhat widely used, but >the disagreement is whether it should even be offered as a *choice* >in languages like Fortran -- forget about trying to get agreement >on whether/how it should be in silicon. How about a summary of the widely agreed upon standard implementation of interval arithmetic. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970804.153111.162@yktvmv.watson.ibm.com> Date: Mon, 4 Aug 1997 19:31:11 GMT References: <19970723.150625.209@yktvmv.watson.ibm.com> <19970728.161210.925@yktvmv.watson.ibm.com> <33DE07F5.59E2@maths.nott.ac.uk> <5rl5hp$kkq@lyra.csx.cam.ac.uk> <33DF4B42.41C6@maths.nott.ac.uk> Andy Walker posted: > ... even in this case. Naive users should not be writing >their own matrix inversion code, and similar! If they do, they are >indeed quite likely to get Infs and NaNs. Even "professionals" >probably shouldn't be doing this -- only a tiny proportion even of >maths graduates know enough NA to stand a reasonable chance of >implementing a robust matrix inversion routine. But we don't need >to! Even in *your* student days, Nick, there were already library >routines for this sort of thing; these days, there are even quite >good libraries of numerical and statistical algorithms. These can >be written in such a way as to by-pass the single-number IA, to >make use of whatever high-precision intermediate steps are needed, >and to output appropriate intervals with their results. Maybe it is possible for standard library routines to output intervals in these cases, but the most widely used libraries such as Linpack or Lapack do not do this, do they? James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970804.155323.261@yktvmv.watson.ibm.com> Date: Mon, 4 Aug 1997 19:53:23 GMT References: <19970728.145246.248@yktvmv.watson.ibm.com> <33e1c231.5850482@news.demon.co.uk> <19970729.181618.170@yktvmv.watson.ibm.com> <5s4fmv$3bk$1@goanna.cs.rmit.edu.au> I wrote concerning interval arithmetic: >>There is no provision for keeping track of any >>correlations which may exist between operands. Richard A. O'Keefe replied: >That is *your* definition. Of course you can beat a straw man to death. >There is an empirical question of how much it costs to get tighter bounds >and how much it is worth to have them. It is true I am unaware of exactly what was proposed for the fortran standard. I was assuming addition of a interval data type with the standard arithmetic operators. If you think this is a straw man, what is your preferred proposal? Richard A. O'Keefe also wrote: >This really does sound like prejudice based on long out of date information. I admit I am probably somewhat prejudiced against interval arithmetic due to overexposure to ridiculous claims by its proponents. Richard A. O'Keefe also wrote: >The real problem with interval arithmetic is NOT that it doesn't handle >correlations, but that it is harder to learn to use than floating point >arithmetic. It is not hard for a novice to produce floating point code >that quietly produces spectacularly _wrong_ answers. It is not hard for >a novice to produce interval code that quietly produces correct but >_useless_ answers. In the hands of an expert, interval code can not only >produce useful answers whenever simple floating point would have, but can >tell you how good the answers are. In a world where 1/3rd of surveyed >spreadsheets (http://www.cba.hawaii.edu/panko/ssr/) are seriously wrong, >I don't think that the behaviour of interval arithmetic in the hands of >the inexpert is *obviously* damning. (Someone who thinks that interval >arithmetic _can't_ handle correlation obviously doesn't know how such >correlations _are_ handled, so may fairly be called inexpert. Inexpert >is not the same as stupid! Most of us are inexpert at most things.) I doubt the claim that it is always possible to rework algorithms to use intervals to give tight bounds. To take a simple example how does one use interval arithmetic primitives to write a linear equation solver with tight bounds? (Using some other method to get tight bounds and then expressing these as intervals is not cricket.) In any case what penalties in algorithm coding time and execution speed are you allowing your expert? James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970806.154151.583@yktvmv.watson.ibm.com> Date: Wed, 6 Aug 1997 19:41:51 GMT References: <19970804.155323.261@yktvmv.watson.ibm.com> <33E7515E.41C6@lanl.gov> William Clodius wrote (in part): >Note that if it becomes part of the standard, with appropriate >semantics, the compiler can in principle perform additional analyses, >i.e., keep track of correllations, which are more difficult to do for >derived types where the semantic information has to be inferred >indirectly at best. How much of the analysis the compiler is allowed to >perform in principle is practical in practice, and whether the compiler >implements all the analysis it could practically do is a different >matter, which is, I believe O'Keefe's point above. ... This is ridiculous. You could just as well say the compiler could, in principle, analyze your program and warn you of any numerically dubious parts. William Clodius continued: > ... One thing I would >expect a compiler to do is attempt to maintain anonymous temporaries at >as high a precision as possible to minimize growth of the bounds. I doubt compiler writers will think much of this idea. Attention Craig Burley, what do you think? As for me, this sort of thing is completely contrary to my concept of fortran should be (simple, straightforward, close to the metal). In any case it does not solve the problem of unreasonable growth of the intervals except in the case (usually unrealistic) where the problem input is exact. Interval arithmetic has the problem that the intervals tend to grow exponentially (even in cases where the actual errors do not). This will happen even with infinite precision arithmetic as long as the initial intervals have finite width. So increasing the precision of the calculations is generally just an expensive waste of time (as it is for numerically unstable algorithms). William Clodius wrote (in part): >As to the specifics of the Fortran proposal, it is still in a state of >rapid evolution that makes it difficult to obtain a coherent picture. Things in a state of rapid evolution should not be frozen into standards. I wrote: >> To take a simple >> example how does one use interval arithmetic primitives to write >> a linear equation solver with tight bounds? (Using some other method >> to get tight bounds and then expressing these as intervals is not >> cricket.) William Clodius replied: >In what way is this not valid? I consider this a perfectly reasonable >approach for vendors of math libraries (e.g., NAG) or the implementors >of Linpack if they should find it gives valid results better than >relying on implementations of the standard. The important thing for >their purposes is that the interval arithmetic type be sufficiently well >defined that the input to their routines does represent the true >intervals and subsequent useage of their output will retain the >appropriate interval information. The claim is that useful things can be done with interval arithmetic. So I am proposing a simple test. Show how interval arithmetic could be used to write a linear equation solver with tight bounds. Finding tight bounds via some other method and then expressing them in terms of intervals at the end is not what I mean by "using interval arithmetic" since interval arithmetic is contributing nothing to the solution of the problem. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970806.175703.868@yktvmv.watson.ibm.com> Date: Wed, 6 Aug 1997 21:57:03 GMT References: <19970804.153111.162@yktvmv.watson.ibm.com> <5s6ocp$bs9@lyra.csx.cam.ac.uk> I wrote: >> Maybe it is possible for standard library routines to output >>intervals in these cases, but the most widely used libraries such as >>Linpack or Lapack do not do this, do they? Nick Maclaren replied: >No, but they could. Quite a high proportion of the NAG library has >facilities to return error indications, but they are rarely in the >form of intervals. It is arguable whether they should be, because >there are often extreme correlations between the error bounds in the >output values see any reliable book on regression analysis for a >standard example. > >However, this does confirm Andy's original point. If there were a >suitable language with interval arithmetic support, it would be both >possible and fairly straightforward to produce wrappers for some of >the standard operations that returned such results. I don't see this. Consider a linear equation solver. Libraries often provide an estimated condition number. However since this is estimated one can contrive (or perhaps cannot prove that one cannot contrive) examples where it is wildly wrong (just as one can contrive examples where double and extended precision give the same wildly wrong answer). Hence there is no easy way to return intervals using such a routine as a base. Can you provide an example of a linear equation solving library routine which can be easily modified to return guaranteed tight intervals? I believe ACRITH handled this by using a super accurate inner product operation to compute accurate residuals and then using iterative improvement to refine the answers. However this is very expensive and furthermore does not appear to work when the input is not exact. Can you (or anyone else) give a pointer to an efficient procedure which computes the solution of systems of linear equations (with input in the form of intervals) and returns tight intervals for the answer? James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970806.182629.200@yktvmv.watson.ibm.com> Date: Wed, 6 Aug 1997 22:26:29 GMT References: <19970804.142703.955@yktvmv.watson.ibm.com> I wrote: >> Btw, wishful thinking to the contrary, in most cases there >> is no economically effective way to use intervals for large real >> computations so a campaign against such giving users such a choice >> would be like a campaign against teaching pigs to fly, pointless. Craig Burley responded: >"Most cases" aren't all cases. In most cases there might be no >economically effective way to use modules for large real >computations written in FORTRAN 77 or FORTRAN 66; nevertheless, >modules and all sorts of similar facilities were added to >Fortran 90. They don't make the answers any more accurate; >all I originally pointed out is that IA, unlike things like >modules, CONTAINs, user-defined operators, etc., actually >offer *some* kind of facility to get more accurate answers, >and an indication of the precision, at a low level. Don't expect me to defend fortran 90. From what I know about it (not much) it is an example of a standards committee running amok. In any case the problem with IA is not simply a conversion problem. Even if you were rewriting your large real computation from scratch IA would still be useless in most cases. As for the distinction between "most cases" and "all cases" I think proposed additions to the fortran standard should meet a cost effectiveness standard. In this case I do not believe the benefit (if any) to a few users would come within orders of magnitude of the cost you would imposing on all users. I posted: >> As far as legal liability goes, do you feel users should >> be allowed to use optimizing compilers? After all these are >> notoriously unstable and full of bugs? Craig Burley replied: >"Allowed to" is wasn't what I was talking about at all. I was >talking about liability; that's a different kettle of fish. > >It might well be the case that, down the road, it turns out the >best way to get reliable answers on a particular algorithm >that, implemented unreliably, contributed to death and/or >destruction of some kind, is to use IA as a low-level type instead >of the underlying IEEE 754, regardless of whether the code >was compiled with or without optimization. In such a case, >if the coders avoided IA because they didn't "like" it, or >didn't want to spend the extra $$ for a compiler that supported >it, there might well be a liability. A deserved one? Well, >my views on tort law are pretty extreme by today's standards, >so I'd say no, but in today's environment, where one might >win millions of dollars for spilling one's own hot coffee in one's >own lap, it behooves people and businesses to be sure they >aren't cutting corners that might save a few lives here are >there just to save a bit of hassle or expense. You were suggesting that use of extended precision arithmetic to estimate errors might entail legal liability in the rare cases where this fails. I was asking if you would make the same argument about use of optimizing compilers. After all this is substantially less safe than running without optimization. I posted: >> I am not objecting to giving people choices, I am objecting >> to forcing people to support useless features by placing them in a >> standard. Nothing is preventing you or any other compiler writer >> from implementing interval arithmetic as an extension to the standard. Craig Burley replied: >You are not just campaigning against adding it to the standard. >You are campaigning against it being available or used *at all*, >from what I can tell. Nothing is *requiring* anyone to implement >the Fortran standard; they can always choose not to, just as >some choose to implement it not-quite-perfectly. > >I've worked for one company that sold plenty of serious >machinery with Fortran compilers that were "ANSI FORTRAN 77 standard" >-- except they had no CHARACTER type, I/O operations, assigned >GOTO, alternate RETURN, alternate ENTRY point, or a few other >things like that. Customers still bought it, because it got >the important work done, sometimes with only a modest rewrite >(say, a few man-weeks, well worth the performance boost I suppose). > >(The company got bought out and shut down, well *after* I had >helped solve the problem of most of these missing features, >IMO because of management problems in the company; the compiler >group didn't have those problems, and was one of the stars >in the company, which is why I left a higher-level management >job to become a senior engineer in that group.) > >If Fortran 2000 indeed requires IA, and you don't think people >will benefit from IA, just sell otherwise-F2K compilers *without* >it for less -- it'll take you less to develop, after all -- and, if >you're right, you'll steal food off the plates of all those >other vendors who wasted resources doing the useless IA stuff >that all their customers discover is a waste of time. This is disingenuous. It is much easier for a vendor to offer a compiler with extensions to the standard than with deletions from the standard. For this reason putting useless features in a standard causes a lot of resources to be wasted supporting them. In my opinion nothing should go into the standard which has not first been successful as a vendor extension. Of course if enough useless crud is put in a new fortran standard vendors may reject it in toto. Wasn't the fortran 77 withdrawn because the fortran 90 people didn't want to compete with it? I posted: >> I see no reason this would be any harder than adding extended >> precision types which many have done. The relative lack of interval >> arithmetic extensions indicates to me that most people believe it is >> less useful than extended precision arithmetic. Why should a >> standards committee take it upon itself to overrule the collective >> judgement of the fortran community by including interval arithmetic >> in the standard. Craig Burley commented: >Well, I'm not crazy about the way the Fortran standard has evolved >either, so I'm not going to argue with you about that. I think >your question in the latter sentence could be asked about all >sorts of features added for Fortran 90 and, now, F2K. (Half-baked >stuff like CONTAINS should have really been thought through better... >finally, more and more people are seeing the subtly buggy effects >they have on their ongoing Fortran development, too bad they got added >to the standard *before* people find out about these subtle effects, >and now it's too late to fix most of them.) So why not learn from past mistakes? I posted: >> You are pretty quick to throw around words like "stupid" >> considering you have conceded you don't really know anything about >> the subject being discussed. Craig Burley responded: >I didn't *call* anyone "stupid". You seemed to be implying that >IA was useless, for a variety of reasons, including that people >won't know how to use it properly *or* that they'd always thus >know enough to use the underlying REAL type *at least* as >effectively as having IA. I used the word "stupid" to paraphrase >this apparent contradiction of *yours*. Since it is harder to use IA effectively then ordinary computer arithmetic, I see no contradiction. Craig Burley continued: >It is hard for me to tell, at *this* point, just what you *are* >objecting to. If it's just the notion that the evolving >standard will include a new facility before it's proven in the >field, fine, say that and be done with it -- I agree wholeheartedly >with you on that. But you've said lots of other things that >suggest to me you consider at least *some* of the above people >to be "stupid", or me to be stupid to believe any of the above >might actually be facts. (Maybe I am, maybe they're not, >but it's a pretty good scam then! And, BTW, I don't believe >aliens landed in Roswell, either, but then, nobody's offering >me $$ to add support for alien-language constructs in a >Fortran compiler.) Certainly I object to putting unproven features in the standard. I also believe the benefits of IA have been greatly overstated. I posted: >> Most users do not invent algorithms, they implement >> algorithms found in a textbook or other source. These algorithms >> are designed to compute valid answers (where possible) using >> standard computer arithmetic. They are not designed to work well >> when converted to intervals (a much harder problem) and often >> will not. Craig Burley responded: >What about *new* algorithms that are designed to work *perfectly*, >or at least much *better*, than their predecessors *assuming >Fortran supports IA*? Are you saying the number of such >algorithms, say, another 50 years into the future, will be >too miniscule to be worth doing IA *now*? That's a remarkable >assertion, if so. These new algorithms do not currently exist. I doubt they will ever exist. In any case the time to put IA in the standard is after they are discovered, not before. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: interval arithmetic and standard algorithms From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970807.182837.268@yktvmv.watson.ibm.com> Date: Thu, 7 Aug 1997 22:28:37 GMT References: <1997Aug621.25.41.9307@koobera.math.uic.edu> D. J. Bernstein asked: >Now, which standard algorithms were you thinking of that won't work well >with intervals? Gaussian elimination (with partial pivoting) for the solution of systems of linear equations for one. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970807.183459.525@yktvmv.watson.ibm.com> Date: Thu, 7 Aug 1997 22:34:59 GMT References: <19970804.141635.393@yktvmv.watson.ibm.com> <33E89CAD.41C6@maths.nott.ac.uk> I asked: >> How much effort are you prepared to force (by putting IA in >> the fortran standard) people to expend proving beyond any doubt that >> IA is a turkey? Dr A. N. Walker replied (in part): > But how much effort *is* it? Especially at a time when >Fortran compilers are being extensively re-written for the new >standard anyway. For comparison, support for rationals in Algol >can be added in about 60 lines of code Lindsey & vdMeulen; it >won't be so easy in Fortran, but I'd be surprised if it took a >competent compiler-writer more than a couple of days. After that, >its a "quality of implementation" issue as to how much time you >want to spend on doing it better optimisation, etc.. Well suppose we ask Craig Burley for his estimate. I asked: >> What proof would you accept? In my opinion the IA >> support in the IEEE standard is already more support than IA deserves. Dr A. N. Walker replied (in part): > Previously, there's been a chicken and egg problem. If Fortran >lays the egg, then at least we can see what emerges. If no major >language ever does it, then we'll never know. Well interval arithmetic support was put into IEEE. Noone uses it. Undaunted the IA cultists want to put it in fortran. I doubt the IA cultists will consider lack of use proof of anything. They will say the implementations were inadequate or the library writers didn't support it properly or that the standard adopted was ill considered or that fortran is a stupid language. IA is not a new idea. An algol compiler with support for a variant of IA (triplex-algol) was produced over 30 years ago. It has had plenty of time to prove itself generally useful and has failed to do so. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970808.140838.789@yktvmv.watson.ibm.com> Date: Fri, 8 Aug 1997 18:08:38 GMT References: <19970807.183459.525@yktvmv.watson.ibm.com> I posted: >> Well interval arithmetic support was put into IEEE. Noone >> uses it. Jan Vorbrueggen replied: >This is simply untrue. So I exaggerated a little for effect. What I meant of course is the alternative rounding modes in IEEE are not widely used. No one seems to be disputing this. Actually, if the truth be known, I have used round to zero mode myself in a random number routine. I did have trouble with the compiler moving the mode switch call past the arithmetic. (It did not occur to me, as another poster suggests, that the operating system might feel free to trash the mode bit.) James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970808.143352.885@yktvmv.watson.ibm.com> Date: Fri, 8 Aug 1997 18:33:52 GMT References: <19970807.183459.525@yktvmv.watson.ibm.com> <54afisyd75.fsf@rrdjazz.nist.gov> I posted: >> Well interval arithmetic support was put into IEEE. Noone >> uses it. Undaunted the IA cultists want to put it in fortran. I Przemek Klosowski replied: >I don't mind hearing an occasional opinion, but _this_ is a downright >biased and unfair. As you well know, the support of most nontrivial >aspects of IEEE (exceptions, rounding, out-of-band/denormalized >numbers) is pathetic, and even non-existent at times. ... What's unfair? Features should be put into an architecture (or a standard) because they are useful and will be supported not because some enthusiast thinks they are neat. If an architected feature is not useful because it is not properly supported it was probably a mistake to include it. Btw in the case of IEEE arithmetic the poor support was entirely predictable and in no way unexpected. I predict IA in fortran will also be poorly supported. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970808.151329.982@yktvmv.watson.ibm.com> Date: Fri, 8 Aug 1997 19:13:29 GMT References: <19970807.183459.525@yktvmv.watson.ibm.com> <5sedlm$43v$1@goanna.cs.rmit.edu.au> >The IEEE 754 standard was a very good standard. >What Kahan has been complaining about (and what I have been complaining >about) is that the good standard that _was_ adopted has been made >artificially hard to exploit. I disagree, there is a lot of nonsense in the IEEE standard. It became the floating point standard by historical happenstance (similar to the way intel chips became the PC standard). There are major advantages to having any standard, this does not mean everything about the standard is ideal. IEEE does have some good points, there is nothing much wrong with the basic 64 bit format for example. It also has a lot of unnecessary fluff. Besides the four rounding modes there is the remainder instruction for example (expensive and useless). Btw the standard has not been made "artificially" hard to support. People have not gone out of their way to sabotage it, they have just declined to support aspects which seem expensive and useless to them. It is the job of architects to include features users want. It is not the job of users to support every esoteric feature an architect thinks up. Richard A. O'Keefe wrote: >The thing is, without good support at all levels of the system, up to and >including compilers, mode switching can be very expensive. I thought I'd >provide some hard numbers. I wrote a little matrix multiplication thingy >whose only purpose is to do lots of adds and multiplies, and wrote the >obvious code. (Actually, I cheated, and simplified the multiplies because >I knew all the numbers were positive.) The machine I now have access to is >an UltraSPARC with Solaris 2.5.something. provides, amongst >other things, > > fpgetround() -> current rounding mode > fpsetround(new rounding mode) -> old rounding mode > >The task is a simple 100*100 matrix multiplication (without using any >special dot product, just plain operations). I tried SPARCompiler C >4.2 and GCC 2.7.2. I tried each with no options (unoptimised code) >and with the highest optimisation level known to me. GCC had the >benefit of __inline__ annotations on the 'addi' and 'muli' functions, >while Sun's compiler doesn't _need_ annotations to do that. Here are >the times I got. > > 0.22 double, cc > 1.96 interval, cc > > 0.05 double, cc -xO5 > 1.29 interval, cc -xO5 > > 0.19 double, gcc > 1.77 interval, gcc > > 0.06 double, gcc -O6 > 1.51 interval, gcc -O6 > >When you look at what's going on, it's clear why optimisation makes almost >no difference to the interval arithmetic times. Virtually all the time is >going into the three calls of fpsetround() that are necessary. The really >sad thing here is that > > - if the compiler knew what the hell was going on, EACH of these calls > (involving a procedure call and about 15 instructions) could be a > *single* "move to floating point status register" instruction. > - inside loops, at least a third of the move to %fsr instructions > could be eliminated as well. > >Since multiplication is involved, I would accept a factor of 4 or 5 time >penalty for doing interval arithmetic as "good". Since I didn't implement >multiplication fully for this benchmark, I would accept a factor of 2 or >3 as a reasonable slow down. How many people would be willing to put >up with a factor of TWENTY-FIVE TIMES slower? > >Do you call something that slows reasonable straightforward code down >by at least a factor of 8 (25/3) compared with what the hardware can easily >do "SUPPORT"? > >Before anyone can honestly claim that interval arithmetic has been >disused *on merit* rather than *price*, they need to point to a system >where the attained speed of interval arithmetic was decently close to >what the hardware could do. So what happens if you ignore the other rounding modes entirely and just use IEEE nearest to support intervals. This is easy if you forget about getting the tightest possible intervals. Let D=1-2.**(-53), U=1+2.**(-52). Then assuming as you did that everything is positive, I believe: [a,b] + [c,d] contained in [d*(a+c),u*(b+d)] [a,b] * [c,d] contained in [d*(a*c),u*(b*d)] Something similar will work in general. Your intervals will be a bit wider but not catastrophically so. In any case the difference between a slow down of 3 and a slow down of 25 is irrelevant if both are more than users are willing to accept. Btw the slow down for extended precision arithmetic in software is in this ballpark, nevertheless it is fairly widely used and supported. One might conclude most users think it is more useful. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970808.155731.644@yktvmv.watson.ibm.com> Date: Fri, 8 Aug 1997 19:57:31 GMT References: <5se8lo$sag$1@goanna.cs.rmit.edu.au> Richard A. O'Keefe wrote: >Yes, but the whole point is that you DON'T *USE* simple implementations >of algorithms designed for a different sort of arithmetic. Come ON >people, let's get sensible here! You don't use "simple implementations >of common algorithms" for rational arithmetic when you're using floating >point, because it is a different arithmetic. If you do, disaster strikes. >Why do people insist on holding interval arithmetic up to a standard >(it must work perfectly with poor code) that floating point is not >required to meet? My posts were in response to a claim by Craig Burley that interval arithmetic would allow naive fortran programmers to find problems with their algorithms. It appears we are in agreement that this is unrealistic. Richard A. O'Keefe also wrote (in part): > I have NOT said, have not implied, and don't see why anyone would > think it plausible that they are or might be identical in form to > floating-point algorithms for the same problems Again we agree: Richard A. O'Keefe also wrote (in part): >You can keep on attacking this straw man of your own imagining as much >as you like, but it isn't *useful* to do so except as an attempt to >intimidate people away from interval arithmetic. It certainly isn't in >the least informative. This post was in reply to someone else but I suspect the "your" refers to me. As noted above this "straw man" is not of my imagining but implicit in Craig Burley's claims about how adding IA to fortran will help naive users. As I noted in another post it is such claims that have made me allergic to IA. Richard A. O'Keefe also wrote (in part): > INTERVAL ARITHMETIC IS *HARDER* TO USE THAN FLOATING POINT > ARITHMETIC, BUT IT BUYS YOU MORE. I agree with the first part at least. Richard A. O'Keefe continued: >I don't actually believe (and have never said) that interval arithmetic >should be provided in Fortran or any other language. What I _do_ think >is that it would be nice to be able to get at the *building blocks* >(directed rounding) that the hardware already provides. Fortran 90 and >Ada 95 already give us much of what we need to make programming IA on >top possible: user defined types and overloaded operators. One thing >they _don't_ do is give us _enough_ operators. For example, in addition >to x + y round to nearest > x +< y round towards -oo > x +> y round towards +oo >are needed. (These operations take floats or arrays of floats as >operands.) Ada won't let us introduce new operation symbols at all. >Fortran will, but they have to be specially spelled (.PLSUP. .PLSDN. >or something like that) and cannot have the same precedence as standard >operators. Given such primitives operating on scalars, in either >language we can program the array versions ourselves, although that >would miss out on an important optimisation: the FPU can be switched >into and out of the appropriate mode once per array operation, instead >of once per element. In Ada 95, if only it would let us introduce new >operator spellings as well as overloadings, everything except dot precision >could be user-programmed. (But not as well as if the compiler could track >the mode of the FPU and optimise mode switching.) Actually I might not object to some small cheap changes of this sort. As for mode switching this could be avoided entirely if you were a bit sloppy about the intervals as noted above. Richard A. O'Keefe continued: >People who think that interval arithmetic is too dangerous to have around >should campaign for IEEE 754/854 (or IEC 5whatsitwhatsit) to be revised to >eliminate rounding modes, so that architects can legitimately remove them. I do think rounding modes (among other things) should be eliminated from the IEEE standard, but because they are useless not because they are dangerous. Btw you could still do interval arithmetic as noted above. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: interval arithmetic and standard algorithms From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970808.163027.559@yktvmv.watson.ibm.com> Date: Fri, 8 Aug 1997 20:30:27 GMT References: <1997Aug621.25.41.9307@koobera.math.uic.edu> <19970807.182837.268@yktvmv.watson.ibm.com> <1997Aug819.28.11.4427@koobera.math.uic.edu> I wrote: >> Gaussian elimination (with partial pivoting) for the solution >> of systems of linear equations for one. D. J. Bernstein replied: >That is definitely not an algorithm that will ``compute valid answers >(where possible) using standard computer arithmetic.'' So what, you asked: >Now which standard algorithms were you thinking of that won't work well >with intervals? As for my original statement, I said algorithms are designed to compute valid answers (where possible) using standard computer arithmetic. Perhaps I should have said the goal of standard algorithms is to compute valid answers (where possible) using standard computer arithmetic. In practice Gaussian elimination with partial pivoting works well. The answer is unreliable if the matrix is ill-conditioned but this is to be expected. I believe there are also some pathological examples where problems arise because of exponential growth in the pivots but this is not seen in practice and is easily detected in any case. (I believe it is a conjecture that these pathological cases are not possible with complete pivoting, but most users are not willing to bear the added cost.) Perhaps you might quit nitpicking and explain how interval arithmetic does a better job of solving systems of linear equations than ordinary arithmetic. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: interval arithmetic and standard algorithms From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970809.001533.712@yktvmv.watson.ibm.com> Date: Sat, 9 Aug 1997 04:15:33 GMT References: <19970808.163027.559@yktvmv.watson.ibm.com> <1997Aug902.12.17.10675@koobera.math.uic.edu> I wrote: >> In practice Gaussian elimination with partial pivoting works well. D. J. Bernstein replied: >Yes, most of the time, if your matrices are small. Small here means less than 10**9 or so if the condition number is good. I believe there is a factor of n (where n is the problem size) in the error term. So for with a problem size of 10**9 you may lose 30 bits or so. Starting with 52 bits (IEEE double) and small condition number this should leave some good bits in the answer. Iterative improvement (a n**2 process) can then be used to improve the accuracy of the answer as needed. Of course solving a dense system of size 10**9 is not practical because it would take too long and require too much storage. However people can and do solve dense systems of size 10**5 or so. Solving a system of size 1000 is routine taking just a few seconds. D. J. Bernstein continued: >And a naive interval adaptation also produces fairly small intervals, >most of the time, if your matrices are small. Small here does not mean 10**9 or even 1000. The problem is that the intervals are growing exponentially wider with n. I think you will be in big trouble even for problems of size a few hundred. (I believe interval arithmetic fails here for the same reason that forward error analysis gives poor bounds. It required the invention of backward error analysis to explain the unexpectedly good performance of Gaussian elimination with partial pivoting in practice.) I wrote: >> Perhaps you might quit nitpicking and explain how interval >> arithmetic does a better job of solving systems of linear equations >> than ordinary arithmetic. D. J. Bernstein replied: >I'm not sure what you're asking. The results aren't even of the same >type: interval arithmetic produces bounds, whereas ordinary arithmetic >produces numbers. It was suggested that naive programmers could check the validity of their algorithms by translating them into interval arithmetic. I am claiming this is not the case since the original algorithms can be perfectly ok whereas the interval arithmetic version fails badly. I claim Gaussian elimination with partial pivoting is such an example. More generally it has been claimed that interval arithmetic allows better algorithms to be developed. So I am asking what better algorithm (in a practical sense) for solving dense systems of linear equations can be produced using interval arithmetic. Btw Gaussian elimination can be modified (cheaply) to yield estimated condition numbers. This allows error estimates for the numbers produced (which most people seem to find satisfactory). James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970821.170352.926@yktvmv.watson.ibm.com> Date: Thu, 21 Aug 1997 21:03:52 GMT References: <19970808.155731.644@yktvmv.watson.ibm.com> Craig Burley wrote: >What *will* be fun, and informative, once IA gets implemented in >a few compilers (maybe in a few years?), is when somebody gets >the bright idea of analyzing *existing* production Fortran code >to determine their numeric "correctness" by making straightforward >translations of relevant portions of it to IA-Fortran. It will >be interesting to see what percentage of code they analyze turns >out to have coding errors that IA helps them find, and thus might >well have helped the original programmers find, had it been >available to them. I'd feel better about IA if that percentage >turned out to be more than, say, 2%, but if it's non-zero, maybe >that'll be enough for some people to justify the effort to add IA >to Fortran. If it saves even one life, I'd say it's worth putting >in; especially given the $$ we Americans (in the States, anyway ;-) >spend, or force others to spend, on very questionable theories >regarding what might or might not shorten somebody's life somewhere, >somehow, compared to which the investment needed to add IA seems >fairly minimal. Typical production fortran codes contain things which cannot be straightforwardly translated to IA-fortran (if one expects meaningful results). For example how do you straightforwardly handle floating compares, conversion of floats to integers, complex numbers (it is my understanding that the proposed standard will not include complex intervals) etc. So the above makes no sense. It is true that existing production codes contain errors and almost any method of analyzing such codes is likely to uncover errors. This does not make almost any method cost-effective. I posted: > Btw you could still do interval arithmetic as noted above. Craig Burley responded: >I'm not sure why that matters, if IA is as useless as you claim. >Seems to me there are people who don't need IA but are happily >using directed rounding modes in their IEEE 754 implementations, >but I might be wrong. I believe support for interval arithmetic was the primary justification for the directed rounding modes. It also matters because it adds support to the claim that IA is useless. For example people have coded software extended precision for machines without hardware support for extended precision. The lack of equivalent effort to support IA indicates its comparative uselessness. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970821.173906.341@yktvmv.watson.ibm.com> Date: Thu, 21 Aug 1997 21:39:06 GMT References: Craig Burley posted: >Uhhhh...okay, so you're saying it's reasonable to use simple floating-point >arithmetic as long as one is happy with an incorrect result? Sorry, >but you've lost me on this one. Floating point arithmetic does not claim to produce exact results. This does not mean it is unreasonable to use it. Craig Burley posted: >If you're trying to say something *other* than that, I'd sure like >to know what, and what evidence you have to support it. Even knowing >where you got the definitive info that the example posted was >"extremely contrived" -- the people who first showed me that example >didn't say this, and in fact didn't seem to think it was, but, then, >they were promoters of IA. I imagine there is a lot that the promoters of IA didn't tell you. It is fairly obvious that the example was contrived. If you knew something about numerical computation you could see this. Craig Burley posted: >My whole point (and, yes, it's worth you're knowing -- I basically >*started* this thread by mentioning IA in the first place ;-) was >that, of all the features added to the Fortran morass lately, IA >seemed to be one of the few that actually had a hope of delivering >more correct answers, or maybe fewer incorrect ones, in the end. Since when have fortran users been asking for more correct answers? By and large they want faster answers. You might think about giving users what they want rather than what you (who don't know anything about the subject) think they should want. Craig Burley posted: >Seems like a good use of resources to me. A comparative handful of >people, probably many fewer than the number of Yale mathematicians >on the planet, add IA to Fortran and other such languages, and everyone >gets to use it on all the Pentiums, Alphas, UltraSPARC, m68ks, and >so on out there, which *clearly* outnumber mathematicians and surely >waste much less time writing papers and posting to USENET. And >when the occasional problem comes along that IA flags by saying "my >naive approach to this doesn't yield a useful answer", one simply >hires a mathematician to do the work. Once again you are ignoring the common situation (for production codes not toy examples) where IA will incorrectly flag useful answers. Craig Burley posted: >It's not my field, but then, code generation for computers *is* my >field, and it works pretty much the same way; when the straightforward, >naive tools to do code generation don't "cut it" for a particular, >rare problem, e.g. by generating programs that take too long to >run, they hire people like me to really "solve" the problem, sometimes >requiring hand-coded assembly. It'd be nice if the vanilla tools >people used today could say things like "this program will take >between 1ms and 2B years to run", though, kinda like IA's useless >answers. (Or, more properly, "this program will take O(9.5nn) >seconds to run for an input file n bytes long", I suppose. ;-) >I wouldn't oppose the deployment of such tools any more than I >now oppose the deployment of IA. So do you refuse to use quick sort or hashing in your code because they perform badly in rare cases? If somebody contrived an example which compiled slowly because all the variable names had the same hash key and presented it as realistic would you consider this a useful and helpful criticism of the compiler? James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: interval arithmetic and standard algorithms From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970821.182151.010@yktvmv.watson.ibm.com> Date: Thu, 21 Aug 1997 22:21:51 GMT References: <1997Aug1104.25.03.2399@koobera.math.uic.edu> D. J. Bernstein posted: >I'm merely responding to your comment that textbook algorithms ``compute >valid answers (where possible) using standard computer arithmetic.'' I will amend my comment to "attempt to compute ... " if this will make you happier. D. J. Berstein posted: >Gaussian elimination is a counterexample. It is tremendously unsafe for >large matrices, though it is a useful tool in the hands of an expert >numerical analyst. In what way is Gaussian elimination particularly unsafe for large matrices? I asked >> So I am asking what better >> algorithm (in a practical sense) for solving dense systems of linear >> equations can be produced using interval arithmetic. D. J. Bernstein posted: >Once again I'm not sure what you mean. > >There are moderately fast algorithms that will find the solution with >guaranteed high precision. Some of them use intervals, but of course >they can still be programmed in languages that don't support intervals. Most numerical libraries (LINPACK, LAPACK, etc.) provide routines for solving large systems of linear equations based on Gaussian elimination. You appear to be claiming these routines are "tremendously unsafe" for the average user. So what should they be using instead? James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970823.134002.369@yktvmv.watson.ibm.com> Date: Sat, 23 Aug 1997 17:40:02 GMT References: <19970808.155731.644@yktvmv.watson.ibm.com> <19970821.170352.926@yktvmv.watson.ibm.com> Craig Burley wrote: >> >What *will* be fun, and informative, once IA gets implemented in >> >a few compilers (maybe in a few years?), is when somebody gets >> >the bright idea of analyzing *existing* production Fortran code >> >to determine their numeric "correctness" by making straightforward >> >translations of relevant portions of it to IA-Fortran. It will >> >be interesting to see what percentage of code they analyze turns >> >out to have coding errors that IA helps them find, and thus might >> >well have helped the original programmers find, had it been >> >available to them. I'd feel better about IA if that percentage >> >turned out to be more than, say, 2%, but if it's non-zero, maybe >> >that'll be enough for some people to justify the effort to add IA >> >to Fortran. If it saves even one life, I'd say it's worth putting >> >in; especially given the $$ we Americans (in the States, anyway ;-) >> >spend, or force others to spend, on very questionable theories >> >regarding what might or might not shorten somebody's life somewhere, >> >somehow, compared to which the investment needed to add IA seems >> >fairly minimal. I replied: >> Typical production fortran codes contain things which >> cannot be straightforwardly translated to IA-fortran (if one expects >> meaningful results). For example how do you straightforwardly handle >> floating compares, conversion of floats to integers, complex numbers >> (it is my understanding that the proposed standard will not include >> complex intervals) etc. So the above makes no sense. Craig Burley responded: >"Makes no sense"? You claim that even a non-zero percentage of >cases where the standardized availability of IA could lead to >saving *lives* makes no sense, or are you claiming that the >number of cases would *always* be zero -- that IA would *never* >help discover a latent bug in existing production Fortran code? My claim is that it makes no sense to talk about the benefits of straightforwardly translating production codes to IA-fortran when this cannot be done sensibly in most cases. As for the value of a life saved, this is on the order of 3 million dollars in the US (the FAA uses some such figure for aircraft safety regulations). The cost of putting IA in the fortran standard would be much greater. In any case I am unaware of any cases where numerically incorrect fortran programs have gotten people killed so this seems to be a nonproblem. Also I doubt IA would actually save lives. In my view it is more likely to cost lives by giving ignorant people a false feeling of security. Consider the Ariadane 5 rocket failure, an instructive example of how using supposedly safer methods (ADA rather than fortran) can cause rather than prevent failures. Craig Burley continued: >(I didn't address the question of how to "straightforwardly" handle >the things you mention, because I assume they aren't straightforward >to handle, but that the *algorithms*, at some level, could be >usefully converted to IA without a huge amount of effort, over a >great deal of time, though of course we're talking well beyond >Y2K scale here in terms of actual costs of changing *everything* to >use IA, which is hardly a scenario worth requiring just to justify >IA, any more than modules and interface blocks were added to Fortran >90 on the assumption that all code would be changed to use them, >thus exposing latent bugs...yet, *that* does happen, too, another >thing I know *firsthand*.) OK, how do you convert gaussian elimination with partial pivoting (a rather common algorithm) to IA without a huge amount of effort. I posted: >> It also matters because it adds support to the claim that >> IA is useless. For example people have coded software extended >> precision for machines without hardware support for extended >> precision. The lack of equivalent effort to support IA indicates >> its comparative uselessness. Craig Burley replied: >There *is* effort to support IA. I'd say, offhand, it might be >equivalent; nobody has stepped forward to fund me to add support >for REAL*16 to my compiler, for example, though I do get questions >about it. But I've gotten at least that much interest in my >adding IA to the compiler, FWIW. The IBM fortran compilers support extended precision (the 370 architecture does provide hardware extended precision, the power architecture does not although the fused multiply-add is helpful for software support). I believe many of the rival commercial fortran compilers (DEC, HP, SUN, SGI, CONVEX, CRAY, etc) provide such software support as well. I am unaware of any equivalent support for an IA extension. So your suggestion of equivalent support appears baseless to me. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970829.123841.138@yktvmv.watson.ibm.com> Date: Fri, 29 Aug 1997 16:38:41 GMT References: <19970808.155731.644@yktvmv.watson.ibm.com> <19970821.170352.926@yktvmv.watson.ibm.com> <19970823.134002.369@yktvmv.watson.ibm.com> Craig Burley posted in part: >(I wonder if IA *analysis* of the code for that killer radiation >machine might have exposed the bug that killed, which I've gathered >had to do with a hole in the user interface?) Not likely. I assume you are referring to the Therac-25. The software in question was written by a single individual in PDP-11 assembly language. It appears to have undergone no real review. The particular bugs which caused the problems were timing related. If operator input was received at the wrong time the software became confused. However the entire design appears to have been unsound. I posted: >> Also I doubt IA would actually save lives. In my view it >> is more likely to cost lives by giving ignorant people a false >> feeling of security. Consider the Ariadane 5 rocket failure, an >> instructive example of how using supposedly safer methods (ADA >> rather than fortran) can cause rather than prevent failures. Craig Burley: >You're touching on a *very* sensitive issue here. Essentially >you're saying that the more easy-to-use, friendly, and robust >the environment we give programmers and scientists, the greater >likelihood they'll produce "destructive" code. (That is, I doubt >you're singling out IA here, since IA was irrelevant in the >example you cited; in fact, most everyone who would analyze the >relevant language construct that did cause the fault in terms >of how it'd have likely appeared, and worked, in typical C, C++, >Fortran, and other, language environments, would probably agree that >the Ada version offered the *most* safety, and that the "fault" was >not with using Ada or believing the code was "safe" simply because >Ada was used. I'm undecided on this, having only read what I've >seen posted about this on newsgroups like this, but it seems the >fault was really in some other aspect of the project, not in >using Ada, and it certainly isn't clear that using FORTRAN 77 would >have made the project more robust -- though it might have made >it prohibitively expensive, I suppose, and a rocket you can't >build is one you can't blow up, either.) What I am saying is that an environment is not better just because some ivory tower academic type thinks it should be better in theory. It is better if real world programmers under real world constraints are more productive using it. It may be a bit unfair to blame ADA solely for the failure (although considering the grief fortran has taken for the mythical do 10 j = 1.10 bug I am not going feel very guilty about it) since some of the poor decisions involved had nothing to do with ADA (ie that the software was perfect so there was no need to make it fail gracefully). However as the following excerpt from the inquiry report shows ADA does appear to implicated to some extent. URL: http://www.esrin.esa.it/htdocs/tidc/Press/Press96/ariane5rep.html In the failure scenario, the primary technical causes are the Operand Error when converting the horizontal bias variable BH, and the lack of protection of this conversion which caused the SRI computer to stop. It has been stated to the Board that not all the conversions were protected because a maximum workload target of 80% had been set for the SRI computer. To determine the vulnerability of unprotected code, an analysis was performed on every operation which could give rise to an exception, including an Operand Error. In particular, the conversion of floating point values to integers was analysed and operations involving seven variables were at risk of leading to an Operand Error. This led to protection being added to four of the variables, evidence of which appears in the Ada code. However, three of the variables were left unprotected. ... I asked: >> OK, how do you convert gaussian elimination with partial >> pivoting (a rather common algorithm) to IA without a huge amount of >> effort. Craig Burley responded: >I don't know; I don't know if it'd even be worthwhile to do so. >How do you convert it to Fortran 90 without a huge amount of effort? >That is, complete with modules, array assignment, and so on? Since >I gather the complexity of the code is really in the algorithm, >not the coding, I assume that'd be easier; whereas for lots of Fortran >code, the complexity is in the code, not the algorithm, so I'd guess >that converting it to IA would be *easier* than converting it to >Fortran 90. (My point is that as long as we're adding so many of >these *other* facilities to Fortran, IA might not be such a waste >of time to add as well; it might offer a rare opportunity to get >better results than many or most of those other facilities, which >are probably just as expensive as IA.) The algorithm is simple. Converting it to IA is simple as long as the IA data type includes the regular arithmetic value. This can be done by expressing intervals as x+-b or as b1Can we close this thread with your agreeing to my original contention >that, of all the new Fortran features, IA is somewhat unique in >that it at least *attempts* to offer some means for getting better >*numeric* results? Or at least would you concede that IA offers a >higher likelihood than, say, standardizing a means for obtaining >command-line arguments, for getting correct numeric results? (Remember >to apply *all* your reasons IA will be useless to the other Fortran >features, e.g. the ability to obtain command-line arguments, before >answering.) I am mercifully unaware of the other proposed fortran features. (I have not even learned much about fortran 90.) If you say some are even stupider than IA I can't really argue. However I don't consider this a very good reason for backing putting IA in the fortran standard. As for a standard way of obtaining command line arguments, what's wrong with that? Users ask for it and some compilers provide it already. Seems like a natural candidate for standardization. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970829.135105.143@yktvmv.watson.ibm.com> Date: Fri, 29 Aug 1997 17:51:05 GMT References: <19970808.155731.644@yktvmv.watson.ibm.com> <19970821.170352.926@yktvmv.watson.ibm.com> <19970823.134002.369@yktvmv.watson.ibm.com> <5ttvt3$pq4$1@goanna.cs.rmit.edu.au> I posted: >> OK, how do you convert gaussian elimination with partial >>pivoting (a rather common algorithm) to IA without a huge amount of >>effort. Richard A. O'Keefe replied: >This is a rather dreadful straw man argument, isn't it? >It has already been stated repeatedly that you _wouldn't_. >It has already been stated repeatedly that the proponents of interval >arithmetic *don't* claim that simply replacing 'REAL' by 'INTERVAL' >will yield major improvements. >It has already been stated repeatedly that, just as floating point >warrants and enables different algorithms from fixed point, so >interval arithmetic warrants and *enables* different algorithms >from floating point. So explain all this to Burley. He's the one who keeps claiming IA will expose problems in current production code via "straightforward" conversion to IA. Richard A. O'Keefe continued: >The point is not that a naive hacker's Gaussian elimination with >partial pivoting would convert automatically into wonderful interval >code, but that a *slightly* less naive hacker would change > REAL X(M), B(N), A(N, M) > ... > CALL RSOLVE(A, X, B) > ... >where someone _else_ wrote the real matrix solver to > INTERVAL X(M), B(N), A(N, M) > ... > CALL RISOLVE(A, X, B) > ... >where someone _else_ wrote an interval matrix solver (using whatever >good algorthm they chose, there are several in the literature, including >a couple that don't need extremely high precision), and then they would >get more informative results. Substituting library subroutines in this fashion is often not at all "straightforward" especially if someone else wrote the original code. Craig Burley posted: >>>There *is* effort to support IA. I'd say, offhand, it might be >>>equivalent; nobody has stepped forward to fund me to add support >>>for REAL*16 to my compiler, for example, though I do get questions >>>about it. But I've gotten at least that much interest in my >>>adding IA to the compiler, FWIW. I replied: >> The IBM fortran compilers support extended precision >>(the 370 architecture does provide hardware extended precision, the >>power architecture does not although the fused multiply-add is >>helpful for software support). I believe many of the rival commercial >>fortran compilers (DEC, HP, SUN, SGI, CONVEX, CRAY, etc) provide such >>software support as well. I am unaware of any equivalent support for >>an IA extension. So your suggestion of equivalent support appears >>baseless to me. Richard A. O'Keefe continued: >Clearly, you can't read. He didn't say that there _is_ equivalent support, >only that the *effort* "might be equivalent", which I understood to mean >that the work required to support IA might be about as much as the work >required to support extended precision. Your reading is not supported by the context of Burley's statement (which you deleted). Also I believe Burley replied without objecting to my interpretation. Perhaps your difficulty stems from the clear absurdity of Burley's statement. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: Interval Arithmetic (Was Re: Object orientation without ...) From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch,comp.lang.misc Message-ID: <19970829.140924.801@yktvmv.watson.ibm.com> Date: Fri, 29 Aug 1997 18:09:24 GMT References: <19970808.155731.644@yktvmv.watson.ibm.com> <19970821.170352.926@yktvmv.watson.ibm.com> <19970823.134002.369@yktvmv.watson.ibm.com> I posted: >> Also I doubt IA would actually save lives. In my view it >>is more likely to cost lives by giving ignorant people a false >>feeling of security. Consider the Ariadane 5 rocket failure, an >>instructive example of how using supposedly safer methods (ADA >>rather than fortran) can cause rather than prevent failures. Ed Dengler replied: >Sorry, I don't buy this. While it would have been nicer _not_ to have a >failure, I would rather a system _knew_ it had a problem and stopped in >an appropriate manner (such as the self-destruct sequence of the rocket >upon detection of computer failure, which is reasonable behaviour) than >to have it continue in an inappropriate state and have it cause more severe >problems (such as incorrect attempts to correct the "erroneous" flight which >may cause the rocket to strike the ground). First, as pointed out by Craig Burley, it was the Ariane 5. Second your scenario is not what happened. From the report of the inquiry board. URL: http://www.esrin.esa.it/htdocs/tidc/Press/Press96/ariane5rep.html e) At 36.7 seconds after H0 (approx. 30 seconds after lift-off) the computer within the back-up inertial reference system, which was working on stand-by for guidance and attitude control, became inoperative. This was caused by an internal variable related to the horizontal velocity of the launcher exceeding a limit which existed in the software of this computer. f) Approx. 0.05 seconds later the active inertial reference system, identical to the back-up system in hardware and software, failed for the same reason. Since the back-up inertial system was already inoperative, correct guidance and attitude information could no longer be obtained and loss of the mission was inevitable. g) As a result of its failure, the active inertial reference system transmitted essentially diagnostic information to the launcher's main computer, where it was interpreted as flight data and used for flight control calculations. h) On the basis of those calculations the main computer commanded the booster nozzles, and somewhat later the main engine nozzle also, to make a large correction for an attitude deviation that had not occurred. i) A rapid change of attitude occurred which caused the launcher to disintegrate at 39 seconds after H0 due to aerodynamic forces. j) Destruction was automatically initiated upon disintegration, as designed, at an altitude of 4 km and a distance of 1 km from the launch pad. Ed Dengler continued: >It was silly of them to place software in a rocket without adequate testing. >But it was sure nice to find out that the use of a reasonable language to >catch out-of-bound errors actually worked. Or would you have the rocket >continue its flight when it clearly no longer had accurate information >on which to base its flight control? Do you think that just programming >in Fortran would have caught this problem at some point in the cycle? The conversion overflow was harmless. Hence there would have been no problem with most fortran compilers (fortran does not require an exception here and most compilers won't give one). Whatever the merits of the ADA philosophy in general, in this case reporting, rather than ignoring, the conversion overflow caused the failure. More from the report of the inquiry board: * The internal SRI software exception was caused during execution of a data conversion from 64-bit floating point to 16-bit signed integer value. The floating point number which was converted had a value greater than what could be represented by a 16-bit signed integer. This resulted in an Operand Error. The data conversion instructions (in Ada code) were not protected from causing an Operand Error, although other conversions of comparable variables in the same place in the code were protected. * The error occurred in a part of the software that only performs alignment of the strap-down inertial platform. This software module computes meaningful results only before lift-off. As soon as the launcher lifts off, this function serves no purpose. still more from the report: Although the failure was due to a systematic software design error, mechanisms can be introduced to mitigate this type of problem. For example the computers within the SRIs could have continued to provide their best estimates of the required attitude information. There is reason for concern that a software exception should be allowed, or even required, to cause a processor to halt while handling mission-critical equipment. Indeed, the loss of a proper software function is hazardous because the same software runs in both SRI units. In the case of Ariane 501, this resulted in the switch-off of two still healthy critical units of equipment. James B. Shearer ========================================================================= Path: yktvmv!jbs Subject: Re: 80*86 and IEE 754 From: jbs@yktvmv.watson.ibm.com Organization: IBM Newsgroups: comp.arch Message-ID: <19971029.192037.286@yktvmv.watson.ibm.com> Date: Thu, 30 Oct 1997 00:20:37 GMT References: <63154h$kep$1@goanna.cs.rmit.edu.au> In article , on 29 Oct 1997 12:09:18 -0500, Craig Burley writes: >If I understand one Java requirement correctly, it's that a Java >implementation yields the exact same results given the same portable >Java code regardless of underlying machine. I have some idea how >useful that could be *especially* regarding floating-point issues >(e.g. rendering engines, such as PostScript, running on heterogenous >networks all computing the same results). The problem is this exact results requirement will cause a significant performance penalty on the disfavored machines. It isn't just Intel, the fused multiply-add would be prohibited hurting performance on IBM machines (and I believe HP). This will impede acceptance of Java among users who care about performance. James B. Shearer