FFT的LISP实现
FFT变换，即快速傅里叶变换，是一种很重要的变换，应用很广泛。我浏览了网上的实现FFT变换的语言大多数是C或者C++,python等，且具体实现中一般不采用递归方式，而采用蝶形运算，因为这些语言可以较为方便地访问数组。而LISP语言对于访问数组不太灵活，递归是其强项。因此在这个实现中，我采用了递归方式。另外，autolisp语言不支持复数，只能自己构造复数来实现。
对FFT不了解的，可以参考如下链接：快速傅里叶变换(FFT)——有史以来最巧妙的算法？
另外，这个LISP的实现也借鉴（抄袭{:1_12:}）了如下链接的代码：A Fast Fourier Transform in Lisp
对此处的代码做了一点点修改。
下面是其主要代码：
;;;=============================================================
;;; 获取偶数项
;;;=============================================================
(defun evens (f)
(if f
(cons (car f) (evens (cddr f)))
)
)
;;;=============================================================
;;; 获取奇数项
;;;=============================================================
(defun odds (f)
(if f
(cons (cadr f) (odds (cddr f)))
)
)
;;;=============================================================
;;; 求w(利用欧拉公式求系数)
;;;=============================================================
(defun phase (s k n / x)
;;(exp (/ (* 0+2i s k 3.1415926535 ) N) )
(if (> s 0)
(setq x (/ (* PI k) N))
(setq x (/ (* (- pi) k) N))
)
(list (cos x) (sin x))
)
;;;=============================================================
;;; 求每一项乘以系数（即对复数旋转）
;;;=============================================================
(defun rotate (s k N f / )
(if f
(cons
(CMP::MUL (phase s k N) (car f))
(rotate s (1+ k) N (cdr f))
)
)
)
;;;=============================================================
;;; 此处修改仅仅是为了减少递归深度
;;;=============================================================
(defun PFFT (s f / e o)
(if (= 2 (length f))
(list
(apply 'CMP::ADD f)
(apply 'CMP::SUB f)
)
(combine s (PFFT s (evens f)) (PFFT s (odds f)))
)
)
;;;=============================================================
;;; With these preliminaries PFFT is simple
;;; 此段为原来方式(the original way)
;;;=============================================================
(defun PFFT1 (s f / e o)
(if (= 1 (length f))
f
(combine s (PFFT1 s (evens f)) (PFFT1 s (odds f)))
)
)
;;;=============================================================
;;; 合并奇偶两部分
;;;=============================================================
(defun combine (s ev od)
(plusminus ev (rotate s 0 (length od) od))
)
;;;=============================================================
;;; 奇偶两部分相加减
;;;=============================================================
(defun plusminus (a b)
(append (mapcar 'CMP::ADD a b) (mapcar 'CMP::SUB a b))
)
源代码请参见附件：
欢迎诸位的建议或者更好的想法！
说明：
1，返回的结果可能猛一看，与网上的结果不太一样，其实是相同的，只不过一个是顺时针，一个是逆时针，也可以在函数rotate里面修改1+ 为1-便一致了。
2，此FFT是针对大量数据有优化效果，数据少可能起不到加速。
虽然 我现在看不懂 但是感觉好牛 我会继续学习 虽然 我现在看不懂 但是感觉好牛 我会继续学习 感谢分享{:1_1:}{:1_1:} 谢谢分享，高飞牛！ 感谢分享有用的知识。
页:
[1]