與所有的古文明一樣，埃及的計數系統也沒有按位置計數這一概念，而且無法表示0。于是，乘法計算起來就特别困難，隻有少數受過訓練的專家才會做。（你可以想象一下：如果自己隻能像使用羅馬數字那樣來做運算，而且要計算的數字又很大，那麼算起來是相當困難的。）
怎樣來定義乘法呢？寬泛地說，我們可以認為乘法就是“把某物多次加到它自己上面”，如果說得嚴謹一些，那麼可以分兩種情況來定義：一種情況是乘以1，另一種情況是乘以一個大于1的數。
我們将乘以1的乘法運算，定義如下：
1a = a（2.1）
接下來需要定義另一種情況，也就是怎樣根據某數的n倍來計算其n+1倍。有些讀者或許已經發現這是一個歸納的過程，本書稍後會以更為正規的形式來使用歸納法。
（n + 1）a = na + a（2.2）
有一種辦法可以計算n與a的乘積，那就是把n個a連加起來。然而這種辦法對于較大的數字來說相當乏味，因為總共要計算n-1次加法才行。此算法可以用C++代碼表示為：
上面這個函數中的兩行代碼分别與等式（2.1）及等式（2.2）相對應。和古埃及人計算乘法時的情況一樣，a與n都必須是正數。
阿姆士所描述的乘法算法，古希臘人将其稱為“埃及乘法”（Egyptian multiplication），而現在有很多人則把它叫做“俄羅斯農夫算法”（Russian Peasant Algorithm）。這種算法所依據的原理是：
4a =（（a + a）+ a）+ a
=（a + a）+（a + a）
這個原理是根據加法結合律推算出來的：
a +（b + c）=（a + b）+ c
如果采用這個辦法，那麼隻需把a + a的值計算一次就行了，這樣可以降低加法運算的次數。
埃及乘法算法的思路是：反複地将n減半，并将a加倍，同時求出a的各種倍數，這些倍數與a的比值都是2的整數次幂。在那個時代，算法并不是用a或n這樣的變量來描述的，而是以具體的數字舉例，然後說：“同樣的操作還可以運用在其他數字上面”。阿姆士自然也不例外，他以41×59（也就是說n = 41，a = 59）為例，示範了怎樣通過下面這種表格來執行該算法：
1 √ 59
2 118
4 236
8 √ 472
16 944
32 √ 1888
表格左邊那一列的數字都是2的整數次幂，而對于右邊那一列來說，其中的每一個數字都是它上方那個數字的兩倍（之是以要采用這種反複翻倍的辦法來清單，是因為把同一個數字加到它自己上面計算起來要相對容易一些）。如果用二進制的形式來表示41這個數，那麼值為1的那些二進制位就可以與表格中勾選的那些行分别對應起來。于是，這張表格實際上就相當于下面這個算式：
41×59 =（1×59）+（8×59）+（32×59）
該等式的右側出現了幾個59的倍數值，這些倍數值都可以通過對59進行适當的翻倍而計算出來。
由于該算法在将n減半的時候需要判斷n是奇數還是偶數，是以盡管沒有直接的證據，但我們依然能夠推測出：古埃及人已經知道了奇數和偶數之間的差別。因為古希臘人宣稱他們是從埃及人那裡學到數學的，是以這一點是可以肯定的。如果把埃及人定義奇數和偶數的辦法表示成現代的數學記号，那就是：
此外，我們還要依賴下面這個關系式：
odd（n） half（n）= half（n-1）
現在，就可以用C++代碼把埃及乘法算法實作出來了：
odd(x)函數可以通過判斷x的最低有效位來實作，而half(x)函數則可以通過對x右移來實作：
multiply1函數要執行多少次加法呢？每次調用該函數時，它都要執行a + a語句中的那個加法運算，而由于我們在對n減半的過程中會遞歸地調用該函數，是以總共要調用log n次。此外，有些時候還需要執行result + a語句中的那個加法運算，于是總的加法次數就是：
其中的v(n)表示在n的二進制形式中有多少個值為1的二進制位，這個數量也稱為種群計數（population count、pop count）。至此，我們已經把一個複雜度為O(n)的算法，優化成了複雜度為O(log n)的算法。
這個算法總是最優的嗎？其實并不是這樣。比方說，如果要計算某數與15的積，那麼按照剛才的公式，總共需要執行的加法次數就是：
然而實際上隻需要像下面這樣，執行5次加法就夠了：
上面這種連加操作稱為加法鍊（addition chain）。我們剛才找到了15這個數字的最優加法鍊（optimal addition chain）。盡管阿姆士所記錄的算法在某些情況下并不是最優的，但它畢竟可以很好地應對許多數字。
習題2.1 對于每一個小于100的正整數n來說，尋找其最優加法鍊。
在閱讀這部分内容的時候，你可能會發現，如果第一個數比第二個數要大，那麼把兩者交換之後再進行運算應該會更快一些（例如計算3×15，要比計算15×3更為容易）。确實是這樣，而且古埃及人也知道這一點。但筆者此處并不打算把這個優化技巧運用到算法中，因為我們将要在第7章對算法進行泛化，使它不僅可以用整數當參數，而且還可以用整數之外的其他類型做參數，到了那個時候，參數之間的順序就會變得很重要了。