Bawię się z .NET BigInteger i zasadniczo zastanawiam się, jaka liczba - szacunkowa odpowiedź byłaby dobra - jest punktem odchylenia krzywej (wykres (wzrost czasu wymaganego do operacji) w porównaniu do (wartość BigInteger))?
czy są zaprojektowane bez takich odchyleń, że jeśli wykreślimy wzrost czasu wymaganego do operacji względem wartości BigInteger od 1 do nieskończoności, będziemy mieli gładką krzywą do końca?
na przykład przy założeniu, że tablice są zaprojektowane z możliwością obsługi 50 elementów. oznacza to, że jeśli mam 1 element, operacje są wykonywane w czasie f (1). a kiedy mam 2 elementy, operacje trwają f (2). jeśli mam 50 pozycji, operacjami są czas f (50). ale ponieważ jest przeznaczony do obsługi tylko 50 elementów, operacje wykonane, gdy będziemy mieli 51 elementów, będą miały wartość g (51), gdzie g (51)> f (51).
Przy prawidłowym zastosowaniu złożoność arytmetyki BigInteger powinna być gładką krzywą. Na przykład złożoność czasowa mnożenia powinna wynosić O (NM), gdzie N jest liczbą cyfr w pierwszym mnożniku, a M jest liczbą cyfr w drugim mnożniku. Oczywiście istnieją praktyczne ograniczenia, w których możesz wybrać N i M tak duże, że liczby nie zmieściłyby się w twoim komputerze.
Czy jest jakiś / czy ktoś wie o jakichkolwiek dokumentach twierdzących, że jest on zaimplementowany jako taki?
Odpowiedzi:
Każda liczba, która może być większa niż ULong.MaxValue lub mniejsza niż Long.MinValue, powinna być reprezentowana za pomocą BigInteger.
Jeśli NIE (Long.MinValue <= X <= ULong.MaxValue), to BigInteger
BigInteger jest dla zbyt dużych liczb, niż normalne prymitywy mogą znieść.
Na przykład, jeśli twoja liczba całkowita jest poza zakresem Long, prawdopodobnie powinieneś użyć BigInteger. Te przypadki są jednak bardzo rzadkie, a używanie tych klas ma znacznie wyższe koszty ogólne niż ich prymitywne odpowiedniki.
Na przykład
longma szerokość 64 bitów i może zawierać zakres: -9,223,372,036,854,775,808 do 9,223,372,036,854,775,80. ulong może pomieścić od 0 do 18 446,744,073,709,551,615. Jeśli twoje liczby są większe lub mniejsze, BigInteger jest Twoją jedyną opcjąJedynym razem, gdy widziałem, jak były używane w aplikacji w świecie rzeczywistym, była aplikacja do krochmalenia.
Zobacz także: Prymitywne zakresy w .NET
źródło
W pewnym sensie celem BigInteger jest nie tyle absolutny rozmiar, co nieograniczona precyzja. Liczby zmiennoprzecinkowe mogą być również bardzo duże, ale mają ograniczoną precyzję. BigInteger pozwala wykonywać arytmetykę bez obawy o błędy zaokrąglania lub przepełnienie. Cena, którą płacisz, jest setki razy wolniejsza niż arytmetyka ze zwykłymi liczbami całkowitymi lub liczbami zmiennoprzecinkowymi.
Jak zauważyli inni, ulong może pomieścić od 0 do 18 446,744,073,709,551,615, i dopóki pozostajesz w tym zakresie, możesz wykonywać dokładną arytmetykę. Jeśli przekroczysz nawet 1 poza ten zakres, otrzymasz przepełnienie, więc odpowiedzią na twoje pytanie jest użycie BigInteger, jeśli potrzebujesz dokładnej arytmetyki i istnieje możliwość, że dowolny wynik pośredni przekroczy 18 446,744,073,709,551,615.
Większość problemów w nauce, inżynierii i finansach może żyć z przybliżeniami wymuszonymi liczbami zmiennoprzecinkowymi i nie może sobie pozwolić na koszt czasowy arytmetyki BigInteger. Większość obliczeń komercyjnych nie może żyć z przybliżeniami arytmetyki zmiennoprzecinkowej, ale działa w zakresie od 0 do 18 446,744,073,709,551,615, więc mogą używać zwykłej arytmetyki. BigInteger jest potrzebny, gdy używa się algorytmów z teorii liczb, które obejmują takie rzeczy, jak kryptografia (pomyśl 50 liczb pierwszych). Czasami jest on również stosowany w aplikacjach komercyjnych, gdy potrzebne są dokładne obliczenia, prędkość nie jest zbyt ważna, a ustawienie odpowiedniego systemu dziesiętnego przecinka jest zbyt dużym problemem.
Przy prawidłowym zastosowaniu złożoność arytmetyki BigInteger powinna być gładką krzywą. Na przykład złożoność czasowa mnożenia powinna wynosić O (NM), gdzie N jest liczbą cyfr w pierwszym mnożniku, a M jest liczbą cyfr w drugim mnożniku. Oczywiście istnieją praktyczne ograniczenia, w których możesz wybrać N i M tak duże, że liczby nie zmieściłyby się w twoim komputerze.
Jeśli użyjesz w Google „Złożoności obliczeniowej bigintegera”, dostaniesz więcej referencji, niż możesz potrząsnąć. Jednym z nich jest odpowiedź na twoje pytanie: porównanie dwóch pakietów arytmetycznych o dowolnej precyzji .
źródło
Limit pamięci
BigInteger opiera się na tablicy int do przechowywania. Zakładając to, teoretyczny limit maksymalnej liczby, który BigInteger może reprezentować, można wyprowadzić z maksymalnego rozmiaru tablicy dostępnego w .net. Jest tutaj temat SO dotyczący tablic: Znajdowanie ilości pamięci, którą mogę przydzielić dla tablicy w języku C # .
Zakładając, że znamy maksymalny rozmiar tablicy, możemy oszacować maksymalną liczbę, którą BigInteger może reprezentować: (2 ^ 32) ^ max_array_size, gdzie:
Daje to liczbę z 600 milionami cyfr dziesiętnych.
Limit wydajności
Jeśli chodzi o wydajność, BigInteger używa algorytmu Karatsuba do mnożenia i algorytmu liniowego do dodawania. Złożoność mnożenia oznacza
, że będzie skalować się całkiem dobrze nawet dla dużych liczb ( wykres złożoności ), jednak nadal możesz trafić ujemną wydajność w zależności od wielkości pamięci RAM i pamięci podręcznej procesora.
O ile maksymalny rozmiar liczb jest ograniczony do 2 GB, na zjeździe nie zobaczysz nieoczekiwanej luki w wydajności, ale nadal działająca na liczbach 600 milionów cyfr będzie bardzo powolna.
źródło
Ograniczeniem jest rozmiar pamięci (i czas, który masz). Możesz mieć naprawdę duże liczby. Jak powiedział Kevin, w kryptografii należy pomnożyć lub potęgować liczby za pomocą tysięcy cyfr (binarnych), i jest to możliwe bez żadnych problemów.
Oczywiście często algorytmy stają się wolniejsze, gdy liczby stają się większe, ale nie tak dużo wolniej.
Kiedy używasz liczb z zakresu mega-cyfr, możesz jednak pomyśleć o innych rozwiązaniach - ponieważ ich obliczanie również się spowalnia.
źródło
Społeczność naukowa ma kilka zastosowań (tj. Odległość między galaktykami, liczba atomów w polu trawy itp.)
źródło
doublelubfloat- i tak nie masz niezbędnej precyzji.Jak sugeruje odpowiedź Kevina Cline'a, BigNumbers zostały dodane przede wszystkim do bibliotek .NET, ponieważ były potrzebne jako element składowy wielu nowoczesnych algorytmów kryptograficznych (podpisy cyfrowe, szyfrowanie kluczy publicznych / prywatnych itp.). Wiele współczesnych algorytmów kryptograficznych obejmuje obliczenia wartości całkowitych o rozmiarach do kilku tysięcy bitów. Ponieważ klasa BigNumber opisuje dobrze zdefiniowaną i przydatną klasę, postanowili ją upublicznić (zamiast utrzymywać ją jako wewnętrzny szczegół kryptograficznych interfejsów API).
źródło