A couple of colleagues of mine from work and me have been working our way through SICP. So far thing's have been pretty good but we recently came across a series of exercises on "interval arithmetic". The basic idea was to be able to construct a term as an interval of uncertainty (represented as a tuple (a,b)) meant for use in engineering calculations. Subsequently to define a series of arithmetic operations (+, -, * /) that operate on intervals and create new intervals with different uncertainties.
After a few such problems, it is brought to our attention that if an expression is written in two different forms, the value obtained can be different. For example (1/R1 + 1/R2) could also be written as ((R1 + R2)/R1R2) and these yield different values. The problem is clearly that all the operations we have defined increase the uncertainty and if an expression is written in a manner that results in more operations we should expect more uncertainty. In fact, as this gist demonstrates, (R2 - R1 + R1) can result in something more uncertain than R2 by itself.
Exercise 2.16 asks us to attempt to write the package in a way so that rewriting an expression in a different form will still yield the same answer. The key to this seems to be a combination of
- Some generalized method to simplify expressions.
- A method of identifying if two intervals are the same.
I initially interpreted the second point as being a way to check if two intervals are equal. But that's a mistake. Two intervals might be equal because they represent the same concept, or because they are two different terms with the same uncertainty and value. For example, if I was building a circuit with resistors, and I happen to use two resistors with the same rating (same value and error), they would still not be identical elements in the circuit. I wouldn't be able to "cancel them out". One of them might have an actual value that is on one side of the interval of uncertainty and the other might be on the opposite end.
The only way to identify if two intervals are the same would be if I redefine my constructor to create with each such tuple, an object id that is meant to be unique. Now if two intervals have the same object id, I'd know that they were in fact the same. An extremely simplistic method to generate such an object id might be to use a random number between one and one billion.
However, I have no idea how to even begin approaching the first problem. Such a thing would be trivial if the only allowed operations were addition and subtraction. (I could simply collect all the same terms and find their coefficients). Or only multiplication and division. But, with all four, I don't know where to start. So if anyone has some insights or resources, please do share them with me.
I'm just tossing out ideas, but...
ReplyDeleteInstead of thinking of a generalized method to simplify expressions, can you think of a way to write the expressions in a canonical form?
What would happen if instead of (define c (mul-interval a b)) computing an interval immediately, (get-lower-bound c) did the actual computation?
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 ...
ReplyDeletehmm
My thought is semilazy...
ReplyDeleteThe goal is this (forgive the atrocious formatting, blogger won't let me use <pre> or <code> tags):
(define r1 (make-interval-percentage 10000 5)) ; 10kOhm, 5% tolerance
(define r2 (make-interval-percentage 14700 2)) ; 14.7kOhm, 10% tolerance
(define parallel-1 (recip-interval (add-interval (recip-interval r1) (recip-interval r2))))
(define parallel-2 (div-interval (add-interval r1 r2) (mul-interval r1 r2)))
(assert (= (center-interval parallel-1) (center-interval parallel-2)))
(assert (= (percentage-interval parallel-1) (percentage-interval parallel-2)))
Actually, there's a simpler test which exhibits the problem...
(define int1 (make-interval 9 11)) ; 10 +/- 1
(define int2 (make-interval 9 11)) ; 10 +/- 1
(assert (identical-interval? int1 int1))
(assert (not (identical-interval? int1 int2)))
(assert (equivalent-interval? int1 int2))
(define sum (sum-interval int1 int2))
(assert (equivalent-interval sum (make-interval 18 22)))
(assert (identical-interval sum (sum-interval int1 int2)))
(assert (identical-interval sum (sum-interval int2 int1)))
(define sum-less-int1 (sub-interval sum int1))
(assert (identical-interval sum-less-int1 int2))
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.
So imagine an add which did something like:
(define (add-int int1 int2)
(let ((num1 (num-int int1))
(num2 (num-int int2))
(den1 (den-int int1))
(den2 (den-int int2)))
(make-int-num-den
(add-int-parts
(mul-int-parts int1 den2)
(mul-int-parts int2 den1))
(mul-int-parts den1 den2))))
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.
Could this idea be expanded into a full package? Maybe, but I oughta leave some work for you ;-).
(suggestion, mul-int-parts would begin something like:
(define (mul-int-parts a b)
(cond
((= a 'one) b)
((= b 'one) a)
...))
where 'one represents the multiplicative identity.
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.
ReplyDeletePlay the Best Merkur Slots for the Money by Play the Best
ReplyDeleteThe three most popular Merkur slot games are Wolf Gold 메리트카지노 and Divine Fortune. 코인카지노 The three most popular slots that players can try for free online 우리카지노 include
Learn the games with play money where it would not price you something if you lose. Pick a game.There are dozens of types of video poker. I recommend Jacks or Better because of|as a result of} it's the unique VP game, it's extensively available, and most importantly, the technique is fairly straightforward. This may appear to 카지노사이트 happen way more usually than it should. But that is an phantasm caused by the human tendency to look for patterns.
ReplyDelete