教你如何用 Python 的平行運算,驗證數學界的百年難題「哥德巴赫猜想」

哥德巴赫寫給歐拉的手稿,探討哥德巴赫猜想。

【我們為什麼挑選這本書】哥德巴赫猜想(Goldbach’s conjecture)是數學界的經典難題。1742 年,德國數學家哥德巴赫提出兩個猜想「任何大於 5 的奇數都是三個質數之和」、「任何一個大於 2 的偶數都是兩個質數之和」,但 200 年過去了,仍沒有數學家可以有效證明。

你的第一本 Python 入門課》的作者毛雪濤和丁毓峰,都在武漢理工大學進行電腦的研究和教學,透過本書讓讀者了解 Python 的基礎技術。下文,我們將透過 Python 程式碼驗證困擾數學界的百年難題:哥德巴赫猜想。(責任編輯:郭家宏)

在數學課上,老師給大家講了一個故事:克利斯汀‧ 哥德巴赫(Christian Goldbach)是德國的大數學家,他發現任取一個奇數,比如 79,可以把它寫成三個質數之和,例如 79 = 53 + 19 + 7;又比如 463 = 257 + 199 + 7。例子太多了,於是他猜測:「任何大於 5 的奇數都是三個質數之和。」但他自己沒法證明。於是,1742 年 6 月 7 日,哥德巴赫寫信給他的好友大數學家歐拉(Leonhard Euler),提出了他的猜想。

歐拉琢磨了很久,於 1742 年 6 月 30 日給哥德巴赫回信,說這個命題看來是正確的,但是他也給不出嚴格的證明。同時歐拉又提出一個命題:「任何一個大於 2 的偶數都是兩個質數之和。」但是這個命題他也沒能給予證明。這兩個命題被視為著名的「哥德巴赫猜想」的兩個版本:奇數版和偶數版。

用 Python 驗證哥德巴赫猜想是否正確

聽了老師講的故事,小小(書中人物)對哥德巴赫猜想產生了興趣。他想知道歐拉的命題到底是不是正確的。雖然歐拉也沒能證明,但是現在電腦運算速度這麼快,能不能用電腦來試試看呢?首先,將歐拉的偶數版哥德巴赫猜想用 Python 程式表示出來。打開 Python IDLE,新建一個 Python 檔,保存為 C:\Workspace\Chapter52\Goldbach.py,輸入以下程式碼:

goldbach() 函式接受一個參數 T,該參數為一個記錄整數區間的列表,由兩個元素組成:T[0] 為區間的起點,T[1] 為區間的終點。由於哥德巴赫猜想指出是大於 2 的偶數,即最小為 4,所以當起點為 4 以下的整數時,把區間起點更正為 4。

另外,如果區間起點為奇數,則將其更正為其後的偶數。接著遍歷區間內的所有偶數,判斷是否符合哥德巴赫猜想。

首先初始化一個布林變數 isGoldbach=False,對於任意偶數 i,如果 i 等於兩個數相加,那麼必定有一個數小於 i/2。只需檢查每一個小於 i/2 的數,找到一個值數 j 和另一個數 k=i-j,如果 j 是質數,k 也是質數,那麼 i=j+k,其中 j 和 k 都是質數,這就滿足哥德巴赫猜想,這時將 isGoldbach 設為 True。

如果發現有一個偶數不滿足哥德巴赫猜想,則輸出「哥德巴赫猜想失敗!」在程式碼中,通過呼叫 isPrime() 函式來判斷一個數是否是素數。需要在 goldbach() 函式之前定義 isPrime() 函式,程式碼如下:

對於大於 1 的數,如果除以 2 到它平方根之間的數,都除不盡,它就是個質數。運行程式,輸入測試資料,結果如圖 52.1 所示。

範例輸出了 5 個樣例,並驗證了 10 ∼ 100 之間所有偶數都滿足哥德巴赫猜想。但是更大的數是否也滿足哥德巴赫猜想呢?

透過 CPU 平行計算,加快哥德巴赫猜想的驗證速度

為了驗證更大的數也滿足哥德巴赫猜想,新建一個 Python 檔,保存為 C:\Workspace\ Chapter52\testGoldbach.py,程式碼如下:

該段程式利用多個 CPU 內核來並存執行 goldbach 函式。需要引入 multiprocessing 模組,該模組用於處理多程式問題。首先,把網際空間(Cyberspace)按 CPU 內核數進行畫分,例如使用 8 核 CPU,則可以將網際空間分為 8 段,然後分別交給 8 個內核並行處理。subRanges() 函式用於將網際空間進行畫分,畫分結果以列表存儲。結果列表的每個元素為一個表示區間的子列表。例如,[10,100] 表示一個從 10 到 100 的整數區域。

然後,使用單程式驗證哥德巴赫猜想。這裡驗證 106 以內的所有偶數。為了對比性能,使用 time.clock() 函式記錄執行時長。接下來使用多程式進行驗證。先使用 cpu_clock() 函式返回系統 CPU 的內核數,然後使用 Pool() 函式建立程式池,池中程式數等於 CPU 內核數。再來使用 Pool 類的 map() 函式並存執行 goldbach 函式。完成後關閉程式池。同樣,記錄執行時間。

由於在子程式中運行的程式無法直接使用 print() 函式輸出資訊,所以在 goldbach() 函式中使用一個變數將需要輸出的結果返回到呼叫程式中。然後通過 map() 函式的返回值將結果列印出來。為此,需要修改 goldbach() 函式,修改後程式碼如下:

運行程式,結果如圖 52.2 所示。

從結果可以看出,對於 106 的數值空間,在 8 核 CPU 上使用單程式執行需要 28s,而使用多程式並存執行僅需要 8s,大大縮短了執行時間。小小終於體會到多核處理器平行計算的厲害之處了!

(本文書摘內容出自《你的第一本 Python 入門課》,由 商業周刊 授權轉載,並同意 TechOrange 編寫導讀與修訂標題。首圖來源: 維基百科 。)

更多實用的 Python 技術

【工程師實用外掛】開啟 Cython,讓你的 Python 運算速度提升 36 倍!
工程師好用資源來了!超完整 Python 查詢表,程式碼複製貼上不用自己寫
【工程師精選乾貨】100 行 Python,神經網路輕鬆搞定


我們正在找夥伴!

2019 年我們的團隊正在大舉擴張,需要你的加入跟我們一起找出台灣創新原動力! 我們正在徵 《採訪社群編輯》、《助理編輯》,詳細職缺與應徵辦法 請點我

點關鍵字看更多相關文章: