九章算術(shù)開方算法系統(tǒng)和與現(xiàn)代計算機程序的比較

1、 九章算術(shù)開方算法系統(tǒng)與其與現(xiàn)代計算機程序的比較傅海倫中國古代把開方法與二次、三次或高次數(shù)字方程解法統(tǒng)稱為開方術(shù)。九章算術(shù)少廣章提出了完整的開平方、開立方程序。一、九章算術(shù)的開平方程序開平方相當(dāng)于求x2 = N的根。開方術(shù)曰：置積為實。借一算，步之，超一等。議所得，以一乘所借一算為法，而以除。除已，倍法為定法。其復(fù)除，折法而下。復(fù)置借算，步之如初，以復(fù)議一乘之，所得副以加定法，以除。以所得副從定法。復(fù)除，折下如前。1九章算術(shù)給出的術(shù)文言簡意賅，在開方籌式中每一個數(shù)字的記數(shù)和入算，都嚴(yán)格遵循位置值制。由于其中明確指出：復(fù)除，折而下、復(fù)除，折下如前，可見，這是一個具有一般性的機械化算法程序。即是說

2、，不論平方根有多少位數(shù)，反復(fù)實施這一程序都可求出來。所以，在此有必要對一般情形下的這種機械化程序加以剖析。以總的來說，開平方的程序是：首先作四行的籌式布算，即從上到下的四行依次布以方根（議所得）、被開方數(shù)（實）、法和借算，然后機械反復(fù)實施超、議、除、折的四大步驟，直至適盡、結(jié)束。超：將置于個位上的借算自右向左隔一位移一步，移到與實的最高位（N為奇數(shù)位）或次高位（N為偶數(shù)位時）對齊為止。若移n位，這相當(dāng)于將方程進(jìn)行倍根變換，變換后的方程為102nx12 = N的形式，如圖 (2)議：議得根的第一位得數(shù)為a1除：以a1乘借算102n得102na1作為法。置于第三行，使得以法除實時，恰得商a1，而余

3、數(shù)N1小于102na12：N ÷(102na1) = a1 + N1 / 102na12。        折：撤去借算，將法102na1加倍為定法，并將定法向右退一位為2102n1a1如圖 (4)，再在下行個位上布置借一算。        為求方根第二位得數(shù)，需要重復(fù)以上四個步驟：        超：將置于個位上的借算自右向左隔一位移一步，顯然祇需

4、移n1 步，即102n2如圖 (5)，這又相當(dāng)于求方程102n2x22 + 2102n1a1x2 = N102na12的正根。        議：復(fù)議得根的第二位得數(shù)a2        除：以a2乘借算102n2，加定法，得法：2102n1a1 + 102n2a2，同樣以法除實：(N102na12) ÷ (2102n1a1 + 102n2a2) = a2 + N2/(2102n1a1 + 102n2a2)，余數(shù)N2小于 (21

5、02n1a1 + 102n2a2)a2。如圖 (6)，如果余數(shù)為零，則開方完畢；若不為零，則折下如前，按接下來的程序步驟繼續(xù)開方。        通過對上述籌算開平方法的分析，可知它是根據(jù)下面這些公式來逐步推求的，與現(xiàn)代的迭代法完全一致，可以通過計算機來實現(xiàn)：        (a + b)2 = a2 + (2a + b)b        (a + b +

6、c)2 = (a + b)2 + 2(a + b) + cc        (a + b + c + d)2 = (a + b + c)2 + 2(a + b + c) + dd                開平方術(shù)文還有對幾種特殊情況的處理方法：一是被開方數(shù)為分?jǐn)?shù)的情形，要通分子，若分母是平方數(shù)，則分子、分母分別開方，然后相除，即A =b/a，；若分母不

7、可開，則以分母乘分子，開分子后再以分母除，即A = b/a，A = ab/a2，。二是開方不盡的情形，這相當(dāng)于求無理根，稱為不可開，求出整數(shù)部分后，以面命之。        顯然，有了以上程序和處理方法，任何一個數(shù)可以開平方，說明九章算術(shù)的術(shù)文更具有抽象性、普適性。二、九章算術(shù)的開立方程序        開立方相當(dāng)于求x3 = N的根。        九章算

8、術(shù)開立方術(shù)是：開立方術(shù)曰：置積為實。借一算，步之，超二等。議所得，以再乘所借一算為法，而除之。除已，三之為定法。復(fù)除，折而下。以三乘所得數(shù)，置中行。復(fù)借一算，置下行。步之，中超一，下超二等。復(fù)置議，以一乘中，再乘下，皆副以加定法。以定除。除已，倍下，并中從定法。復(fù)除，折下如前。3。        對比開平方術(shù)和開立方術(shù)，不難看出，兩種開方的程序基本上是統(tǒng)一的，都是通過籌式布算，機械重復(fù)地實施超、議、除和折的四大步驟，直至適盡，結(jié)束。祇是在開立方的籌式布算中，在法和借算之間增加一行中行，使原來的四行布算變?yōu)槲逍胁妓悖?/p>

9、并在相應(yīng)的超和折的步驟中有細(xì)小的變動或調(diào)整。對被開方數(shù)是分?jǐn)?shù)、或分母不是立方的情形，處理的方式也與開平方一樣，這說明，開立方的程序也具有抽象性和普適性，適應(yīng)于任何一個數(shù)的開立方。根據(jù)術(shù)文，對一般情形下的開立方與其與開平方程序過程的比較可見下表：商10na110na110na110na1實開平方NNN102na12N102na12N102na12(N102na12)(2102n1a12 + 102n2a2)a2開立方N103na13N103na13N103na13(N103na13)(3103n1a12 + 3103n2a1a2 + 103n3a22)a2法開平方102na12102na1210

10、2n1a12102n1a1 + 102n2a2開立方103na123103na12103n1a123103n1a12 + 3103n2a1a2 + 103n3a22中行開平方無開立方3a13103n2a123103n2a1（副）3103n2a1a2借算開平方1102n102n102n2102n2開立方1103n1103n3103n3（副）103n3a22(1)(2)(3)(4)(5)(6)        通過分析上面的籌算開立方方法，可知它是根據(jù)下面這些公式來逐步推求的，也和現(xiàn)代迭代的方法完全一致，可以在計算機上實

11、現(xiàn)。        (a + b)3 = a3 + (3a2 + 3ab + b2)b        (a + b + c)3 = (a + b)3 + 3(a + b)2 + 3(a + b)c + c2c        (a + b + c + d)3 = (a + b + c)3 + 3(a + b + c)2 + 3(a + b + c)d + d2

12、d                中國古代數(shù)學(xué)將二次方程x2 + bx + c = 0 (b , c > 0) 的正根稱為開帶從平方法，九章算術(shù)雖未給出開帶從平方和開帶從立方的程序，但在開平方、開立方術(shù)中從求根的第二位得數(shù)起，就是求形如x2 + bx + c = 0 , x3 + bx2 + cx = d (b ,c , d > 0) 正根的程序，這實際上已蘊含了開帶從平方和立方的程序。三、徽對開方程序的改進(jìn) &#

13、160;      徽借助于出入相補原理，對九章算術(shù)提出的開平方、開立方程序給予了幾何解釋，從而證明了開方程序的合理性，使人們對開方術(shù)有了直觀性的感性認(rèn)識。同時，在闡述其幾何意義時，對開方程序也作了改進(jìn)，以往論者認(rèn)為徽的開方程序與九章算術(shù)一樣，徽祇是解釋了九章算術(shù)的程序，郭書春先生經(jīng)過研究指出二者起碼有兩個重大不同4：        首先，九章算術(shù)中，在議得某位得數(shù)（設(shè)第一位a，第二位b）后，算出法（或定法）（開平方是a與2a + b；開立方是a2與3a2

14、 + 3ab + b2），再以法除實，使得實如法恰恰得到該位得數(shù)。此除即除法，顯然它還保留了開方由除法脫胎出來的痕跡，徽注開方術(shù)，是將除實解釋成以議得數(shù)乘法（開平方a2與 (2a + b)b；開立方是a3與 (3a2 + 3ab + b2)b減實，此除，即減，這無疑是程序上的一大進(jìn)步。        其次，九章算術(shù)的借算在每使用一次后都要撤去，議得次一位得數(shù)時要復(fù)置借算（開立方時還要置中行）于個位，再步之如初，顯得繁瑣，徽則保留借算，將中行與借算先與法對齊，再通過退位求減根方程，顯得簡潔。  &

15、#160;     總之，通過徽的改進(jìn)，程序已簡便得多，已基本接近于現(xiàn)今方法，后來在子算經(jīng)，丘建算經(jīng)與賈憲黃帝九章算經(jīng)細(xì)草中得到了繼承和發(fā)展。四、九章算術(shù)開方術(shù)與現(xiàn)代計算機程序比較        以上開平方、開立方、開帶以平方和立方程序，共同構(gòu)成中國古代數(shù)學(xué)一個獨立的算法程序系統(tǒng)開方算法程序系統(tǒng)，九章算術(shù)中開方算法程序不僅表現(xiàn)了中國籌算所能達(dá)到的高超的算技，而且充份體現(xiàn)了中國數(shù)學(xué)思想方法的構(gòu)造性和算法機械化特色。九章算術(shù)與這種開方算法具有的代數(shù)意義密切相關(guān)。由于在開

16、方中都借用一根算籌分別表示未知量的平方和立方，這樣就賦予用算籌所列出的開方式以x2 = N和x3 = N兩個代數(shù)方程，于是，開平方和開立方的各個演算步驟也就成了解方程求正根的過程。事實上，要保證算法程序機械化的一步步進(jìn)行，并在有限步驟求得方根的每一位得數(shù)，從這種二項二次方程或二項三次方程的代數(shù)意義上，都要經(jīng)過以下三個步驟：        I.首先把方程進(jìn)行倍根變換，估計方根的第一次近似值。        II. 每求得方根的一次近似值之

17、后，就利用二項展開式將原方程進(jìn)行減根變換，求出一個新的方程。        III. 在新方程中，以定法除實即以一次項系數(shù)常數(shù)項，求得方程的下一次近似值。因此這些步驟可循環(huán)重復(fù)，直至根值全部求出或求到一定數(shù)位為止。        以開立方為例，相當(dāng)于求方程f (x) = x3N = 0的正根，估計方根的第一次近似值為x1，依II進(jìn)行減根變換，即令x = x1 + y則y = xx1代入f (x) = 0得y3 + 3x1y2 + 3x1

18、2y = Nx13再依III y = (Nx13)/3x12 =< I>f (x1)/f '(x1)，因此，x = x1f (x1)/f '(x1)。        這就是九章算術(shù)開方術(shù)的演算原理，而這一原理，恰好是 Newton-Raphson解法的根據(jù)56。        現(xiàn)代計算機要用牛頓一類的迭代法求一元二次或三次方程f (x) = 0的根，首先大致估計出根的圍，給一個初值x0，然后可用迭代公式xi+

19、1 = xif (xi)/f '(xi)依次求出第i + 1次根的近似值xi+1，設(shè)e是所求根的精度要求，若滿足|(xi+1xi)/xi+1| < e，則xi+1的值即為所求方程的解，否則再求xi+2 = xi+1f (xi+1)/f '(xi+1)，然后判斷 |(xi+2xi+1)/xi+2| < e是否成立，直至滿足精度為止。由此看來，迭代法雖然也是程序化較強的算法，它是將每一次求得的新值又作為下一次的初值來推求，直到前后兩次求出的值很接近，即接近真正的根，而且其初估值x0以與每次的近似值也不一定是所求根的每一位得數(shù)，這和中國古算開平方和立方求方根的方法、程序不

20、同。中國古算開方程序在有限步驟依次求得方根的每位得數(shù)，通過倍根變換，估得方根的最高位得數(shù)，再通過減根變換，求得新方程和下一次近似值，即為所求方根的次高位得數(shù)，如此繼續(xù)下去，直至結(jié)束。        蒙師大科學(xué)史研究所的沙娜曾用計算機 “FORTRAN 77” 程序語言設(shè)計出開方術(shù)的計算機程序，并對九章開方術(shù)與現(xiàn)代計算機開方中用到的牛頓迭代法進(jìn)行比較7，指出雖然古今開方原理一樣，然而在具體程序進(jìn)行中，因計算工具有不同，其算法亦不盡一樣，因而開方計算機程序也不完全同一般的計算機牛頓開方算法。  &#

21、160;     計算機：        一般牛頓法開方有兩個缺點：1) 在理論上初始值x1 > 0即可，然而計算時此值若不在根附近，則往往不收斂。2) 在計算機中用到一階微分f '(x)，但它可能無法得到或不易列出。這兩點在一般的開方中還并不明顯，但在以后的高次方程的數(shù)值解中則顯得突出。        籌算：1. 對初始值的選取，由于一開始倍根，使得初始值很容易估計在根附

22、近，并由于采用位置值制，使這一步極易做到。由于這個方法被一直保留到高次方程的數(shù)值解中，因而在高次方程數(shù)值解中亦不存在問題。2. 一階微分即減根方程中的方，由于是用二次展開式系數(shù)得到，所以很好計算，在以后的高次方程數(shù)值解中，因用增乘方法得到，亦是很易計算與表達(dá)的。        計算機：        在求根的下一位有效值時，其值不取整，亦無倍根過程，因而迭代次數(shù)是籌算的12倍，當(dāng)然對計算機這并不算甚么。        籌算：        因用手移動籌來計算，計算次數(shù)不僅勞作繁忙且易出錯，對此籌算采取了取整的方法，使運算一次即可得到一位有效值，減少了計算量，使用籌開方成為可能，這些方法均保