Jakie są najlepsze (przenośne) wieloplatformowe biblioteki matematyczne o dowolnej precyzji? [Zamknięte]

81

Szukam dobrej biblioteki matematycznej o dowolnej precyzji w C lub C ++. Czy mógłbyś dać mi jakieś rady lub sugestie?

Podstawowe wymagania:

  1. To musi obsługiwać dowolnie duże liczby całkowite, moim głównym zainteresowaniem jest na liczby całkowite. Jeśli nie wiesz, co oznacza słowo arbitralnie duże, wyobraź sobie coś w rodzaju 100000! (silnia 100000).

  2. Nie trzeba określać dokładności podczas inicjowania biblioteki lub tworzenia obiektów. Precyzja powinny tylko być ograniczany przez dostępne zasoby systemu.

  3. To powinna wykorzystać pełną moc platformy i powinien obsługiwać „małych” numery natywnie. Oznacza to, że na platformie 64-bitowej obliczenia (2 ^ 33 + 2 ^ 32) powinny wykorzystywać dostępne 64-bitowe instrukcje procesora. Biblioteka nie powinna obliczać tego w taki sam sposób, jak robi to z (2 ^ 66 + 2 ^ 65) na tej samej platformie.

  4. To musi skutecznie obsługiwać dodawania ( +), odejmowanie ( -), mnożenia ( *), podział całkowita ( /) reszta ( %) zasilania ( **) przyrost ( ++) zmniejszania ( --), GCD czynnikowe, i inne zwykłe całkowitą arytmetycznych obliczeń. Możliwość obsługi funkcji, takich jak pierwiastek kwadratowy i logarytm, które nie dają wyników w postaci liczb całkowitych, jest plusem. Zdolność do obsługi obliczeń symbolicznych jest jeszcze lepsza.

Oto, co do tej pory znalazłem:

  1. Java „s BigInteger i BigDecimal klasa: I zostały z wykorzystaniem ich do tej pory. Przeczytałem kod źródłowy, ale nie rozumiem matematyki pod spodem. Może opierać się na teoriach i algorytmach, których nigdy się nie poznałem.

  2. Wbudowany typ liczby całkowitej lub w podstawowych bibliotekach bc , Python , Ruby , Haskell , Lisp , Erlang , OCaml , PHP , kilka innych języków: użyłem niektórych z nich, ale nie mam pojęcia, której biblioteki używają, lub jakiego rodzaju implementacji używają.

Co już wiedziałem:

  1. Używanie chardo cyfr dziesiętnych i char*ciągów dziesiętnych oraz wykonywanie obliczeń na cyfrach przy użyciu for-loop.

  2. Używanie int(lub long int, lub long long) jako podstawowej „jednostki” i tablicy tego typu jako dowolnej długiej liczby całkowitej i wykonuj obliczenia na elementach za pomocą for-loop.

  3. Używanie typu całkowitego do przechowywania cyfry dziesiętnej (lub kilku cyfr) jako BCD (dziesiętne kodowane binarnie) .

  4. Algorytm mnożenia Bootha .

Czego nie wiem:

  1. Wydruk powyższej tablicy binarnej w postaci dziesiętnej bez stosowania naiwnych metod. Przykład naiwnej metody: (1) dodaj bity od najniższego do najwyższego: 1, 2, 4, 8, 16, 32,… (2) użyj char*-string wspomnianego powyżej do przechowywania pośrednich wyników dziesiętnych).

Co doceniam:

  1. Dobre porównania na temat GMP , MPFR , decNumber (lub innych bibliotek, które są według Ciebie dobre).

  2. Dobre sugestie dotyczące książek i artykułów, które powinienem przeczytać. Na przykład, ilustracja z postaciami, w jaki sposób a nie naiwne binary-to-przecinku działania algorytmu konwersji będzie dobrze. Artykuł „ Zamiana liczb dwójkowych na dziesiętne z ograniczoną precyzją ” autorstwa Douglasa W. Jonesa jest przykładem dobrego artykułu.

  3. Wszelka pomoc w ogóle.

Proszę nie odpowiadać na to pytanie, jeśli uważasz, że użycie double(lub long doublelub long long double) może rozwiązać ten problem łatwo. Jeśli tak myślisz, nie rozumiesz problemu.

c++ c biginteger bigdecimal gmp Siu Ching Pong -Asuka Kenji-
źródło
3
Z tego co widzę, GMP wydaje się być dobrą biblioteką. Zastanawiam się, dlaczego twórcy Python / Haskell / Erlang / etc potrzebują ponownego wynalezienia koła. Jeśli GMP jest tak dobry, dlaczego nie polegać na nim? Licencja GPL / LGPL może być jednym z problemów, ale mimo to (a także kwestia trybu zaokrąglania), czy są jakieś inne wady GMP? Czy wbudowana liczba całkowita języka Python / Haskell / Erlang / dowolnej biblioteki kryptograficznej jest szybsza niż GMP? Jeśli tak, chciałbym go wyodrębnić i użyć, jeśli pozwala na to licencja.
Siu Ching Pong -Asuka Kenji-
Znalazłem fajny artykuł Douglasa W. Jonesa pod adresem cs.uiowa.edu/~jones/bcd/decimal.html . W artykule opisano metodę konwersji 16-bitowej liczby całkowitej na reprezentację dziesiętną przy użyciu tylko 8-bitowej arytmetyki liczb całkowitych. Pomysł polega na rozbiciu 16-bitowej liczby na 4 półbajty, z których każdy reprezentuje „cyfrę” o podstawie 16. Zatem cyfra-0 (n0) reprezentuje x1, n1 => x16, n2 => x256, n3 => x4096. Wtedy jest oczywiste, że cyfra-0 liczby dziesiętnej (d0) jest cyfrą-0 wyniku n0 * 1 + n1 * 6 + n2 * 6 + n3 * 6. Prawidłowo obsługując przeniesienie, d1 do d4 można być również obliczone.
Siu Ching Pong -Asuka Kenji-
Jednak, o ile mogłem sobie wyobrazić, powyższego pomysłu Douglasa nie można rozszerzyć tak, aby obsługiwał dowolnie długie binarne liczby całkowite. Dzieje się tak, ponieważ liczby 1 (16 ^ 0), 16 (16 ^ 1), 256 (16 ^ 2) i 4096 (16 ^ 3) są wstępnie obliczone. Problem polega więc na tym, jak przedstawić 16 ^ n dziesiętnie dla dowolnie dużego n.
Siu Ching Pong -Asuka Kenji-

Odpowiedzi:

24

GMP to popularny wybór. Squeak Smalltalk ma bardzo ładną bibliotekę, ale jest napisana w Smalltalk.

Poprosiłeś o odpowiednie książki lub artykuły. Trudną częścią bignum jest długi podział. Polecam artykuł Pera Brincha Hansena Multiple-Length Division Revisited: A Tour of the Minefield .

Norman Ramsey
źródło
Dziękuję za link do artykułu! Tak, zgadzam się, że podział jest najtrudniejszą częścią. Wiedziałem, jak zrobić ręczne dzielenie przy użyciu "metody papier-ołówek" dawno temu :-), a zatem ta sama metoda może być zastosowana do ciągu dziesiętnego char *(każdy charreprezentuje cyfrę dziesiętną) lub int *ciągu BCD ( każda intreprezentująca 4/8/16 cyfr BCD). Zastanawiam się jednak, czy biblioteki na poziomie produkcyjnym w świecie rzeczywistym naśladują „metodę papieru i ołówka”, ponieważ jest zbyt wolna.
Siu Ching Pong -Asuka Kenji-
Aby zrozumieć, dlaczego, wyobraźmy sobie, jak to działa na 100,000,000,000,000,000 / 333,333,333,333: Pierwszym krokiem jest porównanie 100,000,000,000z 333,333,333,333. Ponieważ pierwsza jest mniejsza niż druga, obliczenia po prostu przechodzą do następnej cyfry. Drugim krokiem jest znalezienie ilorazu 1,000,000,000,000 / 333,333,333,333, co obejmuje mnożenie metodą prób i błędów 333,333,333,333 * 1(i * 2, * 3i * 4) lub wykonywanie kolejnych odejmowań w pętli. Czy widzisz, jakie to powolne? Uważam, że istnieją wydajniejsze algorytmy.
Siu Ching Pong -Asuka Kenji-
3
@Sui: Brinch Hanson pokazuje, jak można zredukować metodę prób i błędów do co najwyżej dwóch prób. To naprawdę imponujące.
Norman Ramsey
Okej, dokładniej przyjrzę się gazecie. Dziękuję Ci!
Siu Ching Pong -Asuka Kenji-
1
Nie jestem pewien, gdzie znalazłeś swoje rozwiązanie ani w jakim formacie zapisałeś cyfry, ale format COBOL COMP-3 nybble jest o wiele przyjemniejszy w obsłudze, ponieważ jest bardziej kompaktowy, każdy 4 bity przechowuje cyfry 0-9 wartość ORAZ nie musisz odejmować liczby szesnastkowej 30 od wartości znaku ASCII, aby uzyskać użyteczną cyfrę.
13

Ogólnie najszybszą biblioteką arbitralnej precyzji ogólnego przeznaczenia jest GMP . Jeśli chcesz pracować z wartościami zmiennoprzecinkowymi, spójrz na bibliotekę MPFR . MPFR jest oparty na GMP.

Jeśli chodzi o natywną obsługę dowolnej precyzji w innych językach, Python używa własnej implementacji ze względu na licencję, rozmiar i przenośność kodu. GMPY moduł umożliwia dostęp Pythona biblioteki GMP.

casevh
źródło
Dziękuję za odpowiedź! Wspomniał Pan o „przenośności kodu”. Czy mógłbyś wyjaśnić, na czym polega problem? Myślałem, że GMP jest przenośny i obsługiwany na głównych platformach ...
Siu Ching Pong -Asuka Kenji-
2
„Przenośność kodu” to nie to samo, co „obsługiwane na głównych platformach”. Python wykorzystuje prostą implementację, która przyjmuje bardzo niewiele założeń dotyczących zachowania kompilatora C, więc ten sam kod można kompilować na prawie każdym kompilatorze C. GMP wykorzystuje więcej kodu (C i wysoce dostrojony assembler), który przyspiesza GMP, ale także przyjmuje więcej założeń dotyczących zachowania kompilatora C i asemblera. Na przykład GMP nie jest dobrze obsługiwany przez kompilatory Microsoft Visual Studio. Istnieje fork GMP o nazwie MPIR (www.mpir.org), który obsługuje kompilatory Microsoftu.
casevh
Widzę. Oznacza to, że implementacja Pythona jest bardziej podobna do ANSI C, podczas gdy implementacja GMP wykorzystuje sztuczki __asm ​​... Dziękuję za wyjaśnienia.
Siu Ching Pong -Asuka Kenji-
8

Zobacz TTMath , małą bibliotekę z szablonami zawierającą tylko nagłówki, bezpłatną do użytku osobistego i komercyjnego.

Andrey Syrokomskiy
źródło
Hej! Jest to łatwa w użyciu biblioteka i wydaje się, że wykorzystuje moc procesora i używa magii szablonów C ++ do wykonania zadania. Świetna biblioteka! +1 dla Ciebie!
Siu Ching Pong -Asuka Kenji-
Tak, i ma liberalną licencję BSD, nie będącą copyleft.
plasmacel
Z powyższej strony: „To, jak duże mogą być wartości, jest ustawiane w czasie kompilacji”. - więc to nie spełnia wymagań.
osxdirk
7

Sam nie porównywałem ze sobą bibliotek arytmetycznych o arbitralnej precyzji, ale ludzie, którzy wydają się mieć mniej lub bardziej jednolite podejście do GMP. Co jest warte, liczby całkowite o arbitralnej precyzji w GHC Haskell i GNU Guile Scheme są zaimplementowane przy użyciu GMP, a najszybsza implementacja testu porównawczego pidigits w strzelaninie językowej jest oparta na GMP.

Richard Barrell
źródło
Dzięki! ^ ___ ^ Niezła informacja!
Siu Ching Pong -Asuka Kenji-
4

A co z Pari ? Jest zbudowany na najwyższym GMP i zapewnia wszystkie inne korzyści związane z operacjami teorii liczb, których kiedykolwiek będziesz potrzebować (i wiele symbolicznych rzeczy obliczeniowych).

fortran
źródło
Cześć fortran (!), Wygląda dobrze! Dziękuję za informację!
Siu Ching Pong -Asuka Kenji-
Nie ma za co :-) Również z Pari możesz toczyć szybkie prototypy za pomocą GP, a kiedy będziesz szczęśliwy, napisz zoptymalizowaną wersję C (i myślę, że jest ona wyposażona w kompilator GP-> C, który również w tym pomoże)
fortran