Próbuję myśleć o tym, jak bym zrobił obliczenia na bardzo dużych liczbach (do nieskończoności - intergeruje brak liczb zmiennoprzecinkowych), jeśli konstrukcja języka nie jest w stanie obsłużyć liczb większych niż pewna wartość.
Jestem pewien, że nie jestem pierwszym ani ostatnim, który zadałby to pytanie, ale wyszukiwane hasła nie dają mi algorytmu do obsługi takich sytuacji. Raczej większość sugestii oferuje zmianę języka lub zmianę zmiennej lub mówi o rzeczach, które wydają się nieistotne dla mojego wyszukiwania. Potrzebuję więc trochę przewodnictwa.
Naszkicowałbym taki algorytm:
Określ maksymalną długość zmiennej całkowitej dla języka.
Jeśli liczba jest większa niż połowa długości maksymalnej długości zmiennej, podziel ją na tablicę. (daj trochę pokoju do zabawy)
Kolejność tablic [0] = liczby najbardziej po prawej [n-max] = liczby najbardziej po lewej
Dawny. Num: 29392023 Tablica [0]: 23, Tablica [1]: 20, tablica [2]: 39, tablica [3]: 29
Ponieważ ustaliłem połowę długości zmiennej jako punkt odcięcia, mogę następnie obliczyć te, dziesiąte, setne itd. Umieścić za pomocą znacznika w połowie, aby jeśli maksymalna zmienna długość wynosiła 10 cyfr od 0 do 9999999999, to wiem, że zmniejszając to do pięciu cyfr, daj mi trochę pokoju do zabawy.
Więc jeśli dodam lub pomnożę, mogę mieć funkcję sprawdzania zmiennych, która zobaczy, że szósta cyfra (z prawej) tablicy [0] to to samo miejsce, co pierwsza cyfra (z prawej) tablicy [1].
Dzielenie i odejmowanie ma swoje własne problemy, o których jeszcze nie myślałem.
Chciałbym wiedzieć o najlepszych implementacjach obsługi większych liczb niż program może.
źródło
Odpowiedzi:
Szukasz biblioteki arytmetyki o dowolnej precyzji (zwanej także „wielokrotną precyzją” lub „dużą liczbą”) dla języka, z którym pracujesz. Na przykład, jeśli pracujesz z C, możesz użyć Biblioteki GNU Bignum -> http://gmplib.org/
Jeśli chcesz zrozumieć, jak to działa, możesz także napisać własną bibliotekę dużych liczb i korzystać z niej. Najprostszym sposobem na poradzenie sobie z tym jest użycie tablic, w których każdy element jest cyfrą liczby, z którą pracujesz. Następnie musisz zaimplementować wszystkie funkcje, aby dodać, odjąć, pomnożyć, podzielić, potęgować i tak dalej.
źródło
Jest to dobrze znany problem: arytmetyka precyzji arbitralnej
Gdy używany język nie rozwiąże tego problemu, najpierw spróbuj znaleźć bibliotekę innej firmy, która to rozwiązuje. Jeśli nie możesz go znaleźć lub jesteś ciekawy, spróbuj go zaimplementować; artykuł w Wikipedii zawiera dobre odniesienia do klasycznych realizacji.
źródło
Kiedy mamy do czynienia z dużymi liczbami, prawdopodobnie jedną z najbardziej fundamentalnych decyzji projektowych jest to, jak mam reprezentować dużą liczbę?
Czy będzie to ciąg znaków, tablica, lista lub niestandardowa (własna) klasa pamięci.
Po podjęciu tej decyzji rzeczywiste operacje matematyczne można podzielić na mniejsze części, a następnie wykonać z rodzimymi typami języka, takimi jak int lub integer.
W C # .Net umieściłem bardzo podstawowy przykład DODATKU, który przechowuje wynikową dużą liczbę jako ciąg. Przychodzące „liczby” są również ciągami, więc należy móc wysyłać bardzo „duże” liczby. Należy pamiętać, że przykład dotyczy wyłącznie liczb całkowitych, aby było to proste.
Nawet w przypadku ciągów istnieje ograniczenie liczby znaków lub „liczb” w liczbie, jak wskazano tutaj:
Jaka jest maksymalna możliwa długość łańcucha .NET?
Ale możesz dodać kilka naprawdę dużych liczb, znacznie wykraczających poza natywne typy int32 lub int64 dla .Net.
Tak czy inaczej, oto implementacja przechowywania ciągów.
Mam nadzieję, że daje to kilka pomysłów na własne wdrożenie. Pamiętaj, że przykładowy kod prawdopodobnie nie jest zoptymalizowany lub coś podobnego. Ma on dać kilka pomysłów, jak można to zrobić.
źródło
Ten działa dla mnie szybciej:
źródło