Spreadsheet to Demonstrate FFT Multiply

How Exactly Do FFT Multiplies Actually Work?

When I was getting interested in Mersenne prime numbers, I learned the Lucas-Lehmer test depends heavily on an FFT multiply. If you are unfamiliar with it, I'll explain: Instead of multiplying two large numbers, you take their Fourier Transforms, convolve them, then invert. At first, that sounded to me like much more trouble than actually multiplying. In fact, I was healthily skeptical. Therefore, I decided to create a dynamic environment where I could experiment and see everything taking place down to the arithmetic level!

If you are curious, you may take a look at the spreadsheet (xls format) and experiment with it. Enter your test numbers in cells G2 and G3. I highly encourage it.

Example #1

Just in case you can't experiment with it right now, I included two example pictures.

In this first one, look at the purple cells. I am multiplying 2020 times 9 (why those numbers? you'll see). I took a DFT of each of the cells (there was no need to do an FFT to understand the multiplication aspect) and you can see those results in yellow. But, as I learned while doing this, the yellow is really the important values, you want to see look to the orange cells, the "Amplitudes needed for resynthesis.

As you can tell from imaging a signal of 2,0,2,0, there is a DC offset of 1. That is represented by the 1 in cell B29. If the FT of the signal were only 1, it would look like 1,1,1,1 however, there is another signal superimposed: 1,-1,1,-1. Of course, the period of that signal is 2, with phase of 0, and amplitude of 1, so the cell in D29 contains a 1 as well. Since there is no superposition of a signal with period 1 (corresponding to a value like 1,1,0,0), you can see that cell C29 is zero.

Finally, just to make sure my DFT routine was working, I took the inverse below it. The results are in lavender, and of course match the original value.

Over in cell N29, you can see the multiplication, and below that, the inverse which produces the correct result. The result is compared to the original in cell G7.

Example #2

In this example, I multiply a different pair of numbers to provide a further example.

Links

Back to Portfolio Noah Vawter
Next Project