30-6 FFT using modular arithmetic

As defined, the discrete Fourier transform requires us to compute with complex numbers, which can result in a loss of precision due to round-off errors. For some problems, the answer is known to contain only integers, and by using a variant of the \(\text{FFT}\) based on modular arithmetic, we can guarantee that the answer is calculated exactly. An example of such a problem is that of multiplying two polynomials with integer coefficients. Exercise 30.2-6 gives one approach, using a modulus of length \(\Omega(n)\) bits to handle a \(\text{DFT}\) on \(n\) points. This problem gives another approach, which uses a modulus of the more reasonable length \(O(\lg n)\); it requires that you understand the material of Chapter 31. Let \(n\) be a power of \(2\).

a. Suppose that we search for the smallest \(k\) such that \(p = kn + 1\) is prime. Give a simple heuristic argument why we might expect \(k\) to be approximately \(\ln n\). (The value of \(k\) might be much larger or smaller, but we can reasonably expect to examine \(O(\lg n)\) candidate values of \(k\) on average.) How does the expected length of \(p\) compare to the length of \(n\)?

Let \(g\) be a generator of \(\mathbb Z_p^\*\), and let \(w = g^k \mod p\).

b. Argue that the \(\text{DFT}\) and the inverse \(\text{DFT}\) are well-defined inverse operations modulo \(p\), where \(w\) is used as a principal \(n\)th root of unity.

c. Show how to make the \(\text{FFT}\) and its inverse work modulo \(p\) in time \(O(n\lg n)\), where operations on words of \(O(\lg n)\) bits take unit time. Assume that the algorithm is given \(p\) and \(w\).

d. Compute the \(\text{DFT}\) modulo \(p = 17\) of the vector \((0, 5, 3, 7, 7, 2, 1, 6)\). Note that \(g = 3\) is a generator of \(\mathbb Z_{17}^\*\).

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用