Mam pewien problem. Muszę wykonać 200 miliardów obliczeń z liczbami, które mają 50 miejsc po przecinku i muszą być niezwykle dokładne. Obecnie z zainstalowanym pythonem i mpmath zajęłoby to 35 dni, których nie mam. Zna ktoś jakiś język programowania, który byłby w stanie udźwignąć takie zadanie w stosunkowo krótkim czasie? Same operacje są proste, tylko plus, minus, mnożenie i dzielenie. Dziękuję za pomysły.
Udostępnij
W systemach komputerowych (SK) do wydajnych obliczeń numerycznych używa się Fortrana. Jest on najszybszy w kontekście macierzowych pozycyjnych systemów numerycznych (array-based numerical codes). Niemniej, w konteście HPC (high-performance computing) niektórzy wolą Julię, która wymaga mniej kodu do wyrażenia tego samego, a szybkością nie odstępuje od tego pierwszego.
W przypadku Fortrana trzeba użyć zewnętrznych bibliotek, np. MPC, MPFUN/ARPREC/QD/DQFUN. Julia zaś ma już wbudowany typ danych do tego celu.
Ogólnie rzecz biorąc twój problem jest niejako interdyscyplinarny (wielodziedzinowy) na linii matematyka—informatyka—elektronika. Matematyka bowiem nie jest przekładana wprost w ramy informatyki, a sama informatyka często dopasowuje swe rozwiązania do elektroniki, by cały SK działał efektywnie.
Czepiając się terminologii należy zauważyć, że zwykle przez precyzyjny język programowania (o ile już pada takie potoczne określenie) mamy na myśli taki język, który potrafi precyzyjnie operować w SK (SK to sprzęt+oprogramowanie, hardware+software, tzn. część trudno zmienialna i część elastyczna traktowane razem). Nie ma to zatem wiele wspólnego z operacjami matematycznymi jako takimi.
Twój problem, jednakże, polega na tym, że potrzebujesz arytmetyki arbitralnej precyzji (multiple precision, arbitrary precision). 50 miejsc po przecinku to całkiem sporo. Jakkolwiek różnie implementuje się w systemach operacyjnych i językach programowania (JP) obsługę IEEE 754 (standard binarnych operacji na liczbach zmiennoprzecinkowych — floating-point standard), o tyle w praktyce większość JP ogranicza się do 18 cyfr znaczących (double, decimal64) w schemacie x+y=18, gdzie x oznacza cyfry przed przecinkiem, a y cyfry po przecinku. To jest to, co rozumiemy przez „zmienny przecinek” (floating-point), oparty o koncepcję mantysy (mantissa, significand). W C++ mamy nawet typ 'long double’ (quadruple, decimal128) oferujący 34 cyfry znaczące. Nadal za mało.
Co się zatem robi, gdy chce się mieć operacje arytmetyczne z odgórnie ustaloną precyzją po przecinku (multiple precision)? Trzeba zrezygnować ze wsparcia sprzętu (a konkretnie mikroprocesora — µP, CPU — i jego obsługi standardu IEEE 754 dla natywnego słowa maszynowego) i napisać oprogramowanie, co wnosi tyle, że będzie to zawsze, na mocy definicji, rozwiązanie wolniejsze. Typy float/double w JP są implementowane z myślą o dopasowaniu się do zasady działania µP, dlatego są relatywnie szybkie. Z chwilą, gdy chcemy wykroczyć poza te ograniczone możliwości, musimy zachowywać spójność liczby za pomocą dodatkowego kodu, co przekłada się na większość ilość instrukcji/cykli pracy µP.
Mamy tylko dwa utarte wzorce dla liczb o ustalonej precyzji: BigInteger oraz BigFloat (Java, Julia), ewentualnie Decimal (Python). Czasem nie ma to swej nazwy, bo możliwość ta jest wbudowana w JP (Common Lisp). W różnych JP są one różnie implementowane, a w niektórych ich po prostu nie ma (C, C++, Fortran).
Tak czy inaczej, Fortran lub Julia z użyciem wielowątkowości (multithreading) — albo jeszcze lepiej: z użyciem równoległości (parallelism) — powinien dać dobre rezultaty (zakładając, że w twym przedsięwzięciu operacje są od siebie niezależne). Czy to jednakowoż rozwiąże twój problem długiego czasu przetwarzania? Otóż, niekoniecznie. Muszę cię bowiem tutaj, chyba, rozczarować. Jakkolwiek Python jest zgoła wolniejszym językiem od takiego C++, o tyle 35 dni dla 200 miliardów obliczeń wobec liczb z ustaloną precyzją, to jest całkiem dobry wynik dla komputera cyfrowego binarnego, o ile nie dysponujesz mocą obliczeniową superkomputera. Bez względu na wszystko winieneś się przygotować na to, że zajmie to trochę czasu. Dlatego też jakimś rozwiązaniem tego kłopotu jest przeniesienie obliczeń do chmury (cloud computing), np. w ramach AWS. Tyle, że to rozwiązanie na dłuższą metę płatne. Do tego darmowa funkcjonalność zwykle podejmuje politykę zabijania procesów, które zajmują zbyt wiele czasu lub zasobów serwera.
W praktyce alternatywy do tego, co już masz, mogą okazać się kłopotliwe. C++ wymaga obycia, by zarówno pisać w nim kod wydajny, jak i używać zewnętrznych bibliotek. Skrypty w Wolfram Mathematica, Octave czy Matlabie raczej za wiele nie pomogą, bo opierają się o obliczenia symboliczne (symbolic computing). Co prawda, API Wolframa Alpha mogłoby być jakimś rozwiązaniem, gdyby nie to, że darmowa wersja ogranicza się do 2000 zapytań. Jedynie Julia może być dobrym wyborem, zwłaszcza w przypadku zaprzęgnięcia do obliczeń mocy GPU (procesora graficznego).
To, co dodatkowo warto by było zrobić, to optymalizacja złożoności obliczeniowej (time complexity) algorytmu, np. za pomocą zredukowania zbędnych operacji poprzez zamianę ich do formy kanonicznej (canonicalization, standardization, normalization). Poza tym, użyj BigInteger zamiast BigFloat tam, gdzie możesz, bo ten pierwszy jest po prostu nieco szybszy. Nie wiem, z czym dokładnie masz do czynienia, niemniej przypominam iż w zagadnieniach łączących matematykę z informatyką nieustępliwym kanonem pozostaje pozycja Donalda E. Knutha „The Art of Computer Programming”, tutaj: Volume 2, 4.3. Multiple-Precision Arithmetic. Twej uwadze polecam w szczególności sekcję 4.3.3. How Fast Can We Multiply?, wskazującą na to, że najlepsze algorytmy mają złożonosć obliczeniową logarytmiczną.