大家好，argmin的读者们！今天的文章将探讨OpenAI的数学库中声称可以更快计算傅里叶变换的部分内容。内容比通常的更为技术化，但我尝试为需要复习信号处理或计算复杂度的人添加一些教程材料。快速傅里叶变换（FFT）是数字信号处理领域最重要的创新之一，也是我最喜欢的算法之一。FFT是提取信号频率内容的一种快速方法，可以让你快速分析、过滤和处理不同频段的频率。傅里叶变换通过简单的点积计算每个频率带中的能量。设x表示你的输入，一个长度为n的样本数组，f是一个频率。那么x在f处的频率内容可以通过如下公式计算：对于数字信号，一些数学表明 شما 你只需要计算n个点积，每个频率为2π/n的倍数，以理解全部频率内容。天真地说，这需要对每个频率进行n次乘法和加法。因此，计算整个傅里叶变换似乎需要n²次算术操作。快速傅里叶变换是詹姆斯·库利（James Cooley）和约翰·图基（John Tukey）在1965年提出的一种巧妙的递归程序。其主要思路是对长度为n的傅里叶变换进行重排列，计算长度为n/2的两个傅里叶变换，并使用基本的算术操作重新组合输出。重排列和重新组合需要线性数量的算术操作。通过迭代重复这个过程，即log₂(n)次数，可以计算完整的离散傅里叶变换。在记账过程中，FFT在少于5n log₂(n)的算术操作中计算出长度为n的傅里叶变换。为了让这个加速更加具体，当n为1,000时，n²是1,000,000，而5*n log n大约是50,000，形成20倍的速度提升。当n为1,000,000时，速度提升为10,000倍。根据信号处理应用的约束，这些速度提升可能决定了一个变换是否可计算。自从FFT发明以来，人们一直在寻求更快的傅里叶变换。其中一个问题是你能快到什么程度。看起来你可能至少需要n次操作来计算FFT，因为仅仅写下来就需要n步。FFT比这个合理的速度极限慢5*log₂(n)倍，而这个5*log₂(n)因子可能很大。当n为一万亿时，它为200。你能够巧妙地减少200的前因子吗？那么，令人惊讶的是，在OpenAI上周对数学界的庞大论文抛弃中，他们声称拥有一种更快的傅里叶变换。他们的“main.pdf”文件中主要的主张让我非常好奇这里发生了什么。理论上，log(n)项比标准FFT的略微小了一点。我读过这篇论文吗？当然没有。OpenAI没有人读过这篇论文，所以我为什么要读呢？我做了每个世界数学家在处理AI糟糕数学时所做的事情：我把它反馈回糟糕机器里，并使用聊天机器人界面进行信息检索提取相关事实。从人性化的角度来说：我问ChatGPT它对自己的输出有什么看法。这就是我们现在进行数学研究的方式。真是个奇妙的世界。不幸的是，我没有找到一种更快的傅里叶变换。相反，我发现了当形式主义与现实完全脱节时，应用数学理论中产生的腐臭，导致“突破”不过是数学家无法用自然语言恰当地说明游戏规则的产物。首先，“大O”表示法被滥用得如此严重，以至于变得毫无意义。让我们回顾一下定义，这在我大学时给我留下了深刻印象。一个算法的运行时间T(n) = O(F(n))，当且仅当存在一个整数N和一个常数C，使得在n足够大时，算法实际所需的步数是常数乘以某个方便的函数F(n)的上界。F(n)通常是一些熟悉且可解释的东西，比如多项式或指数函数。这个表示法表明，我们只关心当计算规模较大时会发生什么。我们关心计算时间的渐进增长率。所有常数都是等效的。大O表示法对于算法会计中的捷径很有用，但它也允许显著的逻辑懒惰。如果我们想要一个实际上更快的FFT，我们想要一个在合理大小的n下需要少于50n次操作的算法。但O(n)并不意味着50n。它可能意味着10^80n。这将被认为是“线性时间”算法。一个需要n + 10^80的算法也被视为大O范围内的线性时间算法。只有当n大于10^80时才具有线性时间保证的算法，亦被认为是线性时间。10^80大约等于数的数量。