lowj_ltd@uhura.cc.rochester.edu (John Alan Low) (12/30/89)
I am having a problem with Turbo Pascal 4.0. The repeat loop in the following
loop never terminates.
Program Foo;
var x : real;
Begin
x := 0.10;
Repeat
x := x + 0.01;
Until x = 0.30;
End.
The Boolean expression is never true. I inserted a writeln(x) and watched as
it took on values .... 0.28, 0.29, 0.30, 0.31, ...
I inserted a writeln(x = 0.30) and it was always FALSE.
What the heck is wrong here? Any ideas? I solved the problem by multiplying x
by 10 and truncating, and testing to see if it was equal to 3, but geez,
how ridiculous.
---Travis
Ich suche die Leidenschaft, die keine Leiden schafft.silvert@cs.dal.ca (Bill Silvert) (12/30/89)
In article <4658@ur-cc.UUCP> lowj_ltd@uhura.cc.rochester.edu (John Alan Low, aka "Travis" Low) writes: >I am having a problem with Turbo Pascal 4.0. The repeat loop in the following >loop never terminates. > >Program Foo; >var x : real; >Begin >x := 0.10; > Repeat > x := x + 0.01; > Until x = 0.30; >End. You should never check for equality with reals. Computers do their math in binary, not decimal, and 0.30 is a continuing binary fraction. Change the test to: > Until x >= 0.30; or, better, to > Until x >= 0.2999; -- Bill Silvert, Habitat Ecology Division. Bedford Institute of Oceanography, Dartmouth, NS, Canada B2Y 4A2 UUCP: ...!{uunet,watmath}!dalcs!biomel!bill Internet: bill%biomel@cs.dal.CA BITNET: bill%biomel%dalcs@dalac
linden@adapt.Sun.COM (Peter van der Linden) (12/31/89)
> Reply-To: lowj_ltd@uhura.cc.rochester.edu (John Alan Low, aka "Travis" Low) > The repeat loop in the following loop never terminates. > Program Foo; > var x : real; > Begin > x := 0.10; > Repeat > x := x + 0.01; > Until x = 0.30; > End. Another programmer discovers inexact representation of decimals as binary reals! What is happening is that your literals are not *exactly* representable as binary floating point numbers. Hence the loop termination test is never satisfied. The routines that print, also round, so you never saw this. You can change the test to "until x >= 0.30" instead of multiplying. If you have access to a Sun system, read the "Floating Point Programmers Guide" (purple tab in the docu-box). ---------------- Disclaimer: I'm no Jack Kennedy, but I'm no Dan Quayle either. Peter van der Linden linden@SuN.cOm (415) 336-6206
lowj_ltd@uhura.cc.rochester.edu (John Alan Low) (12/31/89)
In article <4658@ur-cc.UUCP> I wrote: >I am having a problem with Turbo Pascal 4.0. The repeat loop in the following >loop never terminates. >Program Foo; >var x : real; >Begin >x := 0.10; > Repeat > x := x + 0.01; > Until x = 0.30; >End. Thanks to everybody who emailed me on this. I forgot that 0.01 is a repeating decimal in binary. I never will again. For those who are as mystified as I was: Since 0.01 cannot be represented as a non-repeating decimal in binary, there is a floating point roundoff error. So x is never equal to 0.30, just very close. Strangely enough, although I put no formatting in the writeln statement, I missed the error. I don't know if it showed up at all, I was very tired when I wrote it. The two simplest solutions were: 1) replace the terminating condition with "Until x >= 0.30". 2) replace the terminating condition with "Until abs(x - 0.30) < delta", where delta is some predetermined error factor. The best solution in terms of speed was: Make x an integer (start at 10) and increment by 1 each time. Where x is used in the loop, subsitute x/100. Terminate when x = 30. Thanks again for all the help. (Boy, do I feel stupid) ---Travis Ich suche die Leidenschaft, die keine Leiden schafft.
silvert@cs.dal.ca (Bill Silvert) (12/31/89)
In article <4660@ur-cc.UUCP> lowj_ltd@uhura.cc.rochester.edu (John Alan Low, aka "Travis" Low) writes: > The best solution in terms of speed was: > Make x an integer (start at 10) and increment by 1 each time. Where > x is used in the loop, subsitute x/100. Terminate when x = 30. Just for the record, if you substitute 0.01*x it will run faster. -- Bill Silvert, Habitat Ecology Division. Bedford Institute of Oceanography, Dartmouth, NS, Canada B2Y 4A2 UUCP: ...!{uunet,watmath}!dalcs!biomel!bill Internet: bill%biomel@cs.dal.CA BITNET: bill%biomel%dalcs@dalac
amull@Morgan.COM (Andrew P. Mullhaupt) (01/01/90)
In article <1989Dec31.145504.2373@cs.dal.ca>, silvert@cs.dal.ca (Bill Silvert) writes: > In article <4660@ur-cc.UUCP> lowj_ltd@uhura.cc.rochester.edu (John Alan Low, aka "Travis" Low) writes: > > The best solution in terms of speed was: > > Make x an integer (start at 10) and increment by 1 each time. Where > > x is used in the loop, subsitute x/100. Terminate when x = 30. > > Just for the record, if you substitute 0.01*x it will run faster. This is a case where the program transformation called 'Reduction of Strength' will improve the speed of your program. The idea is that when an arithmetic progression of numbers is required in a loop, that it is faster to generate the progression by the recurrence x(k) = x(k-1) + d where d is the common difference, than by the multiplicative formula x(k) = x(1) + d * (k-1) which requires multiplication. There are many machines, (Especially the Cray computers or the newer RISC machines on which integer multiplies are considerably slower than other instructions. It is one of the advantages of the loop invariant - monotone function style of loop construction that these optimizations often suggest themselves when the code is written in this way. Later, Andrew Mullhaupt
wsinkees@lso.win.tue.nl (Kees Huizing) (01/03/90)
lowj_ltd@uhura.cc.rochester.edu (John Alan Low) writes: >In article <4658@ur-cc.UUCP> I wrote: >>I am having a problem with Turbo Pascal 4.0. The repeat loop in the following >>loop never terminates. >>Program Foo; >>var x : real; >>Begin >>x := 0.10; >> Repeat >> x := x + 0.01; >> Until x = 0.30; >>End. > Thanks to everybody who emailed me on this. I forgot that 0.01 is a > repeating decimal in binary. I never will again. > .... > Thanks again for all the help. (Boy, do I feel stupid) ^^^^^^^^^^^^^^^^^^^^^ It's not you that is stupid, it's (Turbo?) Pascal. Is it not the purpose of a high level pogramming language to hide the funny details of implementation and representation for the user? As it shows, the equality operator "=" does not on reals what it pretends to do. I accept that it cannot detect perfect equality of reals, but what it could do is detect equality upto some representation dependent accuracy. Why is it not done this way? Kees -- Kees Huizing - Eindhoven Univ of Techn - Dept Math & Comp Sc - The Netherlands DOMAIN: wsinkees@win.tue.nl BITNET: wsdckeesh@heitue5 FAX: +31-40-436685
lowj_ltd@uhura.cc.rochester.edu (John Alan Low) (01/04/90)
In article <803@tuewsd.lso.win.tue.nl> wsinkees@lso.win.tue.nl (Kees Huizing) writes: >>In article <4658@ur-cc.UUCP> I wrote: >>>Program Foo; >>>var x : real; >>>Begin x := 0.10; >>> Repeat >>> x := x + 0.01; >>> Until x = 0.30; End. >It's not you that is stupid, it's (Turbo?) Pascal. Is it not the purpose of >a high level pogramming language to hide the funny details of implementation >and representation for the user? As it shows, the equality operator >"=" does not on reals what it pretends to do. I accept that it cannot >detect perfect equality of reals, but what it could do is detect equality >upto some representation dependent accuracy. >Why is it not done this way? After I read this, I compiled the program with the Turbo Pascal 3.0 turbobcd.com compiler. Guess what? The loop terminates nicely. Also, expressions such as 1/3 + 2/3 come out equal to 1.0. So the binary- coded representation of decimals works nicely, and the "=" works the way it's supposed to. Is there some reason this representation is not common practice? Can anybody shed some light on this? I think that later versions of Turbo Pascal do not implement this representation, so there must be some good reason, right? ---Travis Ich suche die Leidenschaft, die keine Leiden schafft.
linden@adapt.Sun.COM (Peter van der Linden) (01/04/90)
Kees Huizing - Eindhoven Univ of Techn - The Netherlands, wants to know: > the equality operator "=" does not (do) on reals what it pretends to do. > I accept that it cannot detect perfect equality of reals, but what it could do > is detect equality up to some representation dependent accuracy. > Why is it not done this way? A very reasonable question Kees! A number of years ago, a gentleman by the name of Dijkstra, located not a million miles from where you are, had the very same thought, and implemented it into an early Algol compiler. The experiment was soon deemed a failure when it was found that this had the inadvertent and unwanted side effect that comparison was no longer transitive. I.e. if A equalled B, and B equalled C, a program could not conclude that A = C ! ---------------- Disclaimer: I'm no Jack Kennedy, but I'm no Dan Quayle either. Peter van der Linden linden@SuN.cOm (415) 336-6206
jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) (01/04/90)
From article <129838@sun.Eng.Sun.COM>, by linden@adapt.Sun.COM (Peter van der Linden): > Kees Huizing - Eindhoven Univ of Techn - The Netherlands, wants to know: >> the equality operator "=" does not (do) on reals what it pretends to do. >> I accept that it cannot detect perfect equality of reals, but what it >> could do is detect equality up to some representation dependent accuracy. > > A very reasonable question Kees! A number of years ago, a gentleman by the > name of Dijkstra, ... had the very same thought ... > > The experiment was soon deemed a failure when it was found that this had > the inadvertent and unwanted side effect that comparison was no longer > transitive. I.e. if A equalled B, and B equalled C, a program could not > conclude that A = C ! It's worse than that! The PLATO system at the U. or Illinois implemented comparison this way. They had good motives: They didn't want to have to explain to non-numerically-literate users why, for example, 0.1*100.0 wasn't equal to 10.0. It avoided such complaints, but it produced awful results when you tried to code many standard numerical algorithms. For example: If the equality test is modified as above, but the > and < tests are unmodified, it is possible that two of A=B, A<B and A>B may be true at the same time (although only one of A<B or A>B may be true). This leads to a real mess. If you modify all comparison operators so that only one of A<B, A=B, or A>B will be true, comparisons are suddenly misleading. A<=B means (A<B or A=B) and it is consistent with not(A>B), but suddenly, there are values of A and B such that A<=B is reported as true, but in fact, A is slightly greater than B. As a result, there are values of A and B where A<=B is reported to be true, ((A-B)*10)>0 is also reported as true.
dmurdoch@watstat.waterloo.edu (Duncan Murdoch) (01/04/90)
In article <4679@ur-cc.UUCP> lowj_ltd@uhura.cc.rochester.edu (John Alan Low, aka "Travis" Low) writes: > After I read this, I compiled the program with the Turbo Pascal 3.0 > turbobcd.com compiler. Guess what? The loop terminates nicely. Also, > expressions such as 1/3 + 2/3 come out equal to 1.0. So the binary- > coded representation of decimals works nicely, and the "=" works the > way it's supposed to. It's not surprising that the original sum of 0.01's came out exact, because they can be represented exactly in BCD. I think you were just lucky with the other one - you probably added 0.3...33 + 0.6...67 and got 1. You might try it again adding 3 copies of 1/3, and should get 0.999... > > Is there some reason this representation is not common practice? > Can anybody shed some light on this? I think that later versions of > Turbo Pascal do not implement this representation, so there must be > some good reason, right? You're right about recent (4.0+) versions of TP. You can get them in the Turbo Professional library from Turbopower, if you want. Duncan Murdoch
ts@uwasa.fi (Timo Salmi LASK) (01/04/90)
In article <803@tuewsd.lso.win.tue.nl> wsinkees@lso.win.tue.nl (Kees Huizing) writes: >lowj_ltd@uhura.cc.rochester.edu (John Alan Low) writes: > >>In article <4658@ur-cc.UUCP> I wrote: >>>I am having a problem with Turbo Pascal 4.0. The repeat loop in the following >>>loop never terminates. >>>Program Foo; >>>var x : real; >>>Begin >>>x := 0.10; >>> Repeat >>> x := x + 0.01; >>> Until x = 0.30; >>>End. > >> Thanks to everybody who emailed me on this. I forgot that 0.01 is a >> repeating decimal in binary. I never will again. One (similar) solution as has been pointed out by many netters is using function Equal (a, b : real) : boolean; begin if abs(a-b) < 1.0E-5 then equal := true else equal := false; end; . Until Equal (x, 0.30); ................................................................... Prof. Timo Salmi (Site 128.214.12.3) School of Business Studies, University of Vaasa, SF-65101, Finland Internet: ts@chyde.uwasa.fi Funet: vakk::salmi Bitnet: salmi@finfun
bseeg@spectra.COM (Bob Seegmiller) (01/05/90)
In article <4679@ur-cc.UUCP> lowj_ltd@uhura.cc.rochester.edu (John Alan Low, aka "Travis" Low) writes: > > >In article <803@tuewsd.lso.win.tue.nl> wsinkees@lso.win.tue.nl (Kees Huizing) writes: >>>In article <4658@ur-cc.UUCP> I wrote: >>>> [deleted floating-point loop program text] >>It's not you that is stupid, it's (Turbo?) Pascal. Is it not the purpose of >>a high level pogramming language to hide the funny details of implementation >>and representation for the user? As it shows, the equality operator >>"=" does not on reals what it pretends to do. I accept that it cannot >>detect perfect equality of reals, but what it could do is detect equality >>upto some representation dependent accuracy. >>Why is it not done this way? > > [report of discovery that same program works under Turbo Pascal 3.0] > expressions such as 1/3 + 2/3 come out equal to 1.0. So the binary- > coded representation of decimals works nicely, and the "=" works the > way it's supposed to. > > Is there some reason this representation is not common practice? BCD was (probably) used because the 80x86 processor has instructions that support BCD arithmetic, and then it goes in to really ancient history (8080 & business applications and, ... inaccuracies in floating-point arithmetic, plus speed penalties ... & & ). The 360 instruction set still supports BCD arithmetic, though whether it is still used I can't say (I haven't programmed 360's, just Concurrent Interdata processors, and the Interdata instruction set is similar to some version of the 360's -- and I'd never used that particular instruction in my work). I would guess it has big application in business/banking software where round-off would cause a hole in someone's account -- I was doing scientific work where round-off either didn't matter, or was minimized by appropriate algorithm design. > Can anybody shed some light on this? I think that later versions of > Turbo Pascal do not implement this representation, so there must be > some good reason, right? > Umm, the Turbo Pascal 4.0 manual and .DOC files describe Borland's shift from BCD in ver 3.0 to a binary form (which format is described in the manual). Also, I do believe they warn in the manual against using floating-point loop control variables. Guess it pays to read them manual things once in a while. A text on numerical methods using computers would make interesting reading for those curious about just what floating-point numbers are (essentially an incompletely mapped representation of the real [as in set theory] number set). I found a good one when I was at Utah, same publisher and series(?) as Wirth's _Algorithms + Data Structures .._ book, but an author whose name I (sorry) can't remember. A really excellent reference. Now for the name ... anybody? -- /---------------------------------------+-------------------------------------\ | Bob Seegmiller <The usual disclaimer> | Spectragraphics Corp. 619-587-6912 | | "Till mermaids wake us..." - Eliot | 9707 Waples Street | | UUCP: ...!nosc!spectra!bseeg | Sandy Eggo, CA 92121 |
ldo@waikato.ac.nz (Lawrence D'Oliveiro) (01/09/90)
Anybody who says "You should never check for equality with reals" obviously hasn't used a system that supports IEEE 754 arithmetic!
maine@elxsi.dfrf.nasa.gov (Richard Maine) (01/10/90)
On 9 Jan 90 05:15:58 GMT, ldo@waikato.ac.nz (Lawrence D'Oliveiro) said: Lawrence> Anybody who says "You should never check for equality with reals" Lawrence> obviously hasn't used a system that supports IEEE 754 arithmetic! This whole subject really has little to do with Pascal, but here goes anyway... I'm afraid, I don't understand the above comment. I'd have thought just the opposite. Anybody that is careful about writing robust and portable floatting point code should be extremely leary of equality tests for reals. Some are "safer" that others, but any such test should make a careful programmer hesitate. Likewise, those people concerned about writing well-behaved numerical programs generally applaud IEEE 754 as one of the best floatting point representations for serious numerical work. I would suppose that those people liking IEEE 754 would be among those most careful about such things as floatting point equality tests because IEEE 754 is careful about far more subtle issues. Its true that you _can_ do equality comparisons on IEEE 754 numbers, just like you can on most other formats, but that doesn't make it a good idea. It's also true that increasing conformance to IEEE 754 improves the odds that such an equality test might actually give the same results on 2 different systems, but it does little to guarrantee that both systems won't give the same "wrong" result. Anyway, I program on several IEEE 754 systems and I certainly say "you should never (well almost never) check for equality with reals." Perhaps I missed a "smiley face" in the comment quoted above, but it just doesn't make any sense to me. -- Richard Maine maine@elxsi.dfrf.nasa.gov [130.134.64.6]
amull@Morgan.COM (Andrew P. Mullhaupt) (01/10/90)
In article <1990Jan9.051558.16015@waikato.ac.nz>, ldo@waikato.ac.nz (Lawrence D'Oliveiro) writes: > Anybody who says "You should never check for equality with reals" > obviously hasn't used a system that supports IEEE 754 arithmetic! Your assertion is neither obvious nor true. Its implication is also false. You should never check for equality with floating point representations of numbers. Suppose you depend on the following expression (even in IEEE 754): boolean_var := (0.0) = ( ((4.0 / 3.0) - 1.0) * 3.0 - 1.0) you'll likely get what you didn't want. There are lot's of other good reasons (storage history being one) why you it isn't wise to check for equality with floating point representations of numbers. Later, Andrew Mullhaupt
dhinds@portia.Stanford.EDU (David Hinds) (01/14/90)
In article <4679@ur-cc.UUCP>, lowj_ltd@uhura.cc.rochester.edu (John Alan Low) writes: > Is there some reason [BCD] representation is not common practice? BCD arithmetic is SLOW! It is hard to manipulate BCD-format numbers, because at the assembly language level for almost all computers, there are only instructions for doing binary arithmetic. Doing BCD arithmetic is a real pain - the result of every fundamental binary operation has to be corrected to restore it to BCD format. BCD numbers are typically stored as two 4-bit digits per byte, so they also waste space, because only values of 0 to 9 are allowed for each 4-bit digit. So, a binary number of a given number of bits has a higher precision than a BCD number occupying the same space. I haven't timed Turbo's BCD support vs. normal real's, but I would expect the BCD stuff to run maybe 1/2 as fast for addition and subtraction, maybe 1/10 as fast for multiplication and division, and even worse for transcendental functions. -David Hinds dhinds@portia.stanford.edu
as02@bunny.gte.com (03/09/90)
Never use real numbers for a loop count; use an integer counter .
milne@ics.uci.edu (Alastair Milne) (03/10/90)
as02@bunny.gte.com writes: >Never use real numbers for a loop count; use an integer counter . That is to say, use the most appropriate *scalar* for what your counter is indexing: INTEGER, CHAR, Fruit, Colours, etc.. But as <as02@bunny.gte.com> so rightly says, the counter must not be a non-discrete type. Didn't Turbo complain rather loudly? Alastair Milne
amull@Morgan.COM (Andrew P. Mullhaupt) (03/11/90)
In article <8674@bunny.GTE.COM>, as02@bunny.gte.com writes: > Never use real numbers for a loop count; use an integer counter . This advice is often good. But it is spectacularly bad if you need a counter to go through really huge values. Then doubles or extendeds make sense, but reals are probably borderline, because you might be able to do two longint steps in one real. I use a 486 so floating point is VERY fast. I actually have had to use a double as a counter just the other day... Later, Andrew Mullhaupt