tag:blogger.com,1999:blog-5522230262649447143.post5800187482888806074..comments2019-02-18T02:20:15.092-08:00Comments on stuff: Generalized Expression Simplification in SICP?Vishnu S Iyengarhttp://www.blogger.com/profile/06935516811962030409noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-5522230262649447143.post-79192687154403125622010-04-10T21:02:52.565-07:002010-04-10T21:02:52.565-07:00ah hmm, I'm gonna need to think this through. ...ah hmm, I'm gonna need to think this through. One thing though that I DO realise from reading what you said is that I was solving the wrong problem. I wanted to convert every expression to the point where it had the smallest error. Whereas all that was necessary was to convert every expression to a standard form.Vishnu S Iyengarhttps://www.blogger.com/profile/06935516811962030409noreply@blogger.comtag:blogger.com,1999:blog-5522230262649447143.post-1753110766067860682010-04-10T07:13:30.003-07:002010-04-10T07:13:30.003-07:00My thought is semilazy...
The goal is this (forgi...My thought is semilazy...<br /><br />The goal is this (forgive the atrocious formatting, blogger won't let me use <pre> or <code> tags):<br /><br />(define r1 (make-interval-percentage 10000 5)) ; 10kOhm, 5% tolerance<br />(define r2 (make-interval-percentage 14700 2)) ; 14.7kOhm, 10% tolerance<br /><br />(define parallel-1 (recip-interval (add-interval (recip-interval r1) (recip-interval r2))))<br />(define parallel-2 (div-interval (add-interval r1 r2) (mul-interval r1 r2)))<br /><br />(assert (= (center-interval parallel-1) (center-interval parallel-2)))<br /><br />(assert (= (percentage-interval parallel-1) (percentage-interval parallel-2)))<br /><br /><br />Actually, there's a simpler test which exhibits the problem...<br /><br /><br />(define int1 (make-interval 9 11)) ; 10 +/- 1<br />(define int2 (make-interval 9 11)) ; 10 +/- 1<br /><br />(assert (identical-interval? int1 int1))<br />(assert (not (identical-interval? int1 int2)))<br />(assert (equivalent-interval? int1 int2))<br /><br />(define sum (sum-interval int1 int2))<br />(assert (equivalent-interval sum (make-interval 18 22)))<br />(assert (identical-interval sum (sum-interval int1 int2)))<br />(assert (identical-interval sum (sum-interval int2 int1)))<br /><br />(define sum-less-int1 (sub-interval sum int1))<br />(assert (identical-interval sum-less-int1 int2))<br /><br /><br />The trick to avoid errors creeping in is canonicalization. For instance, every expression composed of just arithmetic operations can be algebraically converted to a form (a/b) where a and b can be complex expressions that do not contain division: anything of the form (a/b)+(c/d) can be converted to (ad+bc)/bd; anything of the form ((a/b)/(c/d)) can be converted to ad/bc; repeated use of these two transformation rules will reduce the total number of divisions to 1.<br /><br />So imagine an add which did something like:<br /><br /><br />(define (add-int int1 int2) <br /> (let ((num1 (num-int int1))<br /> (num2 (num-int int2))<br /> (den1 (den-int int1))<br /> (den2 (den-int int2)))<br /> (make-int-num-den <br /> (add-int-parts <br /> (mul-int-parts int1 den2) <br /> (mul-int-parts int2 den1)) <br /> (mul-int-parts den1 den2))))<br /><br /><br />The internal representation of an interval is of the form (a/b) where neither a nor b use division, and the definition of addition reflects that.<br /><br />Could this idea be expanded into a full package? Maybe, but I oughta leave some work for you ;-).<br /><br />(suggestion, mul-int-parts would begin something like:<br /><br /><br />(define (mul-int-parts a b)<br /> (cond <br /> ((= a 'one) b)<br /> ((= b 'one) a)<br /> ...))<br /><br /><br />where 'one represents the multiplicative identity.Blaise Pascalhttps://www.blogger.com/profile/17167036913705912859noreply@blogger.comtag:blogger.com,1999:blog-5522230262649447143.post-63231997425492325372010-04-09T00:59:17.394-07:002010-04-09T00:59:17.394-07:00some sort of lazy computation? As long as all thos...some sort of lazy computation? As long as all those calculations actually do end up occurring, I can't see a way to avoid errors creeping in ...<br />hmmVishnu S Iyengarhttps://www.blogger.com/profile/06935516811962030409noreply@blogger.comtag:blogger.com,1999:blog-5522230262649447143.post-217718888283797612010-04-06T20:19:34.837-07:002010-04-06T20:19:34.837-07:00I'm just tossing out ideas, but...
Instead of...I'm just tossing out ideas, but...<br /><br />Instead of thinking of a generalized method to simplify expressions, can you think of a way to write the expressions in a canonical form? <br /><br />What would happen if instead of (define c (mul-interval a b)) computing an interval immediately, (get-lower-bound c) did the actual computation?Blaise Pascalhttps://www.blogger.com/profile/17167036913705912859noreply@blogger.com