Thread: Zakres liczb

Jaki typ zmiennej trzeba użyć dla zmiennej k, która sięga aż 10^100?
ze standardowej biblioteki to tylko BigInteger w javie
a w c++?
W STLu nie ma Bignumów. Na sprawdzarce nie ma nawet mojego ulubionego typu __int128, bo jest 32 bitowa. Dlatego jeżeli jesteś przekonany, że potrzebujesz długich intów i chcesz pisać w C++, to musisz sam je zaimplementować.

Na przyszłość: w niektórych konkursach (Google Code Jam, Facebook Hacker Cup), gdzie odpowiedzi do testów generujesz u siebie, wygodnie w C++ korzystać z biblioteki GMP (https://gmplib.org/).
@bignum na własne potrzeby: Czyste GMP może być trochę niewygodne. boost ma własne liczby wysokiej precyzji ( boost/multiprecision/cpp_int.hpp, dowolnej, jak i swojsko wyglądające int128t..int1024_t, dwa, trzy razy wolniejsze od GMP), do tego opakowuje GMP (albo MPIR, fork GMP, chyba łatwiejsza do zainstalowania pod windowsem) w coś, co zachowuje się jak liczba.
@Bartłomiej: GMP ma interfejs klasowy w C++, korzysta się z niego jak z typu wbudowanego
O! Nigdy nie zauważyłem;]
Jest jeszcze PARI, nie tyle sama biblioteka liczb wysokiej precyzji (ma coś własnego, można podpiąć GMP) co zestaw funkcji teorioliczbowych/algebraicznych.
Jak już jesteśmy w temacie, to skorzystam:
zna ktoś dobrą bibliotekę liczb _zmiennoprzecinkowych_ podwyższonej (ale nie dowolnej) precyzji.
Jest GMP, MPFR, jednak jeśli chcę "tylko" 30-60 dziesiętnych ("poczwórna" i "ośmiokrotna precyzja") miejsc znaczących, mają one spory narzut pamięci. Jest qd_real (http://crd-legacy.lbl.gov/~dhbailey/mpdist/) ale to tzw 'quad double' i mimo zwartości (32 bajty) nie jest znacznie szybsze.
Jako projekt na zaliczenie programowania w C++ na najwyższą ocenę na Uniwersytecie Łódzkim napisałem własnego vuint (Variable length Unsigned Integer) - cały kod w jednym nagłówku, na szablonie określającym długość, zużywa tylko tyle pamięci ile jest niezbędne, jest tak szybki jak to tylko możliwe w C++, świadomy strumieni i endianowości, nie alokuje żadnej pamięci nigdy, nie rzuca wyjątków, etc.

https://github.com/cni-open-source/vuint

quick link do źródełka:

https://github.com/cni-open-source/vuint/blob/master/include/vuint.hpp

Do tego macie w paczce testy Google'a (żeby się upewnić czy działa dobrze) i krótki przykład liczący 100! (silnię ze 100).

Licencja MIT/X11.
Dumnie brzmią słowa "Jako projekt na zaliczenie programowania w C++ na najwyższą ocenę [...] napisałem ...".
"jest tak szybki jak to tylko możliwe w C++"
Nie jest. Mnożysz liczby w O(n^2).
GMP, aby być najszybsze, używa siedmiu różnych algorytmów mnożeń. Piotr doktoratu nie pisał ;-)