The purpose of this research project is to discover the magical world of the Fast Fourier Transform.
The Fast Fourier Transform is a relatively complex piece of mathematics that has revolutionized many areas of science and engineering. It has applications in many fields from simple arithmetic to medicine.
Find out what the FFT is. Describe basically how it works. Then describe a few applications (2-5 should do; make them from somewhat diverse fields). One should be its application to the multiplication of large integers.
Support code should include an implementation of the FFT and its use to multiply large integers. You can further implement or pseudocode any of your other applications of the FFT from the paper.
This assignment is (Level 6). (This does not include implementations you've chosen to include beyond the large integer multiplication. Please negotiate each such extra implementation's level with me and then add that on.)