24. Implementing the FFT and Multiplying Numbers 1. Introduction We will first describe in detail how a spreadsheet can be set up to perform the Fast Fourier Transform algorithm. We will then apply it to the task of multiplying large numbers. 2. Implementing FFT’s on a Spreadsheet We will describe 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. Such fields include the complex numbers, and numbers mod any prime p of the form qn+1. The task of programming this algorithm is roughly the same for n any power of 2. We will create a spreadsheet for performing the FFT with n=16. We can do so 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. The goal of this algorithm is to obtain evaluations of our polynomial at arguments z0 (-1), z1, z2, . . ., 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 instead illustrate the procedure mod 17, using 3 as our primitive 16th root of unity. Since we want to be able to copy our work and easily substitute different moduli and roots, we prepare ourspreadsheet by putting the modulus, 17, in square in the first row and column of the space we devote to it, and put =(square to the left) in the 15 squares to its right. Similarly, we put 3 in the row beneath it. 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 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 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 10 11 12 13 14 15 1 3 5 2 5 6 2 1 3 2 1 4 6 4 3 1 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 way, 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. STEP 1 We begin by entering in A05: = mod(A04+A84,A0$1) We copy this into A15 through A75. These represent the even power evaluations. We must then move them 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 entriesmust then be moved to the right of the entries in the even places in row 5. STEP 2 You may 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 indices 0-1, 4-5, 8-9, and 12-13. You may 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. Please realize that there are a large number of ways that careless errors can creep into this procedure, and it is absolutely essential that you check that it works before considering yourself finished with it. To check it you can copy rows 4 to 8 anywhere directly below A0-A15, put =A08 in the entry just above the copy of row 4 in column 0, and copy that entry across that row. If your spreadsheet is correct the sum of the entry in row 8 in the column with index j should be the negative of the entry in your bottom row in column with index 16-j for j>0. (And the two entries in the 0 column should add up to 0 mod 17. If you find an error, you should try to locate it, by putting in a simple input polynomial, such as 1 or x or x2, etc.,and checking whether your 8-th line is what it should be for that polynomial. If it is not you can trace back to find the entry or entries that are wrong. With a little practice you will be able to locate each bug quickly. You will feel good when you are done. (If you really wanted to save machine effort, you would precalculate the powers of z that each odd power is to be multiplied by, and have them listed appropriately in rows to make the multiplication convenient. As it is, my machine calculates mod(z7,p) by first raising z to the 7th, and then dividing by p and taking the remainder. With larger n values this sort of thing could lead to a huge number, removing any benefit from use of the method.) FFT 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 3 3 3 3 333 333 333333 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 3 5 2 062 102 146401 1 1 5 3 6 2 6 …