Numbers & Precision
in [Lisp]
|
Prev: aserve on Linux anyone? [was Re: Good functional programminghabbit?]
Next: need help implementing hooks in Common lisp
From: Aravindh Johendran on 3 May 2010 03:04 I'm working on an exercise in SICP - improving the square root program in the first chapter. Exercise 1.7, to be precise. In MIT-Scheme, if I define average to be as follows, (define (average x y) (/ (+ x y) 2)) Why are the following incantations not giving me the correct/expected answers? (+ 0.9999999999999999e23 1.0000000000000001e23) ;Value: 1.9999999999999998e23 (average 0.9999999999999999e23 1.0000000000000001e23) ;Value: 0.9999999999999999e23 Is all of this related to floating point arithmetic? Is there a good source to understand the topic? Wikipedia entry is dense. I hate SICP. One seemingly innocuous question in an exercise about square roots in the first chapter and it is taking me days to answer. --------------------------------------------------- Whereas, in Common Lisp (CCL, SBCL and CLISP) CL-USER> (defun avg (x y) (/ (+ x y) 2)) AVG CL-USER> (avg 9.999999999999999E22 1.0000000000000001E23) 1.0E23 CL-USER> 9.999999999999999E22 1.0E23 CL-USER> 1.0000000000000001E23 1.0E23 CL-USER> (describe 0.9999999999999999e23) ;; CCL version Float: 1.0E+23 Scientific: 1.00E+23 Log base 2: 76.40434 Ratio equiv: 99999997781963083612160 Nearest integer: 99999997781963083612160 ---------------------------------------------------------- Why is CL behavior different? Is rounding off done automatically according to the specs? Even though I entered 0.9999999999999999e23 in the REPL, the genie refers to it as 1.0E+23. Where did it get modified? While it was being read in?
From: Tamas K Papp on 3 May 2010 04:42 On Mon, 03 May 2010 00:04:03 -0700, Aravindh Johendran wrote: > I'm working on an exercise in SICP - improving the square root program > in the first chapter. Exercise 1.7, to be precise. > > In MIT-Scheme, if I define average to be as follows, (define (average x > y) > (/ (+ x y) 2)) > > Why are the following incantations not giving me the correct/expected > answers? > > (+ 0.9999999999999999e23 1.0000000000000001e23) ;Value: > 1.9999999999999998e23 > > (average 0.9999999999999999e23 1.0000000000000001e23) ;Value: > 0.9999999999999999e23 > > Is all of this related to floating point arithmetic? Is there a good > source to understand the topic? Wikipedia entry is dense. I hate SICP. > One seemingly innocuous question in an exercise about square roots in > the first chapter and it is taking me days to answer. > > --------------------------------------------------- > > Whereas, in Common Lisp (CCL, SBCL and CLISP) > > CL-USER> (defun avg (x y) > (/ (+ x y) 2)) > AVG > CL-USER> (avg 9.999999999999999E22 1.0000000000000001E23) 1.0E23 > CL-USER> 9.999999999999999E22 > 1.0E23 > CL-USER> 1.0000000000000001E23 > 1.0E23 > CL-USER> (describe 0.9999999999999999e23) ;; CCL version Float: 1.0E+23 > Scientific: 1.00E+23 > Log base 2: 76.40434 > Ratio equiv: 99999997781963083612160 > Nearest integer: 99999997781963083612160 > ---------------------------------------------------------- > > Why is CL behavior different? Is rounding off done automatically > according to the specs? Even though I entered 0.9999999999999999e23 in > the REPL, the genie refers to it as 1.0E+23. Where did it get modified? > While it was being read in? CL will read these as single floats by default: CL-USER> (defparameter *f* 9.999999999999999E22) *F* CL-USER> *f* 1.e23 CL-USER> (float-radix *f*) 2 CL-USER> (float-precision *f*) 24 As you see, there aren't enough digits in there to represent the numbers you are using as something different from 1. You might want to use double floats: the syntax is 1.0000000000000001d23. But then again, you are at the very limit of machine precision: CL-USER> (- 1.0000000000000001d23 1d23) 1.6777216d7 Use rationals if you want these kind of calculations to be precise. The article by Goldberg [1] is a good intro to floating point arithmetic. There are zillion copies floating around on the net, just grab one, but be advised that it is not an easy topic. If you are just learning Lisp, I would suggest that you ignore this issue and come back to it later, if/when you are doing serious numerical computation. Best, Tamas [1] http://portal.acm.org/citation.cfm?id=103163
From: Pascal J. Bourguignon on 3 May 2010 11:16 Tamas K Papp <tkpapp(a)gmail.com> writes: > On Mon, 03 May 2010 00:04:03 -0700, Aravindh Johendran wrote: > >> I'm working on an exercise in SICP - improving the square root program >> in the first chapter. Exercise 1.7, to be precise. >> >> In MIT-Scheme, if I define average to be as follows, (define (average x >> y) >> (/ (+ x y) 2)) >> >> Why are the following incantations not giving me the correct/expected >> answers? >> >> (+ 0.9999999999999999e23 1.0000000000000001e23) ;Value: >> 1.9999999999999998e23 >> >> (average 0.9999999999999999e23 1.0000000000000001e23) ;Value: >> 0.9999999999999999e23 >> >> Is all of this related to floating point arithmetic? Yes. > Use rationals if you want these kind of calculations to be precise. >> Is there a good source to understand the topic? Yes: > The article by Goldberg [1] is a good intro to floating point > arithmetic. > [1] http://portal.acm.org/citation.cfm?id=103163 or: http://docs.sun.com/source/806-3568/ncg_goldberg.html > [...] just grab one, but be advised that it is not an easy topic If you are > just learning Lisp, I would suggest that you ignore this issue and > come back to it later, if/when you are doing serious numerical > computation. Well, it's not difficult to understand the problem. What's not easy is to solve it adequately. This is where numerical algorithmic wizzardry comes in. But understanding the problem is easy, it is taught to pupil at the end of primary school: Divide 1 by 3 with 4 digits of precision. You get 0.3333 Now, add three times this (approximate) value of 1/3: 0.3333 + 0.3333 + 0.3333 -------- 0.9999 and subtract it from 1: 1 - 0.9999 -------- 0.00001 which is, using 4 digits of precision: 0.0000 But, if you use floating point, instead of fixed point, then 0.00001 is written 1e-5, and there is no rounding (there's only one significant digit here). However, we can see where the problem comes from: there is no exact representation of 1/3 in base ten. Similarly, there is no exact representation in base two of numbers you're considering. For more details, read Goldberg's aricle. -- __Pascal Bourguignon__ http://www.informatimago.com
From: Aravindh Johendran on 3 May 2010 16:21 On May 3, 4:42 am, Tamas K Papp <tkp...(a)gmail.com> wrote: > Use rationals if you want these kind of calculations to be precise. > > The article by Goldberg [1] is a good intro to floating point > arithmetic. Thanks for the pointers. Funny how numbers can be so complicated in computers/programming. ----------------------------- On May 3, 11:16 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > But understanding the problem is easy, it is taught to pupil at the > end of primary school: Ouch! > However, we can see where the problem comes from: there is no exact > representation of 1/3 in base ten. Similarly, there is no exact > representation in base two of numbers you're considering. For more > details, read Goldberg's aricle. OK, am beginning to understand. Thanks for the response and pointer. - Aravindh
From: Barry Margolin on 3 May 2010 21:49
In article <0a14e585-ca3c-4838-832d-4fc2544daab4(a)i10g2000yqh.googlegroups.com>, Aravindh Johendran <ajohendran(a)gmail.com> wrote: > On May 3, 4:42�am, Tamas K Papp <tkp...(a)gmail.com> wrote: > > > > Use rationals if you want these kind of calculations to be precise. > > > > The article by Goldberg [1] is a good intro to floating point > > arithmetic. � > > Thanks for the pointers. Funny how numbers can be so complicated in > computers/programming. To quote Barbie: "Math is hard." -- Barry Margolin, barmar(a)alum.mit.edu Arlington, MA *** PLEASE post questions in newsgroups, not directly to me *** *** PLEASE don't copy me on replies, I'll read them in the group *** |