中国古代数学算法的Python实现

Golden Grape

2017-12-28 15:00

看了这篇《没有定理的中国古代数学，如何站在世界之巅？》。虽然我觉得题目很标题党，不过里面的内容很有趣啊，讲解了中国古代数学里的几个算法。由于我正在学Python，所以自然就拿来练手了。

可以运行的代码在这里

更相减损术

“术曰：以少减多，更相减损，求其等也。”

def 更相减损术(a,b):
    while (a != b):
        if a > b:
            a=a-b
        else :
            b=b-a
    return a

这个很好写啦，读入两个数a和b，求其等也，就是一直要求到两个数相等为止。所以用条件循环while，当a不等于b时就一直重复算。算什么呢，以少减多，就是判断一下谁大. 如果a>b, 就用a-b替换a，否则就用b-a替换b。一直到两个数减到相等为止，就可以随便返回其中一个数作为最大公约数了。

大衍求一术

这个好帅，是求解ax≡1(mod b)。就是说a乘以x除以b所得的余数等于1。详细的解说还是看那篇公众号的文章吧。

def 大衍求一术(a,b):
    m=np.matrix( [ [a,1], [b,0] ] )
    while (m[0,0] != 1 ):
        if m[0,0]>m[1,0]:
            m[0,:]=m[0,:]-m[1,:]
        else:
            m[1,:]=m[1,:]-m[0,:]
        if m[1,0]==1:
            return 1
        else:
            return m[0,1]

因为打算用矩阵，所以要首先导入Numpy包，python很强大的一点就是有各种包，只要import一下就好像有了超能力。大衍求一术要求先生成一个2*2的矩阵

a 1
b 0

这样的，所以先用np.matrix产生一个矩阵m，注意python的序数是从0开始的，所以m[0,0]=a, m[0,1]=1, m[1,0]=b, m[1,1]=0。

然后跟前面的更相减损术差不多，也是减来减去，区别是以行为单位来减，终点是把a的位置变成1，比大小的时候是用左边那列的元素比大小。

所以如果m[0,0]>m[1,0]，那就把上一行减去下一行m[0,:]-m[1,:]，再替换掉上面一行m[0,:]=m[0,:]-m[1,:]。反之亦然。一直重复，直到m[0,0] == 1。

通常是返回m[0,1]的数值就可以了。但有可能a,b互质，所以需要分情况讨论一下。

我的古文水平和编程水平都还不够高，不然把中国古代数学中的种种算法都写出程序也是一件很风雅的事情。