Ved å lage historie med 42 sifre har forskere fra Universitetet i Paderborn og KU Leuven låst opp et flere tiår gammelt matematikkmysterium med det såkalte niende Dedekind-tallet.

Eksperter over hele verden har forsket på verdien siden 1991. Paderborn-forskere kom frem til den nøyaktige rekkefølgen av tall ved å bruke Noctua-superdatamaskinen som ligger der. Resultatene vil bli presentert i september kl Internasjonalt verksted om boolske funksjoner og deres applikasjoner (BFA) i Norge.

Det som startet som et masteroppgaveprosjekt av Lennart Van Hirtum, den gang informatikkstudent ved KU Leuven og nå forsker ved Universitetet i Paderborn, har blitt en stor suksess. Forskere slutter seg til en berømt gruppe med sitt arbeid. De første sifrene i serien ble funnet av matematikeren Richard Dedekind selv da han definerte problemet i 1897, og senere av datastorheter som Randolph Church og Morgan Ward. «I 32 år var å beregne D(9) en åpen utfordring, og man lurte på om det noen gang ville være mulig å beregne dette tallet,» sier Van Hirtum.

Det forrige nummeret i Dedekind-sekvensen, det åttende Dedekind-nummeret, ble funnet i 1991 ved å bruke en Cray 2, den kraftigste superdatamaskinen på den tiden. «Så det virket tenkelig for oss at det nå ville være mulig å beregne det 9. tallet på en stor superdatamaskin,» sier Van Hirtum, og beskriver motivasjonen for det ambisiøse prosjektet, som han i utgangspunktet gjennomførte sammen med direktørene for masteroppgaven sin ved KU Louvain.

Sandkorn, sjakk og superdatamaskiner

Hovedtemaet for Dedekind-tall er såkalte monotone boolske funksjoner. Van Hirtum forklarer, «I utgangspunktet kan du tenke på en monoton boolsk funksjon i to, tre og uendelige dimensjoner som et spill med en n-dimensjonal kube. Du balanserer kuben i ett hjørne, og farger deretter hvert av de resterende hjørnene enten hvite. eller rødt. Det er bare én regel: du bør aldri plassere et hvitt hjørne over et rødt hjørne. Dette skaper et slags vertikalt rød-hvitt skjæringspunkt.

«Målet med spillet er å telle hvor mange forskjellige kopper det er. Antallet deres er det som er definert som Dedekind-tallet. Selv om det ikke ser ut som det, blir tallene fort gigantiske i prosessen: Det 8. tallet Dedekind har allerede 23 sifre.»

Relativt store – men uforlignelig lettere å beregne – tall er kjent fra en legende om oppfinnelsen av sjakkspillet. «Ifølge denne legenden ba oppfinneren av sjakkspillet kun kongen om noen få riskorn på hver rute på sjakkbrettet som belønning: ett korn på den første ruten, to korn på den andre, fire på den tredje , og dobbelt så mange på hver av de følgende rutene Kongen innså snart at denne forespørselen var umulig å tilfredsstille, fordi det ikke er så mye ris i hele verden.

«Antall riskorn på hele diagrammet vil være 20 sifre – en ufattelig mengde, men fortsatt mindre enn D(8). Når du innser disse størrelsesordene, er det åpenbart at både en effektiv metode for beregning og en veldig rask datamaskinmetode ville være nødvendig for å finne D(9),» sa Van Hirtum.

Milepæl: år blir måneder

For å beregne D(9) brukte forskerne en teknikk utviklet av avhandlingsleder Patrick De Causmaecker kjent som P-koeffisientformelen. Den gir en måte å beregne Dedekind-tall ikke ved å telle, men med en veldig stor sum. Dette gjør at D(8) kan dekodes på bare åtte minutter på en vanlig bærbar datamaskin. Men, «Det som tar åtte minutter for D(8) blir hundretusenvis av år for D(9). Selv om du brukte en stor superdatamaskin eksklusivt for denne oppgaven, ville det fortsatt ta mange år å fullføre beregningen» , Van Hirtum påpeker.

Hovedproblemet er at antallet termer i denne formelen øker utrolig raskt. «I vårt tilfelle, ved å utnytte symmetriene i formelen, klarte vi å redusere antall termer til «bare» 5,5×10¹⁸– enormt mye. Til sammenligning er antallet sandkorn på jorden omtrent 7,5×10¹⁸som ikke er å neglisjere, men for en moderne superdatamaskin, 5,5×10¹⁸ driften er ganske håndterlig, sa IT-spesialisten.

Problemet: Å beregne disse termene på vanlige CPUer er treg og bruk av GPUer, som for tiden den raskeste maskinvareakselerasjonsteknologien for mange AI-applikasjoner, er ikke effektiv for denne algoritmen.

Løsningen: applikasjonsspesifikk maskinvare ved hjelp av høyt spesialiserte, parallelle aritmetiske enheter kalt FPGAer (brukerprogrammerbare portarrayer). Van Hirtum utviklet en første prototype for maskinvareakseleratoren og begynte å søke etter en superdatamaskin med de nødvendige FPGA-kortene. I prosessen lærte han om Noctua 2-datamaskinen ved «Paderborn Center for Parallel Computing (PC2)» ved Universitetet i Paderborn, som har et av de kraftigste FPGA-systemene i verden.

Professor Christian Plessl, leder for PC2, forklarer: «Da Lennart Van Hirtum og Patrick De Causmaeker kontaktet oss, ble det umiddelbart klart for oss at vi ønsket å støtte dette Moonshot-prosjektet. Å løse vanskelige kombinatoriske problemer med FPGA-er er et lovende område. applikasjon og Noctua 2 er en av få superdatamaskiner i verden som eksperimentet er gjennomførbart med. Ekstreme krav til pålitelighet og stabilitet er også en utfordring og en test for vår infrastruktur. Teamet med ekspert FPGA-konsulenter jobbet tett med Lennart for å tilpasse og optimalisere applikasjonen for miljøet vårt.»

Etter flere år med utvikling, kjørte programmet på superdatamaskinen i omtrent fem måneder. Og så var tiden kommet: 8. mars fant forskerne det niende Dedekind-nummeret: 286386577668298411128469151667598498812366.

Nå, tre år inn i Dedekind-prosjektet, jobber Van Hirtum som NHR Graduate School Fellow ved Paderborn Center for Parallel Computing for å utvikle neste generasjon maskinvareverktøy i sin doktorgrad. Forskerskolen National High Performance Computing (NHR) er den felles forskerskolen til NHR-sentrene. Han vil rapportere om sin ekstraordinære suksess med Patrick De Causmaecker 27. juni klokken 14.00 i O2-konferanserommet ved Universitetet i Paderborn.