3
$\begingroup$

I'm having some trouble doing SICP exercise 2.15. Please note that this question is not closed related to Lisp. Instead, it's closely related to numerical analysis.

Exercise 2.15. Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, par2 is a "better" program for parallel resistances than par1. Is she right? Why?

This question is a little confusing when pulled out of context, so please let me explain. The formula for parallel resistors can be written in two algebraically equivalent ways: $\frac{R_1R_2}{R_1+R_2}$ and $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$. However, it seems that computing parallel resistors with the second formula would always produce higher precision than using the first one.

My question is:

  1. Which formula is better? $\frac{R_1R_2}{R_1+R_2}$ or $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$? Here "better" means provides higher precision.
  2. Why it is better than the other one? Please prove your answer to the first question.

Here is my effort

After many experiments, $\frac{1}{\frac{1}{R1}+\frac{1}{R2}}$ seems to be the better formula. I guess that the reason behind can be conclude as the fewer time uncertain numbers are repeated, the less uncertainty is introduced, and the higher precision we can get.

But that's not enough. I expect a more scientific and more rigorous answer.

$\endgroup$
  • $\begingroup$ By repeated, do you mean multiplied? $\endgroup$ – Yuval Filmus Jan 18 '17 at 16:36
  • 1
    $\begingroup$ @YuvalFilmus In my understanding, "repeat" means "appear more than once" in this exercise. Both R1 and R2 appear twice in the first formula, and only once in the second one, so the second formula is "such a form that no variable that represents an uncertain number is repeated" $\endgroup$ – nalzok Jan 18 '17 at 16:56
  • $\begingroup$ I didn't really understand your original title (I thought it had something to do with probability) so I edited. Please feel free to revert if you think your title was better than mine! $\endgroup$ – David Richerby Jan 18 '17 at 18:09
4
$\begingroup$

First, I want to say that it is not the case in general that an algorithm that minimizes the number of uses of the inputs is more accurate, at least for IEEE 754 floating point. For example, compensated summation.

On the other hand, it's certainly the case that interval arithmetic can greatly benefit from knowing when two inputs are identical. As a trivial example, if $X$ is an interval variable, then logically $X - X = 0$ but of course the subtraction algorithm (usually) doesn't know whether it's inputs are logically identical, and so it must assume the worst-case $$X - X = [X^{lo} - X^{hi},X^{hi} - X^{lo}]$$

This is roughly what's going on here and almost certainly view SICP is taking. If you use naive interval arithmetic operations, repeated uses of a variable will be treated independently, and so it won't be possible to cancel out error and the worst-case must be assumed. Using the formulas from the interval arithmetic Wikipedia page and assuming $R_1$ and $R_2$ are represented by intervals that are strictly positive, you can simply calculate: $$\frac{1}{\frac{1}{R_1}+\frac{1}{R_2}} = \left[\frac{1}{\frac{1}{R_1^{lo}}+\frac{1}{R_2^{lo}}},\frac{1}{\frac{1}{R_1^{hi}}+\frac{1}{R_2^{hi}}}\right]$$ while $$\frac{R_1 R_2}{R_1 + R_2} = \left[\frac{R_1^{lo}R_2^{lo}}{R_1^{hi}+R_2^{hi}},\frac{R_1^{hi}R_2^{hi}}{R_1^{lo}+R_2^{lo}}\right]$$

It's clear that $$\frac{R_1^{lo}R_2^{lo}}{R_1^{hi}+R_2^{hi}} \leq \frac{R_1^{lo}R_2^{lo}}{R_1^{lo}+R_2^{lo}}$$ and symmetrically for the upper bounds, so the latter formula has a looser interval.

$\endgroup$
  • $\begingroup$ This answer is great! However, I think compensated summation mainly deals with the error brought by floating-point arithmetic, on which this exercise doesn't lay much emphasis. Let's assume floating-point arithmetic always gives accuracy result. (Alternatively, let's assume rational numbers are stored as numerator / denominator in the memory, so the representation is exact.) In this case, considering only the error caused by interval arithmetic itself, is Eva Lu Ator right? $\endgroup$ – nalzok Jan 19 '17 at 3:22
  • $\begingroup$ As a generally true fact about interval arithmetic, I don't know. I suspect that you can prove that it holds for broad classes of expressions. For example, I'm fairly confident that it's true for expressions involving only addition, subtraction, and multiplication. In general "expressions" can be arbitrary programs for which this statement is almost certainly false. $\endgroup$ – Derek Elkins Jan 19 '17 at 5:38
  • $\begingroup$ To divide two intervals, we can simply multiplies the first by the reciprocal of the second, so I guess the statement holds true for all expressions involving only addition, subtraction, multiplication, and division. I'm glad to perform the proof on my own, but could you give me some hints on how to prove it? You know, even elementary arithmetic can produce a broad class of expressions, and I don't know where to get started. Also, by "arbitrary programs", do you mean weird things like the Dirichlet function? $\endgroup$ – nalzok Jan 19 '17 at 6:03
  • $\begingroup$ I've tried many expressions with more "advanced" functions such as $\log_a b =\frac{\log b }{\log a }$, but all of them show me that "the more inter-interval operations (i.e. operations between two intervals) are performed, the more information on precision is lost, and thus the less accurate the result would be". Could you please give me an example of an "arbitrary program" for which Eva Lu Ator's statement is false? $\endgroup$ – nalzok Jan 19 '17 at 6:29
  • $\begingroup$ $\log$ is monotonic so it's not going to cause problems. I didn't state that it was false, though largely because it's not clear what "uses" means in that context nor what the range of allowed operations would be. As a simple example though, doing Newton's method with intervals diverges but if you "use" a variable an extra time to intersect, it works correctly: www2.math.uni-wuppertal.de/~xsc/xsc/node12.html $\endgroup$ – Derek Elkins Jan 19 '17 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.