快速傅里叶变换(FFT):史上最巧妙的算法?
The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?
频道:Reducible · 时长:28:23 · 发布:2020-11-14 · 播放:2296182
简介
Reducible 对快速傅里叶变换的视觉讲解,以多项式乘法为动机。它展示了如何通过提出正确的问题来发现 FFT 的关键思想。
HN 为什么推荐
HN 一再称其为绝妙的解释,让 FFT 豁然开朗,有些人会定期重看。
它从多项式乘法推导出 FFT 算法,非常精彩。我大约每 6 个月重看一次。 — HN, 2024
中文字幕节选
算法的世界浩瀚无边,但我们通常可以将它们分为两大类 第一类是那些本身就很有用的算法,比如标准的图 算法如DFS或BFS,这些算法无处不在,它们 高效,因此我们喜欢理解它们。第二类我们研究的算法 是那些纯粹优美的算法,想想你第一次看到 汉诺塔那极其简单的递归实现时,如果你有灵魂,你 会感到一种惊奇,一种对如此优雅算法的敬畏。它 实际上并不那么有用或高效,但我们仍然研究 它,就像我们喜欢读小说一样,它启发我们,激发 跳出框框的思考。今天我想谈一个算法,它理所当然地 属于这两类,也是我个人最喜欢的算法:快速傅里叶 变换。快速傅里叶变换,简称FFT,毫不夸张地说,是 上世纪最重要的算法之一。我们今天拥有的许多现代技术, 如无线通信、GPS,实际上任何与 广阔的信号处理领域相关的东西,都依赖于FFT的洞见。但它 也是你将看到的最美丽的算法之一。其深度和 其中蕴含的绝妙想法之多,简直令人震惊。人们很容易错过FFT的 美丽之处,因为它通常是在相当复杂的背景下介绍的, 需要很多先决知识,比如离散傅里叶变换、时 域到频域的转换等等。公平地说,要完全 欣赏FFT的应用,你确实无法避免这些概念。 但我想做点不同的事。我们将采用基于发现的方法 来学习FFT,在一个你们都熟悉的背景下:多项式 乘法。在我看来,这个视频的结构就是 从一些共同点开始,然后慢慢提出问题,希望能 引导你们发现快速傅里叶变换背后真正巧妙的想法。 好了,让我们开始吧。 这里的设定很简单:给定两个多项式,求它们的乘积。 我们的任务是为此问题设计一个高效算法。数学上, 我们知道一种算法可以通过反复应用分配律 来乘多项式。你们可能从任何代数课上就本能地 应用过这个算法。但在尝试这个想法之前,我们首先要解决的 问题是多项式在计算机中的表示。最自然的表示 方式是通过系数,我们将系数映射到列表。 将系数按以下顺序排列会有所帮助,主要是因为现在 第k个索引的系数映射到第k次项的系数。我们将 这种表示称为多项式的系数表示。 一般来说,给定两个d次多项式,乘积的次数将是2d, 而如果我们真的用最自然的分配律方法 来实现这个算法,其运行时间将是O(d²),因为 多项式a中的每一项都必须与多项式b中的所有项相乘。 现在的问题是:我们能做得更好吗?第一个真正聪明的想法 来自于稍微不同地思考多项式。为了看到关键洞见,让我们 看一个最简单的多项式:一次多项式,或线性函数。 我们可以用恰好两个系数来表示任何直线:一个用于零次项, 一个用于一次项。使这种表示有效的关键部分 是每个表示都与唯一的直线一一对应。还有哪些 直线的表示具有这个性质?实际上有几种合理的 表示,但我们将要使用的是两点表示。 我们从几何学知道,任何直线都可以由两个不同的点表示, 事实证明,对于一般多项式有一个简洁的扩展,我 将在这里陈述:任何d次多项式都可以由d+1个 点唯一表示。例如,如果我给你三个随机点,这意味着
HN 上的讨论
我几乎总是更喜欢文字而不是视频,但关于同一主题的这个视频太棒了:[VIDEO]。我每年至少看一次。另外,博客文章(进而这个 HN 帖子)的标题在我看来并不完全正确:它不是关于 DFT,而是专门关于 FFT。 — tverbeure, 2025-10
如果你还没看过,你应该看看这个视频:[VIDEO] 它从多项式乘法推导出FFT算法,非常棒。我大约每6个月重看一次。 — tverbeure, 2024-07
那个视频对我也有同样的效果。我也喜欢关于快速傅里叶变换的reducible视频,以及Veratasium分享一些有趣历史的那篇。Reducible - FFTs有史以来最巧妙的算法[VIDEO] Veritasium - 有史以来最重要的算法[LINK] — kippinitreal, 2023-01
正如作者提到的,信号处理中的卷积和概率中的卷积在两种不同语境下本质上是等价的。有趣的是,多项式乘法背后也是同一个概念。在离散情况下,我们有代表...(离散化)概率密度 <-> (离散)信号强度 <-> 多项式系数...的向量的平行。如果我们看离散情况,由于卷积操作计算成本高(O(n^3)),人们通常依赖快速傅里叶变换算法(FFT),其运行时间为O(n log(n))。一个关于FFT应用于多项式乘法的优秀且非常愉快的视频是[VIDEO]。 — squaredot, 2022-12
不是书,但我真的很喜欢这个人的视频:[VIDEO]。我通常吃午饭时看。他做得非常棒。 — withinboredom, 2021-11
相关视频
- 漫威交响宇宙 · Every Frame a Painting · 13:35
- 你能解决气候变化吗? · Kurzgesagt – In a Nutshell · 15:49
- 但什么是黎曼 zeta 函数?可视化解析延拓 · 3Blue1Brown · 20:28
- 但比特币究竟是如何运作的? · 3Blue1Brown · 25:15
- 高维空间中的飞镖(与 3blue1brown 合作)- Numberphile · Numberphile · 32:11
- 拯救旅行者1号!- Bruce Waggoner 在 !!Con 2024 · !!Con · 35:25
- HC2023-K2:深度学习硬件 · hotchipsvideos · 1:05:27
- 最被低估的算法 · Veritasium · 26:33
- Unix 与 Google · FOAM · 7:15
- 但什么是傅里叶变换?视觉介绍。 · 3Blue1Brown · 19:41
- D/A 与 A/D | 数字展示与讲解(Monty Montgomery @ xiph.org) · FL Studio · 23:52
- CppCon 2017: Matt Kulukundis “逐步设计一个快速、高效、缓存友好的哈希表” · CppCon · 59:33
- 现代字典 by Raymond Hettinger · SF Python · 1:07:41
- CppCon 2014: Chandler Carruth “算法效率,数据结构性能” · CppCon · 1:13:41
- CppCon 2017: Juan Pedro Bolivar Puente “后现代不可变数据结构” · CppCon · 1:05:59
- 排序算法:速度存在于人们的头脑中 - Andrei Alexandrescu - CppCon 2019 · CppCon · 1:29:55