24. Implementing the FFT and Multiplying Numbers 24.1 Introduction for Applying FFT In order to apply the Fast Fourier Transform algorithm, we must first describe in detail how a spreadsheet can be used to perform the FFT. We will then use FFT to multiply large numbers. 24.2 Implementing FFT’s on a Spreadsheet This section describes the fast algorithm for evaluating a polynomial of degree up to n-1 at n roots of unity. This algorithm can be applied in any field in which the equation xn-1 has a primitive root. A field is any set of elements that, under addition and multiplication, satisfies commutativity, distributivity, associativity, and has an identity element as well as inverse elements. Such fields include the complex numbers, and numbers mod any prime p of the form qn+1. The task of implementing this algorithm in spreadsheet software is roughly the same for n any power of 2. For our purposes we will create a spreadsheet for performing the FFT with n=16. For this we will need numbers with 16th roots of unity. 1616In order to find a primitive 16th root of unity in a modular field “x” on a spreadsheet first select a cell as a test value cell. In the cell below it write the following command =mod(cell above*test cell, x). If your “test cell” is the very first cell A1, the command typed into A2 will look like the following =mod(A1*$A1, x). Copy this cell into the 16 rows below the test cell. Test integer values in the test cell beginning with 2 and see whether or not the 16th cell has a “1” in it without any 1s appearing before the th cell. The first positive integer value fulfilling the above criterion will be a primitive th root of unity mod x. We can do FFT for mod 17 or 97 or 257, which are all fields that possess 16th roots of unity. We will arrange our algorithm so that we can switch moduli and primitive roots easily which will allow us to perform our operations mod each of these. The Chinese Remainder Theorem will then allow us to recover evaluations as high as the product of all three of these moduli. (For the Chinese remainder theorem please refer to course notes 21 and 22). The goal of the FFT algorithm is to obtain evaluations of our polynomial at 2arguments z0 (-1), z1, z , . . ., zn-1, where z is a primitive n-th root of unity on our field. This can be done in the complex plane where we can use z=cos(2π/n)+isin(2π/n).We will demonstrate the procedure mod 17, using 3 as our primitive 16th root of unity. You should check whether or not 3 is a 16th root of unity mod 17 using the process of finding primitive roots of unity in a modular field described above. Since we want to be able to copy our work and easily substitute different moduli and roots, we prepare our spreadsheet by putting the modulus, 17, in square in the first row and column of the space we devote to performing the FFT, and in the 15 cells to the right of the original cell type =(cell to the left). Similarly, we cut and paste the original row we have created into the row below it and type 3 (the value of the primitive root of unity) in the first cell in the newly copied and pasted row. In this way if we copy our work to different columns in the same rows, we will be able to insert a different modulus and root in each copy by changing two entries. In our third row we enter indices from 0 to 15 which will represent the power of x whose coefficient in our polynomial p is to be entered into the fourth row in that column. When we reach the end of the algorithm, the evaluation at zk will appear in the column with index k. So when we begin, our spreadsheet entries will look like 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 1 2 3 4 5 6 7 8 9 4 1 3 5 2 5 6 2 1 3 2 1 4 6 4 3 1 Row A_0 A_1 A_2 A_3 A_4 A_5 A_6 A_7 A_8 A_9 A_10 A_11 A_12 A_13 A_14 A_15 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 10 11 12 13 14 15 where the last row represents the polynomial that starts as 1 + 3x + 5x2 + 2x3 + . . . Notice that, while this is not a particularly unnatural way to describe a polynomial, it is not the normal convention, which starts with the highest power first. Here the highest power appears on the right. The algorithm will consist of 4 steps, which corresponds to the fact that 16 is 24; if we perform a 2k FFT we will need k steps. For convenience we label the columns A0 to A15 here. On a spreadsheet these would be A through Q or any similar range. 24.3 FFT Methodology STEP 1 We begin by entering in A05: = mod(A04+A84,A0$1) The notation A05 means we are talking about the cell in column A0 and the fifth row. The subscript denotes thecolumn while the following coefficient denotes the row. This will make it easier for you to implement the FFT on the spreadsheet if we give a general set of axes to work off of. We copy this entry into A15 through A75. These represent the even power evaluations. We must then move them (by cutting and pasting) to the even power locations; the entry in Aj5 should therefore be moved to square A2j5 for each j. We then enter in A06: = mod((A04 - A84)*A0$2^A0$3,A0$1) and copy it into A16 through A76. These entries must then be moved to the right of the entries in the even places in row 5. STEP 2 Copy the entry in A05 down into A06 and then across into A16 - A76. These should then be moved so as to occupy the squares in the 6th row with power indices 0-1, 4-5, 8-9, and 12-13. You then enter into A07: mod ((A05-A85)*A0$2^(2*int(A0$3/2)),A0$1) , copy these into the 7 places to its right, and move these into the 6th row in columns with indices 2-3,6-7,10-11, and 14-15. STEP 3 Copy the entry in A06 down into A07 and then across into A17- A77. These should then be moved so as to occupy the squares in the 7th row with indices 0-3 and 8-11. Enter into A08: mod ((A06-A86)*A0$2^(4*int(A0$3/4)),A0$1) , copy this into the 7 places to its right, and move these into the 7th row in columns with indices 4-7, and 12-15. STEP 4 Copy the entry in A07 down into A08 and then across into A18- A78.+ Enter into A09: mod (A06-A86,A0$1) , copy this into the 7 places to its right, and move these into the 8th row in columns with indices 8-15. At this point the entries in the 8th row here should be the evaluations sought. …