读算法简史：从美索不达米亚到人工智能时代03π和傅里叶

1. 不断扩展的圆圈

1.1. 哥贝克力石阵

• 1.1.1. 哥贝克力石阵令人印象深刻，但它真正的不同寻常之处在于其建造年代
  
• 1.1.2. 该遗址可追溯到公元前10000年至公元前8000年，远远早于古苏美尔
  
• 1.1.3. 成为世界上已知的最古老的巨石遗址
  

1.2. 圆的根本特征是从中心点到边缘的距离是恒定的

• 1.2.1. 这个距离就是圆的半径(radius)
  
• 1.2.2. 圆的直径(diameter)或宽度是其半径的两倍
  
• 1.2.3. 一个圆的周长(circumference)是其边缘的长度
  
• 1.2.4. 一个圆越大，它的周长和直径就越大
  
• 1.2.5. 圆的周长略大于它直径的三倍
  
  
  
  • 1.2.5.1. 比率对于所有大小的圆来说都是恒定的
    
  • 1.2.5.2. 最早的近似估计3，只对了一位数
    
  • 1.2.5.3. 约在公元前2000年，巴比伦人估计π=3.125，算对了两位数
    
  • 1.2.5.4. 埃及莱因德纸草提供了一个略好一点的近似值=3.16049，接近算对了三位数
    
  • 1.2.5.5. 计算π值的第一个真正突破来自希腊数学家阿基米德
    
  
  
• 1.2.6. 这个确切的比率如今用希腊字母π来表示
  
  
  
  • 1.2.6.1. 威尔士数学家威廉·琼斯(William Jones)在1707年首次使用π表示圆周率，古希腊人并不这样用
    
  
  

1.3. 阿基米德

• 1.3.1. 约公元前287—公元前212年
  
  
  
  • 1.3.1.1. 被认为是古代最伟大的数学家之一
    
  • 1.3.1.2. 阿基米德在锡拉库萨陷落时被一名罗马士兵杀害了
    

    1.3.1.2.1. 公元前212年阿基米德被杀害是罗马统治欧洲的先兆
    

    
    
  
  
• 1.3.2. 想要测量一个不规则物体的体积，可以通过测量它浸入水后的排水量来实现
  
  
  
  • 1.3.2.1. 这一推论使他得以确定王冠的密度
    
  
  
• 1.3.3. 研究成果是一种前所未有的精确计算π值的算法
  
  
  
  • 1.3.3.1. 正多边形与圆形的外形近似
    
  • 1.3.3.2. 多边形的周长很容易计算，因为它的边是直的
    
  • 1.3.3.3. 正多边形的边越多，越接近于圆形
    
  • 1.3.3.4. 在将近2000年之后的1699年，阿基米德的算法才被超越
    
  
  
• 1.3.4. 算法
  
  
  
  • 1.3.4.1. 以一对内多边形和外多边形的周长作为输入
    
  • 1.3.4.2. 内多边形周长和外多边形周长相乘
    
  • 1.3.4.3. 除以二者之和
    
  • 1.3.4.4. 得出一个新的外多边形的周长
    
  • 1.3.4.5. 把这个新外多边形的周长乘以之前的内多边形周长
    
  • 1.3.4.6. 求平方根
    
  • 1.3.4.7. 得出一个新的内多边形的周长
    
  • 1.3.4.8. 输出新的内多边形和新的外多边形的周长
    
  
  
• 1.3.5. 阿基米德算法的美妙之处在于，它可以反复运行
  
  
  
  • 1.3.5.1. 一次运行得到的输出可以作为下一轮迭代的输入进入算法中
    
  • 1.3.5.2. 这样一来，十二边形就可以转化为二十四边形
    
  • 1.3.5.3. 四十八边形可以变成九十六边形，以此类推
    
  • 1.3.5.4. 每一次重复，内多边形和外多边形都向圆更逼近了一点，得出更好的π估计值
    
  
  
• 1.3.6. 一个正六边形在轮廓上近似于六个完全相同的三角形边对边合在一起，每个重合的边都指向中心点
  
  
  
  • 1.3.6.1. 这些三角形是等边(equilateral)三角形，也就是说，所有三条边的长度相等
    
  • 1.3.6.2. 正六边形的周长与直径之比是=3
    
  • 1.3.6.3. 3是π的一个合理近似值
    
  • 1.3.6.4. 多边形的边越多，用它获得的π的近似值就越可靠
    
  
  
• 1.3.7. 阿基米德完成了一个九十六边形的计算，得到π的两个估计值
  
  
  
  • 1.3.7.1. 前者精确到四位数
    
  • 1.3.7.2. 后者不那么精确，但更简单，因而更受欢迎
    
  
  

1.4. 把π的真实值全写下来是不可能的

• 1.4.1. 18世纪60年代，约翰·海因里希·兰伯特(Johann Heinrich Lambert)证明了π是一个无理数(irrational number)
  
  
  
  • 1.4.1.1. 意味着想要枚举π需要无限多位数字
    
  • 1.4.1.2. 无论枚举到什么程度，数字都不会出现循环
    
  • 1.4.1.3. 人们最多能做到获取π的近似值
    
  
  

1.5. 如果没有π，我们就很难对圆和球体进行推理

• 1.5.1. 计算圆周运动、旋转和振动将成为数学难题
  
• 1.5.2. π的值被用在许多实际应用中，从建筑到通信、从航天飞行到量子力学
  

2. 世界纪录

2.1. 文明出现在中国的时间与出现在美索不达米亚和埃及的时间差不多

• 2.1.1. 中国的城市社会大约最早是在长江和黄河沿岸发展起来的
  
• 2.1.2. 对中国早期数学知之甚少，因为当时用来写字的竹简容易腐烂
  

2.2. 现存最古老的中国数学著作《周髀算经》于公元前300年左右问世。这本书主要涵盖历法和几何，其中包括勾股定理
2.3. ​《九章算术》是一部类似于莱因德纸草的数学问题汇编，从大约同一时期流传下来
2.4. 中国对π值的探究似乎比西方要执着很多

• 2.4.1. 公元264年，刘徽用一个96边的内多边形得到了一个近似值3.14，精确到了三位数
  
  
  
  • 2.4.1.1. 他将这个方法扩展到一个有3072条边的多边形，得到了一个改进的近似值3.14159，精确到了六位数
    
  
  
• 2.4.2. 公元5世纪，祖冲之在儿子祖暅的协助下做出了更准确的估计
  
  
  
  • 2.4.2.1. 算出的上限和下限分别为3.1415927和3.1415926，精确到了七位数，创造了新的世界纪录
    
  • 2.4.2.2. 成就屹立了近900年，是他们卓越贡献的有力证明
    
  
  

2.5. 根据吉尼斯世界纪录，π的最精确值有31万亿位

• 2.5.1. 产生这一数值的程序是由来自日本的埃玛·岩尾春香(Emma Haruka Iwao)编写的
  
• 2.5.2. 程序在谷歌云上的25个虚拟机上运行计算，共花费了121天
  

3. 花剌子模

3.1. 约在公元762年，哈里发哈伦·拉希德(Harun al-Rashid)在他的新首都巴格达建立了智慧馆(Bayt al-Hikmah)

• 3.1.1. 他的继任者不断扩建智慧馆，使之成为9世纪到13世纪一个重要的知识中心，这段时期现在被称为伊斯兰黄金时代
  

3.2. 智慧馆最有影响力的知识分子是穆罕默德·伊本·穆萨·阿尔·花剌子模

• 3.2.1. 他在780年至850年间居住于巴格达
  

3.3. 《代数学》(The Compendious Book on Calculation by Completion and Balancing)是一部代数著作

• 3.3.1. 英语中的“代数”(algebra)一词，就是从这本书的阿拉伯语标题（al-jabr，意思是恢复平衡）派生而来的。这本书描述了如何使用算法来解决数学问题，特别是线性方程和二次方程
  

3.4. 《印度算术法》​（On the Hindu Art of Reckoning，约825年）一书中描述了十进制数字系统，我们今天使用的数字系统也在其中

• 3.4.1. 十进制数字系统起源于印度河谷文明（今巴基斯坦南部）​，该文明大约繁盛于公元前2600年，与吉萨金字塔的建造时间大致是同一时代
  
• 3.4.2. 9个非零的印度-阿拉伯数字(1-9)于公元前3世纪到公元2世纪之间出现在该地区
  
• 3.4.3. 大约在同一时期，零(0)这个数字终于在印度出现了
  
• 3.4.4. 人们接受新数字系统的速度很慢
  
  
  
  • 3.4.4.1. 用了几个世纪的时间，罗马数字（I、II、III、IV、V等）才被印度-阿拉伯数字取代
    
  • 3.4.4.2. 欧洲学者似乎非常乐于用算盘进行计算，并用罗马数字记录结果
    
  • 3.4.4.3. 直到16世纪，随着人们开始使用笔和纸来计算，十进制数字系统才成为首选
    
  
  
• 3.4.5. 英语中的“算法”(algorithm)一词正是来自《印度算术法》(Algoritmi de Numero Indorum)拉丁文译本书名中阿尔·花剌子模的名字
  

4. 层波叠浪

4.1. 观念的转变、沉重的赋税和一场场农业歉收引发了1789年的法国大革命
4.2. 傅里叶

• 4.2.1. 1768年，让-巴蒂斯特·约瑟夫·傅里叶（Jean-Baptiste Joseph Fourier）出生于法国欧塞尔
  
• 4.2.2. 傅里叶于1830年5月16日逝世
  
• 4.2.3. 他的名字后来被刻在埃菲尔铁塔的侧面，以此表彰他的科学成就
  

4.3. 傅里叶的《热的解析理论》(Théorie de la Chaleur)于1822年出版

• 4.3.1. 任何波形都可以看成适当时间延迟的和按比例放大缩小的谐波的加合
  
• 4.3.2. 傅里叶的假定后来被证明是正确的
  

4.4. 一次谐波（first harmonic）

• 4.4.1. 它的周期(period)——两个波峰之间的距离——等于泳池的长度
  

4.5. 二次谐波(second harmonic)。它的周期等于泳池长度的一半
4.6. 谐波序列叫作傅里叶级数(Fourier series)
4.7. 所有的波形——无论何种形状的波形——都是缩放和延迟谐波的加合

• 4.7.1. 缩放的意思是放大或缩小波形的大小
  
• 4.7.2. 放大会使波峰更高，波谷更低
  
• 4.7.3. 缩小则相反
  
• 4.7.4. 延迟一个波形意味着在时间上平移它
  
• 4.7.5. 延迟意味着波峰和波谷比之前更晚到达
  

4.8. 设定一次谐波的振幅(amplitude)是1

• 4.8.1. 一个波形的振幅是它与平衡位置之间的最大偏差
  
• 4.8.2. 谐波的振幅就是波峰的高度
  
• 4.8.3. 二次谐波的振幅是1/2
  
• 4.8.4. 三次谐波的振幅为1，延迟为1/2个周期
  
• 4.8.5. 如果我们把这些谐波进行加合，就能得到一个新的复合波(compound waveform)
  
  
  
  • 4.8.5.1. 波的叠加(superpose)
    
  
  

5. 傅里叶变换

5.1. 加合波形很容易

• 5.1.1. 要逆转这个过程就复杂得多
  

5.2. 如果给定一个复合波，如何确定组成复合波的谐波的振幅和延迟？

• 5.2.1. 答案就是使用傅里叶变换(Fourier transform，FT)
  

5.3. FT以任何波形作为输入，并将其分解为谐波组分

• 5.3.1. 它的输出是原始波形中分解出来的每一个谐波的振幅和延迟
  

5.4. 在计算机发明后的几十年里，傅里叶变换的真正力量才突显出来

• 5.4.1. 计算机可以快速地、低成本地分析各种波形
  

5.5. 样本(sample)

• 5.5.1. 计算机每隔一段时间就会对波形的水平采集一次“样本”​
  
• 5.5.2. 如果采样次数足够密集，数字列表就会给出波形形状的合理近似值
  

5.6. 相关系数(correlation)

• 5.6.1. 相关系数是对两个波形相似性的衡量，如果相关系数较高，就表明输入中的一次谐波较强
  

5.7. 振幅等于两个相关系数的平方和再除以样本数量后的平方根，延迟是通过计算两个相关系数的相对强度得出的
5.8. FT算法的工作原理

• 5.8.1. 以一个波形作为输入
  
• 5.8.2. 对每一个可能的谐波重复以下步骤
  
  
  
  • 5.8.2.1. 产生谐波
    
  • 5.8.2.2. 求输入与谐波的相关系数
    
  • 5.8.2.3. 将谐波延迟四分之一个周期
    
  • 5.8.2.4. 求输入与延迟谐波的相关系数
    
  • 5.8.2.5. 计算谐波的整体振幅和延迟
    
  • 5.8.2.6. 当所有谐波处理完毕后停止重复
    
  • 5.8.2.7. 输出每一个谐波的振幅和延迟
    
  
  

5.9. FT被广泛用于分析现实世界中的信号(signal)

• 5.9.1. 信号是现实世界中随时间变化的任何量
  
• 5.9.2. 声音信号是能被我们听到的气压的变化
  
• 5.9.3. 在语音识别系统（如Siri、Alexa）中，FT会在进一步分析之前将声音信号分解成其谐波组分
  
• 5.9.4. 数字音乐播放器（如Spotify、Tidal）依靠FT识别冗余谐波信息，从而降低数据存储量
  
• 5.9.5. 无线电信号是一种可以用电子设备探测到的电磁变化信号
  
  
  
  • 5.9.5.1. 在无线通信系统（如WiFi、DAB）中，FT可以使数据通过无线电信号得到有效传输和接收
    
  
  

6. 快速傅里叶变换

6.1. 现代设备使用一种原始算法的变体，它被恰当地命名为快速傅里叶变换，或简写为FFT
6.2. FFT发明于1965年，用以满足迫切的军事需要

• 6.2.1. 冷战期间，美国希望能够监视苏联的核试验
  
• 6.2.2. 唯一的方法是在友好国家的监测站测量爆炸引起的地震震动
  
• 6.2.3. 使用传统的FT来分析地震数据的速度非常慢
  
• 6.2.4. 科学家詹姆斯·库利(James Cooley，1926-2016)和约翰·图基(John Tukey，1915-2000)想出了一个新版本的算法，可以在很短的时间内产生相同的结果
  
  
  
  • 6.2.4.1. 库利-图基版的FFT使美军能将苏联的核试验定位在15千米的精度范围内
    
  
  

6.3. 算法利用谐波波形的对称性在不同的求相关系数阶段之间共享结果

• 6.3.1. 在谐波波形中，波谷只是波峰的反面
  
• 6.3.2. 波峰上升的那一半是下降部分的镜像
  
• 6.3.3. 高次谐波是低次谐波的加速版
  
• 6.3.4. 通过对中间结果的再用，消除了计算过程中不必要的重复
  

6.4. 在FFT“发明”近20年后，人们发现这个算法实际上已经存在180多年了

• 6.4.1. 伟大的德国数学家卡尔·弗里德里希·高斯(Carl Friedrich Gauss，1777-1855)在1805年将该算法用于天文学数据分析
  
• 6.4.2. 作为一个完美主义者，高斯生前没来得及将这些结果发表，这种方法最终是在他去世后出版的论文集中被发现的
  
• 6.4.3. 高斯1805年的笔记显示，他甚至早于傅里叶就开始了这方面的研究
  
  
  
  • 6.4.3.1. 这个算法称为高斯变换可能更合适
    
  
  

《道德经》：曲则全，枉则直，洼则盈，敝则新，少则得，多则惑。是以圣人抱一为天下式。不自见，故明；不自是，故彰；不自伐，故有功；不自矜，故长。夫唯不争，故天下莫能与之争。古之所谓曲则全者，岂虚言哉！诚全而归之。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！