Homework #1: Review of square roots

Posted 1/18; Due 1/25

Background

S'pose you wanted to design a calculator, and you've already tackled the job of implementing addition, subtraction, multiplication, and division buttons. Your next job is to implement the square root button.

There are a variety of algorithms that you can choose from to accomplish this task (algorithms that compute square roots of real numbers using only addition, subtraction, multiplication, and division). Four such algorithms were mentioned in class (Newton's method, Taylor series, bisection, and the BAD-ass relaxation algorithm -- Beaux, Ahmed, and Dennis's creation). You're welcome to use any of these in your implementation or create another. Mind you, since we've discussed the BAD-ass algorithm in class so much, my expectations will be higher of your responses below should you choose that one. (NB: This is a nonlinear problem so, generally speaking, only iterative procedures are available to us, but if you can come up with a direct procedure, super!)

Questions

"E" is for "easy" (or at least easier); these are the questions you need to answer correctly at a minimum for a passing grade. "M" is for medium-ish difficulty questions; usually these will require a bit more work. "H" is for harder questions; hey, these are the interesting ones!

E Assume you can perform exact arithmetic (+, &minus, ×, ÷). Write a procedure that returns an approximate square root given a real radicand and relative error tolerance.

E Translate this procedure into a computer program that uses limited precision arithmetic. (IEEE floating point on a desktop machine is probably easiest; binary-coded decimal floating point on the TI or HP or hexadecimal floating point on an IBM or Microsoft Excel's fixed point are all also readily available.)

E Use your program to compute √2 with a relative accuracy of 10^-10. Make a semi-log plot of the error in each iterate's estimate versus the iteration number. Verify that the convergence rate is what you expect it to be. Make sure to label your plot appropriately and describe exactly just what is being plotted.

M Prove that your procedure "works" with exact arithmetic. That is, show that it stops after a finite number of steps, and that after those steps the resulting approximation has a relative error smaller than the desired tolerance.

M How many iterations are required? How does this depend on the radicand? The error tolerance? How many arithmetic operations are required (+ and ×)? How many comparisons/branches?

M Make a plot of the output of your square root function versus the input. (It may help to overlay your plot with the "true" square root.) Is this a continuous graph? NB: It may help to lower the error tolerance to exaggerate the appearance to demonstrate the interesting parts of the graph. Changing the scale and restricting to smaller intervals ("zooming") may help, too.

H Prove your conjecture about continuity.

H What effect does limited precision arithmetic have on the execution of your procedure? For instance, does it have any effect on speed? Is your procedure still accurate for all inputs? Are there any inputs for which your procedure becomes unstable? (Think about round-off/truncation and/or cancellation.) Does it still make sense to talk about continuity?

H Write a procedure that produces an output (to within a prescribed relative error tolerance) for any IEEE single precision floating point input.

H Prove it.

H Is there a procedure that produces an answer that is correctly rounded? (Warm-up: how is this different from an answer that has a small relative error?)

H In class, we used a shifting procedure (on a logarithmic scale) to achieve a range reduction. In exact arithmetic, it wouldn't matter if we used the reciprocal to get our range reduction. (Right?) What effect would this have in finite precision arithmetic? What about Daniel's suggestion of altering the update step of the algorithm?

E	Assume you can perform exact arithmetic (+, &minus, ×, ÷). Write a procedure that returns an approximate square root given a real radicand and relative error tolerance.
E	Translate this procedure into a computer program that uses limited precision arithmetic. (IEEE floating point on a desktop machine is probably easiest; binary-coded decimal floating point on the TI or HP or hexadecimal floating point on an IBM or Microsoft Excel's fixed point are all also readily available.)
E	Use your program to compute √2 with a relative accuracy of 10^-10. Make a semi-log plot of the error in each iterate's estimate versus the iteration number. Verify that the convergence rate is what you expect it to be. Make sure to label your plot appropriately and describe exactly just what is being plotted.
M	Prove that your procedure "works" with exact arithmetic. That is, show that it stops after a finite number of steps, and that after those steps the resulting approximation has a relative error smaller than the desired tolerance.
M	How many iterations are required? How does this depend on the radicand? The error tolerance? How many arithmetic operations are required (+ and ×)? How many comparisons/branches?
M	Make a plot of the output of your square root function versus the input. (It may help to overlay your plot with the "true" square root.) Is this a continuous graph? NB: It may help to lower the error tolerance to exaggerate the appearance to demonstrate the interesting parts of the graph. Changing the scale and restricting to smaller intervals ("zooming") may help, too.
H	Prove your conjecture about continuity.
H	What effect does limited precision arithmetic have on the execution of your procedure? For instance, does it have any effect on speed? Is your procedure still accurate for all inputs? Are there any inputs for which your procedure becomes unstable? (Think about round-off/truncation and/or cancellation.) Does it still make sense to talk about continuity?
H	Write a procedure that produces an output (to within a prescribed relative error tolerance) for any IEEE single precision floating point input.
H	Prove it.
H	Is there a procedure that produces an answer that is correctly rounded? (Warm-up: how is this different from an answer that has a small relative error?)
H	In class, we used a shifting procedure (on a logarithmic scale) to achieve a range reduction. In exact arithmetic, it wouldn't matter if we used the reciprocal to get our range reduction. (Right?) What effect would this have in finite precision arithmetic? What about Daniel's suggestion of altering the update step of the algorithm?

Note that the first thing I'm gonna do is test your code. If it doesn't work, you better already know that and have told me in advance. In that case, you should at least:

identify that the code's output is incorrect; what about the output tells you it's incorrect?
figure out why it's incorrect
figure out a fix

Note that the last two are often different things.

About the difficulty of problems: just because I say it's "hard" doesn't mean it is hard. Conversely, just because I say it's "easy" doesn't mean it's easy. Try them out; see for yourself. YMMV, buyer beware, and all that jazz. Also, if you can cogently explain why a question is difficult (even without answering it), that's something.