Czy są jakieś solidne implementacje dużych liczb całkowitych w C?

Question

Pracuję nad projektem, w którym muszę zgrupować duże liczby całkowite (jak 3^361) z absolutną precyzją i tak dużą prędkością, jak to możliwe. C jest najszybszym znanym mi językiem, więc próbuję zakodować moje rozwiązanie w tym języku.

Problem polega na tym, że nie byłem w stanie znaleźć dobrej implementacji żadnych typów danych do reprezentowania nieograniczonych liczb całkowitych w C innych niż kod źródłowy Pythona. Czas, aby przejść przez kod i ustalić, czego potrzebuję.

Wolę używać sprawdzonego kodu innej osoby z pełnym zestawem funkcji (dodawanie, odejmowanie, mnożenie, dzielenie, modulacja, potęgowanie, sprawdzanie równości ... nawet bitowa operacja byłaby słodka) niż spędzanie tygodni to zabierz mnie, abym nawet zaczął tworzyć swoją własną wersję na równi. Chociaż byłoby to świetnym doświadczeniem, to nie jest głównym tematem mojego problemu i wolałbym dostać się do części, która mnie interesuje :)

Answer 1

Gnu MP udostępnia bibliotekę bignum.

Answer 2

Kilka osób wspomniało już o GMP. Dodam tylko, że przynajmniej kiedy ostatnio wyglądałem, było całkiem dobrze ograniczone do pracy z gcc.

Jeśli chcesz użyć innych kompilatorów, to para, którą możesz rozważyć, to NTL i MIRACL. Przetestowałem nieco MIRACL i wydaje mi się, że działa dość dobrze. Używałem NTL całkiem sporo, a podczas gdy duże liczby całkowite są dla niego bardziej pożywką, to wciąż je całkiem ładnie. Nie twierdzi, że jest tak szybki jak GMP (i, w gruncie rzeczy, może używać GMP do wykonywania podstawowych operacji), ale kiedy przeprowadziłem pewne minimalne testy porównawcze między tymi dwoma, nie znalazłem wielu znaczących różnic (chociaż to było wystarczająco dawno temu, że wątpię, czy to już jest ważne).

Answer 3

Biblioteka OpenSSL zapewnia również solidną implementację BigNum (<openssl/bn.h>).

Answer 4

Używam biblioteki MAPM, która jest przenośną dowolną precyzją (integer i zmiennoprzecinkowy).

Answer 5

Jeśli potrzebujesz standardu ANSI C, pobierz kod w aplikacji Dave Hanson C Interfaces and Implementations. Bardzo jasne i dobrze zaprojektowane.

Jeśli rozszerzenia gcc i gcc są poprawne, to jak wskazano w innych dokumentach, Gnu jest dobrze przemyślaną i powszechnie używaną biblioteką.

Answer 6

libtommath, z libtomcrypt, jest prawdopodobnie najmniejszy, najprostszy i najszybszy. (Zabawne, jak te 3 superlatywy prawie zawsze spotykają się ...) Jeśli nie możesz znaleźć źródła, możesz pobrać źródło z drzewa źródłowego ssh dropbear.