楼主
slowFT
第一次实现了“不用任何数学知识，编程初学者都可以写的傅里叶变换”。
基于相减能量最低法和三分法的慢速傅里叶变换。
这是一个“暴力搜索”傅里叶变换算法，它的核心思想极其简单：对每一个可能的频率，通过反复尝试找到最匹配的正弦波。
判断匹配程度的方法是，从原信号中减掉，剩余信号总能量越低，越匹配。
算法的工作方式：
1. 计算平均值，找到直流分量
2. 对每个频率，先搜索最佳相位：在0到1之间使用三分法不断缩小区间，找到使减去后能量最小的相位
3. 再用同样的方法搜索最佳幅度：在0到一个很大的数之间使用三分法找最优值
4. 最终每个频率都得到一对值（幅度，相位）
与传统傅里叶变换的区别：
- 不需要任何数学知识：不理解复数、欧拉公式、正交性也能看懂
- 直观易懂：就是在做“波形减去尝试”——调整正弦波的位置和高度，看它能减掉多少能量
- 极其缓慢：对每个频率都要进行几十次搜索，每次搜索都要遍历全部数据点
适用场景：
- 教学演示：让学生理解傅里叶变换的物理意义
- 自定义基函数：可以搜索方波、三角波等其他波形
- 验证傅里叶变换算法的正确性和可行性
局限性：
- 计算复杂度极高：O(N² × 迭代次数)，比标准FFT慢到不可理喻
这不是一个实用的算法，但它是理解傅里叶变换“到底在干什么”的最佳入门代码。
代码如下
<?php
function slowFT($array){
$FT=[];
$zero=array_sum($array)/count($array);
$FT[0]=[$zero,null];
for($freq=1;$freq<floor(count($array)/2)-1;$freq++){
$phase=get_phase($array,$freq);
$size=get_size($array,$freq,$phase);
$FT[$freq]=[$size,$phase];
}
return $FT;
}
function customsin($count,$freq,$phase,$size,$x){
return $size*sin(2*pi()*($freq*$x/$count-$phase));
}
function getenergy($freq, $phase, $size, $array) {
$energy = 0;
for ($x = 0; $x < count($array); $x++) {
$energy += ($array[$x] - customsin(count($array), $freq, $phase, $size, $x)) ** 2;
}
return $energy;
}
function get_phase($array,$freq){
$min=0;
$max=1;
for($i=0;$i<15;$i++){
$mid1=$min+($max-$min)*1/3;
$mid2=$min+($max-$min)*2/3;
$energy1=getenergy($freq,$min,1,$array);
$energy2=getenergy($freq,$mid1,1,$array);
$energy3=getenergy($freq,$mid2,1,$array);
$energy4=getenergy($freq,$max,1,$array);
$sum1=$energy1+$energy2;
$sum2=$energy2+$energy3;
$sum3=$energy3+$energy4;
if($sum1<=$sum2 && $sum1<=$sum3){
$max=$mid1;
}elseif($sum2<=$sum1 && $sum2<=$sum3){
$min=$mid1;
$max=$mid2;
}else{
$min=$mid2;
}
}
return ($min+$max)/2;
}
function get_size($array, $freq, $phase) {
$min = 0;
$max = 200000000;
for ($i = 0; $i < 80; $i++) {
$m1 = $min + ($max - $min) / 3;
$m2 = $min + ($max - $min) * 2 / 3;
$energy1 = getenergy($freq,$phase,$m1,$array);
$energy2 = getenergy($freq,$phase,$m2,$array);
if ($energy1 < $energy2) {
$max = $m2;
} else {
$min = $m1;
}
}
return ($min + $max) / 2;
}