|
德國(guó)帕德博恩大學(xué)和荷語(yǔ)區(qū)魯汶大學(xué)（KU Leuven）的科學(xué)家用一個(gè)42位的數(shù)字創(chuàng)造了歷史，用所謂的第九個(gè)戴德金數(shù)解開(kāi)了幾十年的數(shù)學(xué)之謎。 作者：帕德博恩大學(xué)（Paderborn大學(xué)） 2023-6-26 譯者：zzllrr小樂(lè)（數(shù)學(xué)科普微信公眾號(hào)）2023-6-28 自1991年以來(lái)，世界各地的專家一直在尋找這個(gè)數(shù)值。帕德博恩的科學(xué)家們?cè)谖挥谀抢锏腘octua超級(jí)計(jì)算機(jī)的幫助下得出了確切的數(shù)列。研究結(jié)果將于9月在挪威舉行的布爾函數(shù)及其應(yīng)用國(guó)際研討會(huì)（BFA，Boolean Functions and their Applications）上公布。
始于Lennart Van Hirtum（上圖）的碩士論文項(xiàng)目（當(dāng)時(shí)他是荷語(yǔ)區(qū)魯汶大學(xué)的計(jì)算機(jī)科學(xué)學(xué)生，現(xiàn)在是帕德博恩大學(xué)的研究助理），已經(jīng)取得了巨大的成功。科學(xué)家們加入了一個(gè)杰出的團(tuán)體。該數(shù)列的早期數(shù)字是由數(shù)學(xué)家理查德·戴德金（Richard Dedekind）在1897年定義問(wèn)題時(shí)自己發(fā)現(xiàn)的，后來(lái)由蘭道夫·丘奇（Randolph Church）和摩根·沃德（Morgan Ward）等早期計(jì)算機(jī)科學(xué)大師發(fā)現(xiàn)?！?2年來(lái)，D(9)的計(jì)算是一個(gè)公開(kāi)的挑戰(zhàn)，是否有可能計(jì)算出這個(gè)數(shù)字是值得懷疑的，”Van Hirtum說(shuō)。 戴德金數(shù)列中的前一個(gè)數(shù)字，即第8個(gè)戴德金數(shù)，是在1991年使用當(dāng)時(shí)最強(qiáng)大的超級(jí)計(jì)算機(jī)Cray 2發(fā)現(xiàn)的?！耙虼?，我們似乎可以想象，現(xiàn)在應(yīng)該可以在大型超級(jí)計(jì)算機(jī)上計(jì)算第 9 個(gè)數(shù)字，”Van Hirtum 說(shuō)，描述了這個(gè)雄心勃勃的項(xiàng)目的動(dòng)機(jī)，他最初與他在荷語(yǔ)區(qū)魯汶大學(xué)的碩士論文導(dǎo)師共同實(shí)施。 沙粒、國(guó)際象棋和超級(jí)計(jì)算機(jī) 戴德金數(shù)的主要主題是所謂的單調(diào)布爾函數(shù)（monotone Boolean functions）。Van Hirtum解釋說(shuō)：“基本上，你可以將二維、三維和無(wú)限維的單調(diào)布爾函數(shù)視為具有n維立方體的游戲。在一個(gè)角上平衡立方體，然后將剩余的每個(gè)角著色為白色或紅色。只有一條規(guī)則：切勿在紅色角上方放置白角。這創(chuàng)造了一種垂直的紅白相交。
該圖顯示了0、1、2和3維的所有可能截面?？梢灾谱鞯倪@些彩色2維、3維、n維截面的數(shù)量被定義為戴德金數(shù)（Dedekind數(shù)）。 “游戲的目的是計(jì)算有多少不同的切割。它們的數(shù)量就是戴德金數(shù)。即使看起來(lái)不像，但這些數(shù)字在這個(gè)過(guò)程中會(huì)很快變得巨大：第 8 個(gè)戴德金數(shù)字已經(jīng)有 23 位數(shù)字（56130437228687557907788）。 相對(duì)較大的數(shù)字 - 但無(wú)比容易計(jì)算 - 數(shù)字是從關(guān)于國(guó)際象棋游戲發(fā)明的傳說(shuō)中知道的?！案鶕?jù)這個(gè)傳說(shuō)，國(guó)際象棋游戲的發(fā)明者只要求國(guó)王在棋盤(pán)的每個(gè)方格上提供幾粒米作為獎(jiǎng)勵(lì)：第一個(gè)方格一粒，第二個(gè)方格兩粒，第三個(gè)方格四粒，接下來(lái)的每個(gè)方格上兩倍。國(guó)王很快意識(shí)到這個(gè)要求是不可能實(shí)現(xiàn)的，因?yàn)槿澜缍疾淮嬖谶@么多大米。 “整個(gè)棋盤(pán)上的米粒數(shù)將有20位數(shù)字 - 這是一個(gè)難以想象的數(shù)量，但仍然少于D(8)。當(dāng)你意識(shí)到這些數(shù)量級(jí)時(shí)，很明顯需要一種有效的計(jì)算方法和一臺(tái)非?？斓挠?jì)算機(jī)來(lái)找到D(9)，”Van Hirtum說(shuō)。 里程碑：年變成月 為了計(jì)算D(9)，科學(xué)家們使用了碩士論文導(dǎo)師Patrick De Causmaecker開(kāi)發(fā)的一種技術(shù)，稱為P系數(shù)公式（P-coefficient formula）。它提供了一種計(jì)算戴德金數(shù)的方法，不是通過(guò)計(jì)數(shù)，而是通過(guò)非常大的求和。這使得 D(8) 在普通筆記本電腦上只需八分鐘即可解碼。但是，“D(8)需要八分鐘的東西變成了D(9)的數(shù)十萬(wàn)年。即使你專門(mén)使用大型超級(jí)計(jì)算機(jī)來(lái)完成這項(xiàng)任務(wù)，完成計(jì)算仍然需要很多年，”Van Hirtum指出。 主要問(wèn)題是這個(gè)公式中的項(xiàng)數(shù)增長(zhǎng)得非?？??！霸谖覀兊陌咐校ㄟ^(guò)利用公式中的對(duì)稱性，我們能夠?qū)㈨?xiàng)的數(shù)量減少到'僅僅’5.5x101?——數(shù)量巨大。相比之下，地球上的沙粒數(shù)量約為7.5x101?，這沒(méi)什么好輕視的，因?yàn)閷?duì)于現(xiàn)代超級(jí)計(jì)算機(jī)來(lái)說(shuō)，5.5x101?操作非常易于管理，”這位計(jì)算機(jī)科學(xué)家說(shuō)。 問(wèn)題：在普通處理器上計(jì)算這些項(xiàng)的速度很慢，而且使用 GPU 作為目前許多 AI 應(yīng)用程序最快的硬件加速器技術(shù)對(duì)于該算法來(lái)說(shuō)效率不高。 解決方案：使用高度專業(yè)化和并行的算術(shù)單元（即所謂的FPGA - Field Programmable Gate Array 現(xiàn)場(chǎng)可編程門(mén)陣列）的特定應(yīng)用硬件。Van Hirtum為硬件加速器開(kāi)發(fā)了初始原型，并開(kāi)始尋找具有必要FPGA卡的超級(jí)計(jì)算機(jī)。在這個(gè)過(guò)程中，他注意到了帕德博恩大學(xué)“帕德博恩并行計(jì)算中心（PC2）”的Noctua 2計(jì)算機(jī)，該計(jì)算機(jī)擁有世界上最強(qiáng)大的FPGA系統(tǒng)之一。
PC2負(fù)責(zé)人Christian Plessl博士教授解釋說(shuō)：“當(dāng)Lennart Van Hirtum和Patrick De Causmaeker與我們聯(lián)系時(shí)，我們立即意識(shí)到我們希望支持這個(gè)大膽的創(chuàng)新計(jì)劃項(xiàng)目。用FPGA解決困難的組合問(wèn)題是一個(gè)很有前途的應(yīng)用領(lǐng)域，Noctua 2是全球?yàn)閿?shù)不多的實(shí)驗(yàn)可行的超級(jí)計(jì)算機(jī)之一。極高的可靠性和穩(wěn)定性要求也對(duì)我們的基礎(chǔ)設(shè)施提出了挑戰(zhàn)和考驗(yàn)。FPGA專家咨詢團(tuán)隊(duì)與Lennart密切合作，根據(jù)我們的環(huán)境調(diào)整和優(yōu)化應(yīng)用。 經(jīng)過(guò)幾年的開(kāi)發(fā)，該程序在超級(jí)計(jì)算機(jī)上運(yùn)行了大約五個(gè)月。然后時(shí)間到了：8月9日，科學(xué)家們發(fā)現(xiàn)了第9個(gè)戴德金數(shù)：286386577668298411128469151667598498812366。 至此，戴德金數(shù)D(n)前幾個(gè)（ 0 ≤ n ≤ 9）確切值已知為： D(0)=2 D(1)=3 D(2)=6 D(3)=20 D(4)=168 D(5)=7581 D(6)=7828354 D(7)=2414682040998 D(8)=56130437228687557907788 D(9)=286386577668298411128469151667598498812366 （OEIS 中的序列 A000372 https:///A000372） 如今，在戴德金項(xiàng)目開(kāi)始三年后，Van Hirtum正在帕德博恩并行計(jì)算中心擔(dān)任NHR研究生院的研究員，在他的博士學(xué)位中開(kāi)發(fā)下一代硬件工具。NHR（national es hochleistungs rechnen 德國(guó)國(guó)家高性能計(jì)算）研究生院是NHR中心的聯(lián)合研究生院。他將于6月27日下午2點(diǎn)在帕德博恩大學(xué)O2演講廳與Patrick De Causmaecker一起報(bào)告他的非凡成功。 參考資料：
讓數(shù)學(xué) 更加 易學(xué)易練， 易教易研， 易賞易玩， 易見(jiàn)易得， 易傳易及。 |
|
|
來(lái)自： zzllrr小樂(lè) > 《待分類》
