Homework 8, due Wed Dec 14
Homework must be given to me in class on Dec 14 or left under MY
office ( NOT Ernest's door). Any time up to 12 noon on
Thu Dec 15 is OK, but after that late homework will not be accepted
or graded. Ernest will not be available after Dec 9. However, I
am available to answer questions about the exam Tue Dec 13 through
Fri Dec 16 (the day of the exam). Drop by my office or send email for
an appointment.
- Implement Algorithm 12.1 (p.500 of the text). If you use Matlab,
note that the second argument to fft in the algorithm statement is an
output argument; thus the function declaration should
be function y = myfft(x, n, w). Do not use the name fft,
which is a standard function in Matlab. Test the code and compare the results
to a standard FFT code such as fft in Matlab before going
on to the next part.
Important note: The last paragraph on p.500 on the issue of
the result coming out in the wrong order is very confusing for the
following reason: the author is thinking in terms of p and
s being global variables. However, if p
and s are local variables, i.e. allocated and deallocated
every time the recursive function is called, the output order is
correct. In most programming languages, the only way you could make
p and s global is by explicitly passing these
as additional parameters. While this may save on execution time, it
makes the code far more confusing, so I recommend not doing
this, unless you are very clear about what you are doing and are trying
to make the code more efficient.
- Computer Problem 12.2, p.508, answering all parts (a),(b),(c),(d).
For part (a), no FFT is required; you can solve the system with \.
The point of parts (c) and (d) is to emphasize what may or may not
be obvious: the FFT provides a far more efficient solution than \
(or even matrix multiply) for a problem like this, although it makes
little difference when there are only 12 variables.
- Compare the efficiency of your code and the standard code on large
randomly generated problems (for example, n=220).
The book comments that the recursive implementation may not be an
efficient choice, but another important, maybe more important, issue
in Matlab is avoiding
the explicit for loops. If you can, replace the loops by vector
operations. Note that vectors can be indexed by other vectors.
See Moler's book (freely available online, see course web page)
for tips on Matlab programming.
There is no problem using loops or recursion in a compiled language
like C. How much slower is your code compared to the standard code
for n=220?
You don't need this, but here
is some info on the meaning of ascension and declination that I found
on the web. The unit "minute" is a 60th of a degree, not a unit of time.
The measure in degrees of the position of a celestial object north or south of the celestial equator. If an object is on the celestial equator, it has a declination of 0 degrees, and if it is on the north or south celestial pole, it has a declination of +90 degrees or .90 degrees. Declination is analogous to latitude on the Earth, which measures terrestrial positions north or south of the equator. right ascension and declination together comprise a coordinate system that allows astronomers to locate objects in the sky.