każdy dokument, który dokładnie mówi, dla jakiego zakresu liczb są .NET BigIntegers?

12

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?

c# .net vb.net numbers

— Pacerier
źródło

3

@ Wyborcy, niższe głosy nic nie znaczą, jeśli nie można zostawić komentarza wyjaśniającego, dlaczego pytanie nie jest dobrym pytaniem. Głosowałem za tym, ponieważ nie widzę w tym żadnych problemów.

— The Muffin Man

Nie głosowałem, ale nie jestem pewien, o co tu chodzi. Czy chcesz poznać złożoność środowiska wykonawczego / pamięci operacji na bigintach (dodawanie, mnożenie, dzielenie itp.)?

— nikie

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, a operacje są czasem f (1). a kiedy mam 2 elementy, operacje trwają f (2). jeśli mam 50 operacji, to czas f (50). ale ponieważ jest przeznaczony do obsługi tylko 50 elementów, operacje wykonane, gdy będziemy mieli 51 elementów, to g (51), gdzie g (51)> f (51)

— Pacerier

@Charles E. Grant tak! o tym właśnie mówię. pytanie czy jest jakiś / czy ktoś wie o jakichkolwiek dokumentach twierdzących, że jest on zaimplementowany jako taki?

— Pacerier

@Paceier Przeniosłem swój komentarz do mojej odpowiedzi i dodałem link do dokumentu, w którym dokładnie to omawiam.

— Charles E. Grant,

7

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

— Malfist
źródło

oczywiście wiem, że powinniśmy używać normalnych prymitywów, kiedy tylko możemy. Mam na myśli, że powiedzmy, że BigInteger jest przeznaczony dla liczb 100 razy większych niż ULong.MaxValue czy BigInteger jest zaprojektowany dla liczb 100k razy większych niż ULong.MaxValue? Mam na myśli, że wiem, że może on obsługiwać 100k razy większy niż ULong.MaxValue, ale czy został zaprojektowany z myślą o tym zakresie, czy też został zaprojektowany z tym zakresem deklarowanym jako „nietypowy wymóg”?

— Pacerier

5

Nie możesz reprezentować liczby nawet jeden większej niż ULong.MaxValue bez użycia BigInteger, więc to jest to. Każda liczba, która może być większa niż ULong.MaxValue, powinna być BigInteger.

— Malfist

oczywiście istnieją sposoby reprezentowania liczb większych niż ULong.MaxValue i bez użycia BigInteger. Mógłbym po prostu napisać niestandardową strukturę, która składa się z ULong oraz wartości logicznej i altówki, którą mogę reprezentować nawet dwukrotnie ULong.MaxValue

— Pacerier

Tak, ale korzystanie z BigInteger jest o wiele mniej skomplikowane i prawdopodobnie nie byłoby o wiele szybsze, jeśli w ogóle, i nie byłoby tak elastyczne jak BigInteger. Możesz również reprezentować bardzo duże liczby za pomocą tablicy boolanów, ale to jest po prostu zbyt skomplikowane.

— Malfist

2

@Mavrik, zmienił to pytanie na zupełnie inne pytanie niż to, na które odpowiedziałem.

— Malfist

4

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 .

— Charles E. Grant
źródło

4

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:

2 ^ 32 - maksymalna liczba w komórce macierzy (int)
max_array_size - maksymalny dozwolony rozmiar tablicy int, który jest ograniczony wielkością obiektu 2 GB

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 3 * n ^ 1,585 , ż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.

— Valera Kolupaev
źródło

jest to wspaniała informacja, jednak gdzie jest twoje źródło, że BigInteger opiera się na tablicach int?

— Pacerier

Właśnie przekopałem się do źródeł .net za pomocą dotPeek. Wygląda na to, że sama liczba jest przechowywana w danych uint [] _data struktury BigInteger.

— Valera Kolupaev

* Zaktualizowano bardziej szczegółową odpowiedzią, jednak nie mogę znaleźć żadnego kodu źródłowego .net, do którego mogę się odwoływać, z wyjątkiem zdekompilowanych fragmentów.

— Valera Kolupaev

Wydaje mi się, że w .NET istnieje standardowy algorytm mnożenia, jak można to zrozumieć na podstawie ILSpy: .NET BigInteger Multiplication

— Ivan Kochurkin

1

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.

— Paŭlo Ebermann
źródło

0

Społeczność naukowa ma kilka zastosowań (tj. Odległość między galaktykami, liczba atomów w polu trawy itp.)

— Dave Wise
źródło

nie bądź niegrzeczny ... ale jak ta odpowiedź odnosi się do pytania?

— Pacerier

2

Pytanie, jak napisano, brzmi tak, jakby szukał rzeczywistego przykładu, dlaczego taki typ danych musiałby zostać utworzony.

— Dave Wise,

lepszym sformułowaniem byłoby „czy BigInteger naprawdę pasuje do liczb tak dużych jak 10 ^ 30”?

— Pacerier

W tym celu lepiej użyć doublelub float- i tak nie masz niezbędnej precyzji.

— Paŭlo Ebermann

lepszym sformułowaniem byłoby „czy BigInteger naprawdę pasuje do liczb tak dużych jak 10 ^ 30, gdy potrzebujemy precyzji”?

— Pacerier

0

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).

— Stephen C. Steel
źródło

btw tylko ciekawe, gdzie jest twoje źródło, że BigNumbers zostały dodane do bibliotek .NET przede wszystkim dlatego, że były potrzebne jako element składowy wielu nowoczesnych algorytmów kryptograficznych (a zatem powinny być w stanie obsługiwać wartości do kilku tysięcy bitów)?

— Pacerier