- 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=2
^{20}). 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=2^{20}?

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.