Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo tài liệu 'thuật toán algorithms (phần 49)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | THE FAST FOURIER TRANSFORM 473 Complex Roots of Unity It turns out that the most convenient points to use for polynomial interpolation and evaluation are complex numbers in fact a particular set of complex numbers called the complex roots of unity. A brief review of some facts about complex analysis is necessary. The number i is an imaginary number though 1 is meaningless as a real number it is convenient to give it. a name i and perform algebraic manipulations with it replacing i2 with -1 whenever it appears. A complex number consists of two parts real and imaginary usually written as a bi where a and b are reals. To multiply complex numbers apply the usual rules but replace 2 with -1 whenever it appears. For example a bi c di ac bd ad bc i. Sometimes the real or imaginary part can cancel out when a complex multiplication is performed. For example 1 - i l -i -2i 1 t 4 -4 1 z 8 16. Scaling this last equation by dividing through by 16 y 2 we find that 8 1. kv 2 v 27 In general there are many complex numbers that evaluate to 1 when raised to a power. These are the so-called complex roots of unity. In fact it turns out that for each N there are exactly N complex numbers z with zN 1. One of these named wy is called the principal Nth root of unity the others are obtained by raising to the kth power for fa 0 1 2 . . . N 1. For example we can list the eighth roots of unity as follows Wg Wg Wg Wg Wg w w Wg. The first root is 1 and the second is the principal root. Also for N even the root is -1 because 1 . The precise values of the roots are unimportant for the moment. We ll be using only simple properties which can easily be derived from the basic fact that the Nth power of any Nth root of unity must be 1. 474 CHAPTER 36 Evaluation at the Roots of Unity The crux of our implementation will be a procedure for evaluating a polynomial of degree N 1 at the Nth roots of unity. That is this procedure transforms the N coefficients which define the polynomial into the N values .
