《數學與泛型程式設計：高效程式設計的奧秘》一第2章 算法初談

算 法 初 談

摩西很快就學會了算術與幾何。

……這些知識是他從埃及人那裡學來的，

埃及人最重視的研究科目是數學。

——亞曆山大的斐洛（Philo of Alexandria），《摩西生平》（Life of Moses）

算法（algorithm）是用來完成計算任務的一系列有限步驟。由于算法與計算機程式設計的關系特别密切，是以很多人或許認為，算法是一個來自計算機科學專業的概念。其實算法這個詞已經有幾千年曆史了。數學中充滿了各種各樣的算法，有些算法我們天天在用，就連國小生計算加法時所用的豎式（long addition）都可以說是一種算法。

盡管算法的曆史很悠久，但它并不是天生就有的，而是由人發明出來的。雖然我們并不清楚第一個發明算法的人是誰，但我們知道，早在四千多年前埃及就已經有了某些算法。

*

古埃及文明以尼羅河為中心，尼羅河發洪水之後，土壤就變得肥沃起來，進而促進了古埃及的農業發展。可是問題在于，每次洪水過後，用來劃分财産邊界的那些标志也随之消失了。于是，埃及人就用繩子丈量距離，并拟定一套流程，使自己能夠根據早前的書面記錄來恢複當時的邊界劃分情況。有一批專職的祭司負責研究與此有關的數學技巧，這些人叫做“rope-stretcher”（拉繩者），希臘人後來把他們稱為geometer，也就是“Earth-measurer”（地形測量者）的意思。

我們很少發現與古埃及人的數學知識有關的文字記錄。對于那個時期，目前隻發現了兩份數學文獻，其中一份就是此處要提到的萊因德數學紙草書（Rhind Mathematical Papyru），它以蘇格蘭收藏家萊因德得名。萊因德在埃及所買的這份紙草書是公元前1650年左右由一位名叫阿姆士（Ahmes）的抄寫員所寫的。其中含有一系列算術與幾何問題，而且還列有一些計算用的表格。這份卷軸裡面所寫的第一個算法是一種能夠迅速計算乘法的技巧，此外還有第二個算法，用來迅速地計算除法。我們首先來講這個快速乘法算法，在本書後面的章節中大家會發現，該算法當今依然是一項重要的運算技巧。