第 1 章　歐幾里得與花拉子密：古代幾何邏輯與「演算法」詞彙的誕生#

本章導言#

演算法的第一個黃金時代不在計算機時代，而在古代地中海與伊斯蘭世界。本章三節：1.1 歐幾里得輾轉相除法；1.2 花拉子密與「algorithm」的字源；1.3 算盤與阿拉伯數字的計算基礎設施。

1.1 歐幾里得（Euclid）與輾轉相除法：公元前 3 世紀《幾何原本》裏流傳兩千年的最大公因數尋找藝術#

1.1.1 一條被寫進文明基因的程序#

《幾何原本》（約公元前 300 年）第七卷命題 I–II 給出求兩數最大公因數的方法：以小除大取餘，再以餘除除數，輾轉直至餘為零。用現代偽碼寫出：

while b ≠ 0:
    (a, b) ← (b, a mod b)
return a

這是現存最早、且至今仍在使用的演算法之一——1969 年 Knuth 的《計算機程式設計藝術》開篇即以它示範什麼是演算法。其效率有保證：最壞情形相鄰斐波那契數，步數約為輸入位數的 5 倍（拉梅定理，1844）。

1.1.2 為什麼它是「演算法」而非「技巧」#

《幾何原本》的體系是公理—定義—命題—證明：輾轉相除法附有正確性證明（以更相減損術終止性論證），輸入任意、步驟有限、結果唯一——完整滿足今日演算法的定義。這說明演算法的本質要件（明確性、有限性、正確性）在兩千三百年前已被寫下。

1.1.3 傳播與再生#

• 婆羅摩笈多（628 年）與花拉子密（9 世紀）吸收印度與希臘算術，把「步驟化」推向代數；
• 斐波那契《計算之書》（1202）把阿拉伯記數與此類程序帶入歐洲商業；
• 1960 年代，Stein 以二進制移位改寫（binary GCD），輾轉相除法進入硬體與編譯器優化——古老程序持續演化。

1.1.4 前因後果#

• 前因：巴比倫六十進制與埃及單位分數的計算傳統＋希臘公理化思潮（泰勒斯、畢達哥拉斯）。
• 事件：約前 300 年《幾何原本》成書，亞歷山大圖書館成為知識中介。
• 後果：公理化＋程序化的雙重傳統被伊斯蘭數學繼承，直接通往 1.2 花拉子密的代數革命。

下一節：1.2 花拉子密