上图来自 PDF Fourier Transforms and the Fast Fourier Transform (FFT) Algorithm, Paul Heckbert.
如果a_n都相等的话，Ａ_k是等比数列求和．
为啥傅里叶变换在解密中也有用？因为解密涉及大整数的分解，which涉及一长串数，把它们看作信号的幅值，进行变换后可以得到频谱，即数重复出现的规律．
欧拉恒等式是欧拉公式的特例．i的i次方不是１个数而是一堆数：sin(2npi)都是0
For image processing applications, it is useful to consider the Discrete Cosine Transform (2D DCT) instead of the 2D DFT due to its superior empirical performance for signal compression and reconstruction tasks.
以下摘自Image Compression Using the Discrete Cosine Transform, Andrew B. Watson, NASA Ames Research Center.
The discrete cosine transform (DCT) is a technique for converting a signal into elementary frequency components. It is widely used in image compression.
Developed by Ahmed, Natarajan, and Rao [1974], the DCT is a close relative of the discrete Fourier transform (DFT). In fact, it is possible to compute the DCT via the DFT (see [Jain 1989, p. 152]): First create a new list by extracting the even elements, followed by the reversed odd elements. Then multiply the DFT of this re-ordered list by so-called "twiddle factors" and take the real part. The inverse DCT can be computed by multiplication with the inverse of the DCT matrix.
The application of the DCT to image compression was pioneered by Chen and Pratt [1984].
The one-dimensional DCT is useful in processing one-dimensional signals such as speech waveforms. For analysis of two-dimensional (2D) signals such as images, we need a 2D version of the DCT. For an n x m matrix s, the 2D DCT is computed in a simple way: The 1D DCT is applied to each row of s and then to each column of the result.
DCT-based image compression relies on two techniques to reduce the data required to represent the image. The first is quantization of the image's DCT coefficients; the second is entropy coding of the quantized coefficients. Quantization is the process of reducing the number of possible values of a quantity, thereby reducing the number of bits needed to represent it. Entropy coding is a technique for representing the quantized data as compactly as possible.
On a SUN Sparcstation 2, the timings increase (at a rate of 0.005 second/pixel) from about 20 seconds for a 64**2 pixel image to about 320 seconds for 256**2 pixels.
鄙人用的是Intel N100 CPU. 单线程８皇后程序和直接puts("92")的体感速度一样．:-) 在7000局象棋里，用电脑搜索有绝杀的，也没跑多长时间。ffmpeg几十张gif转mp4秒出（图片尺寸小）。没等我找到合适的店铺，我已经不需要快电脑了。
These times are much longer than for comparable functions written in a low-level langauge such as C. For example, a C program performed the same computations in under 2 seconds for an image of 2562 pixels, more than 100 times faster than our Mathematica functions. 哦。也许数学软件可以降低一点点神秘度：不必苦思“这不得慢死？” Just do it.