Jak komputery oceniają ogromne liczby?

Question

Jeśli wprowadzę wartość Wolfram Alpha, na przykład 1234567^98787878, mogę podać mi kilka szczegółów. Obejmuje to przybliżenie dziesiętne, całkowitą długość, ostatnie cyfry itp. Jak oceniasz tak duże liczby? Jak rozumiem, język programowania musiałby mieć specjalny typ danych, aby przechowywać numer, nie mówiąc już o dodaniu go do czegoś innego. Chociaż widzę, jak można podejść do dodania dwóch bardzo dużych liczb, nie widzę, jak ocenia się olbrzymie liczby.

10^2 można obliczyć, dodając kolejne. Jednak liczba taka jak powyższy przykład wymagałaby gigantycznej pętli. Czy ktoś mógłby wyjaśnić, jak ocenia się tak duże liczby? Ponadto, w jaki sposób ktoś może utworzyć niestandardowy duży typ danych do obsługi dużych liczb w C# na przykład?

Answer 1

No to dość proste i można to zrobić samemu

1. Liczba cyfr można uzyskać poprzez logarytmu:

   od A^B = 10^(B * log(A, 10))

   możemy obliczyć (A = 1234567; B = 98787878) w naszym przypadku:

   B * log(A, 10)=98787878 * log(1234567, 10)=601767807.4709646...

   integer part + 1(601767807 + 1 =) oznacza liczbę cyfr

2. pierwsze powiedzmy pięć, cyfr można również uzyskać za pośrednictwem logarytmu; teraz powinniśmy analizować część ułamkowa

   B * log(A, 10)=98787878 * log(1234567, 10)=601767807.4709646...

   f = 0.4709646...

   pierwsze cyfry są 10^f (punkt dziesiętny usunięty) = ...

3. Ostatnio powiedzmy pięć, cyfry mogą być w postaci odpowiedniej reszty:

   pięciu znaków = A^B rem 10^5

   A rem 10^5=1234567 rem 10^5= `34567

   a^B rem 10^5 **=** ((A rem 10^5)^B), 10^5 rem **=** (34567^98787878) REM 10^5 = 45009`

   Ostatnie pięć cyfr

   można znaleźć BigInteger.ModPow (C#) bardzo użyteczny tutaj

Wreszcie

1234567^98787878 = 29577 ... 45009 (601767808 cyfr)

Answer 2

Zwykle istnieją biblioteki udostępniające typ danych binarnych dla dowolnie dużych liczb całkowitych (np. Odwzorowanie cyfr k*n...(k+1)*n-1, k=0..<some m depending on n and number magnitude> na słowo maszynowe o rozmiarze n przedefiniowanie operacji arytmetycznych). dla C#, możesz być zainteresowany BigInteger.

potęgowanie można rekurencyjnie podziale:

pow(a,2*b) = pow(a,b) * pow(a,b); 
pow(a,2*b+1) = pow(a,b) * pow(a,b) * a; 

liczbowo teoretyczne wyniki, które engenedered specjalnych algorytmów w celu określenia właściwości dużych ilościach bez faktycznie computing im tam też są (a dokładniej: ich pełna ekspansja po przecinku) .

Answer 3

Aby obliczyć, ile cyfr istnieją używa następujące wyrażenie:

decimal_digits(n) = 1 + floor(log_10(n)) 

To daje:

decimal_digits(1234567^98787878) = 1 + floor(log_10(1234567^98787878)) 
           = 1 + floor(98787878 * log_10(1234567)) 
           = 1 + floor(98787878 * 6.0915146640862625) 
           = 1 + floor(601767807.4709647) 
           = 601767808 

spływu cyfr K są obliczane wykonując potęgowania mod 10^k, który sprawia, że ​​wyniki pośrednie stają się zbyt duże.

Przybliżenie zostanie obliczone za pomocą implementacji zmiennoprzecinkowej (programowej), która efektywnie oceni^(98787878 log_a (1234567)) do pewnej stałej precyzji dla pewnej liczby a, która sprawia, że ​​arytmetyka działa dobrze (zazwyczaj 2 lub e lub 10). Pozwala to również uniknąć konieczności pracy z milionami cyfr w dowolnym momencie.

Answer 4

Myślę, że częścią odpowiedzi jest samo pytanie :) Aby zapisać te wyrażenia, można przechowywać bazę (lub mantysę), a także wykładnik osobno, podobnie jak notacja naukowa. Rozszerzając to, nie można w pełni ocenić wyrażenia i przechowywać tak dużych liczb, chociaż teoretycznie można przewidzieć pewne właściwości następującego wyrażenia. Przeprowadzę Cię przez wszystkie właściwości, o których mówisz:

1. Dziesiętne przybliżenie: Można obliczyć, oceniając proste wartości logu.
2. Łączna liczba cyfr dla wyrażenia a^b, może być obliczona za pomocą wzoru Cyfry = funkcja piętra (1 + Log10 (a^b)), gdzie funkcja piętra jest najbliższą liczbą całkowitą mniejszą od liczby. Dla np. liczba cyfr w 10^5 wynosi 6.
3. Ostatnie cyfry: Można je obliczyć na podstawie faktu, że wyrażenie liniowo rosnących wykładników tworzy postęp arytmetyczny. Dla np. na miejscu jednostek; 7, 9, 3, 1 powtarza się dla wykładników 7^x. Więc możesz obliczyć, że jeśli x% 4 wynosi 0, ostatnia cyfra to 1. Czy ktoś może utworzyć niestandardowy typ danych dla dużych liczb, nie mogę powiedzieć, ale jestem pewien, że liczba ta nie będzie oceniana i przechowywana .

Answer 5

Istnieje wiele bibliotek dla tego i zdolność jest wbudowana w przypadku Pythona. Wydajesz się przede wszystkim zainteresowana wielkością takich liczb i czasem, jaki zajmuje wykonanie obliczeń, takich jak wykładnik w twoim przykładzie. Więc wyjaśnię ci trochę.

Reprezentacja Możesz użyć tablicy do przechowywania wszystkich cyfr dużych liczb. Bardziej wydajnym sposobem byłoby użycie tablicy 32-bitowych liczb całkowitych bez znaku i zapisanie "32-bitowych porcji" dużej liczby. Te fragmenty można traktować jako pojedyncze cyfry w systemie liczbowym z 2^32 różnymi cyframi lub znakami. W tym celu użyłem tablicy bajtów w 8-bitowym Atari800.

Doing matematyki Można oczywiście dodać dwa takie numery poprzez zapętlenie nad wszystkimi cyframi i dodając elementy jednej tablicy do drugiej i śledzenie niesie. Gdy już wiesz, jak dodać, możesz napisać kod, aby wykonać "ręczne" mnożenie przez pomnożenie cyfr i umieszczenie wyników we właściwym miejscu i wiele dodatków - ale oprogramowanie zrobi to wszystko dość szybko. Są też szybsze algorytmy mnożenia niż te, których używałbyś ręcznie również na papierze. Mnożenie papieru to O (n^2), gdzie inne metody to O (n * log (n)). Jeśli chodzi o wykładnik, możesz oczywiście pomnożyć tę samą liczbę miliony razy, ale każde z tych mnożeń używa poprzednio wspomnianej funkcji do mnożenia. Istnieją szybsze sposoby na potęgowanie, które wymagają znacznie mniej mnożenia. Na przykład możesz obliczyć x^16, obliczając (((x^2)^2)^2)^2, które obejmuje tylko 4 rzeczywiste multiplikacje (dużej liczby całkowitej).

W praktyce To zabawne i edukacyjne, aby spróbować napisać te funkcje samodzielnie, ale w praktyce będzie chcesz użyć istniejącej biblioteki, które zostały zoptymalizowane i zweryfikowane.