Odpowiedź na życie, wszechświat i wszystko
Zespół kierowany przez Andrew Sutherlanda z MIT i Andrew Bookera z Uniwersytetu w Bristolu rozwiązał ostatni element słynnej, 65-letniej zagadki matematycznej, uzyskując odpowiedź na najbardziej nieuchwytną liczbę ze wszystkich: 42.
Liczba 42 jest szczególnie istotna dla fanów powieści science fiction Douglasa Adamsa „Autostopem przez galaktykę”, ponieważ ta liczba jest odpowiedzią udzieloną przez superkomputer na „ostateczne pytanie o życie, wszechświat i wszystko”.
Booker chciał również poznać odpowiedź na 42. To znaczy, czy istnieją trzy sześciany, których suma wynosi 42?
Ta zagadka sumy trzech sześcianów, po raz pierwszy ustawiona w 1954 roku na Uniwersytecie w Cambridge i znana jako Równanie Diophantine x3+y3+z3=k, rzuciła wyzwanie matematykom, aby znaleźli rozwiązania dla liczb 1-100. Przy mniejszych liczbach ten typ równania jest łatwiejszy do rozwiązania: na przykład 29 można zapisać jako 33 + 13 + 13, podczas gdy 32 jest nierozwiązywalne. Wszystkie zostały ostatecznie rozwiązane, lub okazały się nierozwiązywalne, przy użyciu różnych technik i superkomputerów, z wyjątkiem dwóch liczb: 33 i 42.
Booker wymyślił pomysłowy algorytm i spędził tygodnie na superkomputerze swojego uniwersytetu, gdy ostatnio wymyślił rozwiązanie dla 33. Ale kiedy zwrócił się do rozwiązania dla 42, Booker stwierdził, że obliczenia potrzebne były o rząd wielkości wyższe i może być poza jego możliwości superkomputera. Booker mówi, że otrzymał wiele ofert pomocy w znalezieniu odpowiedzi, ale zamiast tego zwrócił się do swojego przyjaciela Andrew „Drew” Sutherlanda, głównego pracownika naukowego w Departamencie Matematyki. „Jest światowym ekspertem w tego typu sprawach”, mówi Booker.
Sutherland, którego specjalnością są masowo równoległe obliczenia, pobił rekord w 2017 roku dla największego klastra Compute Engine, z 580 000 rdzeni na Preemptible Virtual Machines, największym znanym klastrze obliczeń o wysokiej wydajności, który działa w chmurze publicznej.
Podobnie jak inni obliczeniowi teoretycy liczb, którzy pracują w geometrii arytmetycznej, był świadomy problemu „sumy trzech sześcianów”. I obaj pracowali razem już wcześniej, pomagając w tworzeniu L-funkcji i Bazy Danych Form Modułowych (LMFDB), internetowego atlasu obiektów matematycznych związanych z tym, co znane jest jako Program Langlandsa. „Byłem zachwycony, gdy Andy poprosił mnie, bym dołączył do niego w tym projekcie” – mówi Sutherland.
Booker i Sutherland przedyskutowali strategię algorytmiczną, jaką należy zastosować w poszukiwaniu rozwiązania 42. Tak jak Booker znalazł rozwiązanie dla 33, wiedzieli, że nie muszą uciekać się do wypróbowywania wszystkich możliwości dla x, y i z.
„Istnieje pojedynczy parametr całkowity, d, który określa stosunkowo niewielki zbiór możliwości dla x, y i z, takich, że wartość bezwzględna z jest poniżej wybranej granicy wyszukiwania B,” mówi Sutherland. „Następnie wylicza się wartości d i sprawdza każdą z możliwych wartości x, y, z związanych z d. W próbie złamania 33, granica wyszukiwania B wynosiła 1016, ale to B okazało się zbyt małe, aby złamać 42; zamiast tego użyliśmy B = 1017 (1017 to 100 milionów miliardów).
W przeciwnym razie, główną różnicą między poszukiwaniem 33 a poszukiwaniem 42 byłaby wielkość wyszukiwania i używana platforma komputerowa. Dzięki hojnej ofercie brytyjskiej firmy Charity Engine, Booker i Sutherland byli w stanie wykorzystać moc obliczeniową z ponad 400 000 komputerów domowych wolontariuszy, na całym świecie, z których każdy został przypisany do zakresu wartości dla d. Obliczenia na każdym komputerze działają w tle, więc właściciel może nadal używać swojego komputera do innych zadań.
Sutherland jest również fanem Douglasa Adamsa, więc projektowi nie można było się oprzeć.
Metoda użycia Charity Engine jest podobna do części fabuły otaczającej liczbę 42 w powieści „Autostopowicz”: Po tym, jak odpowiedź Deep Thought na liczbę 42 okazuje się niezadowalająca dla naukowców, którzy nie znają pytania, na które ma ona odpowiedzieć, superkomputer postanawia obliczyć Ostateczne Pytanie poprzez zbudowanie superkomputera zasilanego przez Ziemię … innymi słowy, wykorzystując ogólnoświatową platformę obliczeń masowo równoległych.
„Jest to kolejny powód, dla którego bardzo podobało mi się uruchomienie tych obliczeń na Charity Engine – faktycznie użyliśmy komputera o skali planetarnej, aby rozwiązać od dawna otwarte pytanie, na które odpowiedź brzmi 42.”
Wykonali oni szereg obliczeń przy niższej wydajności, aby przetestować zarówno swój kod, jak i sieć Charity Engine. Następnie użyli szeregu optymalizacji i adaptacji, aby kod lepiej nadawał się do masowo rozproszonych obliczeń, w porównaniu do obliczeń uruchomionych na jednym superkomputerze, mówi Sutherland.
Dlaczego superkomputer w Bristolu nie mógł rozwiązać tego problemu?
„Cóż, każdy komputer *może* rozwiązać ten problem, pod warunkiem, że jest się skłonnym czekać wystarczająco długo, ale mając około pół miliona komputerów pracujących równolegle nad tym problemem (każdy z wieloma rdzeniami), byliśmy w stanie zakończyć obliczenia znacznie szybciej, niż moglibyśmy to zrobić używając maszyny z Bristolu (lub którejkolwiek z maszyn tutaj w MIT)”, mówi Sutherland.
Używanie sieci Charity Engine jest również bardziej energooszczędne. „W przeważającej części wykorzystujemy zasoby obliczeniowe, które w przeciwnym razie poszłyby na marne” – mówi Sutherland. „Kiedy siedzisz przy komputerze i czytasz e-mail lub pracujesz nad arkuszem kalkulacyjnym, wykorzystujesz tylko niewielki ułamek dostępnych zasobów procesora, a aplikacja Charity Engine, oparta na Berkeley Open Infrastructure for Network Computing (BOINC), korzysta z tego. W rezultacie, ślad węglowy tych obliczeń – związany z energią elektryczną, którą nasze obliczenia spowodowały, że komputery w sieci zużyły ponad to, co zużyłyby w każdym przypadku – jest niższy niż byłby, gdybyśmy użyli superkomputera.”
Sutherland i Booker prowadzili obliczenia przez kilka miesięcy, ale ostateczne udane uruchomienie zostało zakończone w ciągu zaledwie kilku tygodni. Kiedy nadeszła wiadomość od Charity Engine, dostarczyła ona pierwsze rozwiązanie x3+y3+z3=42:
42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
„Kiedy usłyszałem tę wiadomość, to był zdecydowanie moment, w którym zacisnąłem pięści”, mówi Sutherland. „W przypadku obliczeń na dużą skalę poświęcasz mnóstwo czasu i energii na optymalizację implementacji, dostrajanie parametrów, a następnie testowanie i ponowne testowanie kodu przez tygodnie i miesiące, nigdy tak naprawdę nie wiedząc, czy cały ten wysiłek się opłaci, więc jest to niezwykle satysfakcjonujące, gdy tak się dzieje.”
Booker i Sutherland twierdzą, że do rozwiązania pozostało jeszcze 10 liczb z zakresu 101-1000, a następna liczba to 114.
Ale obaj są bardziej zainteresowani prostszą, ale obliczeniowo trudniejszą zagadką: czy istnieje więcej odpowiedzi na sumę trzech sześcianów dla 3.
„Istnieją cztery bardzo łatwe rozwiązania, które były znane matematykowi Louisowi J. Mordell, który słynny napisał w 1953 roku, „Nie wiem nic o całkowitych rozwiązań x3 + y3 + z3 = 3 poza istnieniem czterech trójek (1, 1, 1), (4, 4, -5), (4, -5, 4), (-5, 4, 4); i to musi być bardzo trudne rzeczywiście dowiedzieć się czegoś o wszelkich innych rozwiązań. Ten cytat spowodował duże zainteresowanie problemem sumy trzech sześcianów, a w szczególności przypadkiem k=3. Chociaż przypuszcza się, że rozwiązań powinno być nieskończenie wiele, to mimo ponad 65 lat poszukiwań znamy tylko łatwe rozwiązania, które były znane już Mordellowi. Byłoby bardzo ekscytujące znaleźć inne rozwiązanie dla k=3.”
.