Wielkie tablice wielkich liczb w C i C++

tarpauwatratar · Feb '16

Zakładam, że dostępna pamięć jest nieograniczona. Pytanie: czy w C i C++ można używać bardzo dużych tablic, w których przechowane będą bardzo duże liczby, przy czym przez "bardzo duże liczby" rozumiem liczby wczytane do komputera z pomocą własnej struktury do arytmetyki wielkich liczb?

Przykładowo:
1. Definiuję strukturę BigInt, która przechowuje dowolną liczbę całkowitą,
2. Definiuję tablicę BigInt tab[BigInt];

Bardziej wymowny przykład:
1. jak wyżej
2. BigInt tab[9999999999999999999999999999999999999999999999999999];
3. for(BigInt i = 0; i < 9999999999999999999999999999999999999999999999999999; i++) tab[i] = i;

narbej · Feb '16

Poważny błąd, robieie takiego założenia.

Ani w C ani w C++, ani w żadnym innym znanym mi języku nie. Może marsiańscy ludkowie albo inni kosmici w swoim języku programowania to umieją, ja nic na ten temat nie wiem. Ale oczywiście [ograniczonej wielkości] tablice struktur Bignum, czy lepiej tablicę wskaźników do takich struktur możesz, jak najbardziej, jeżeli potrzebujesz, robić. Ograniczonej do wielkości dostępnych typów standartowych [aby indeksować tablicę] i do ograniczonej wielkości pamięci.

Swoją drogą, jeżeli to nie tajemnica, do czego Ci takie cuś potrzebne?

tarpauwatratar · Feb '16

Założenie jest głupie, ale pozwala uniknąć odpowiedzi "braknie Ci pamięci", bo o tym już wiem

Obawiałem się, że tak jest. Próbowałem to zrobić wszelkimi dostępnymi środkami, ale kompilator nie chciał współpracować. Dlaczego języki programowania tworzone przez Ziemian nie posiadają tej funkcjonalności? Czy jest to spowodowane wyłącznie tym, że na rzeczywistym komputerze pamięć jest ograniczona?

Przykładowo: chciałbym wygenerować sitem Eratostenesa liczby pierwsze od 1 do 10^1000.

narbej · Feb '16

Na pewno tak. Po co to robić jak i tak nie będzie można tego wykorzystać. Języki programowania dostosowywane są do możliwości dzisiejszych [a nie dopiero planowanym] komputerów. Dodatkowo jest małae zapotrzebowanie na taką funkcjonalność. Komu jest potrzebna taka tablica liczb pierwszych? Jeżeli już, to pojedyńcze duże lub nawet bardzo duże liczby pierwsze a nie wszystkie po kolei. Sito w takim zastosowaniu nie jest dobrym rozwiązaniem. Oczywiście osoby czy firmy, którym jest to konieczne i niezbędne mają lepszy sprzęt [niż PC] i mogą trochę więcej.

quenthui · Feb '16

Niech przemówią liczby.
Załóżmy, że masz na komputerze 8GB ramu.
To jest 8 * 10^9 bajtów.
Int zajmuje 4 bajty.
To oznacza, że teoretycznie możesz zaalokować tablicę intów o rozmiarze 2 miliardów (2 * 10^9).
W praktyce tyle nie dostaniesz, bo nie tylko twój program korzysta z pamięci.

Np. na spoju maksymalną tablicę intów, jaką możesz zaalokować to około 400 milionów (zakładając, że nie ma specjalnych limitów pamięci).

Jeśli potrzebujesz więcej, musisz korzystać z dysku. I jakoś mądrze symulować odwoływanie się do konkretnych indeksów. W ten sposób, mając dysk 4T możesz operować na tablicy o rozmiarze biliona (10^12) elementów.
Jednak to i tak za mało, żeby rozwiązać zadanie Prime or Not42.

Poprawcie mnie, jeśli się mylę.

PS. Pamiętaj, że zawsze możesz przeładować operator nawiasów kwadratowych tak, żeby poprawnie obsługiwał twoje BigInty.

tarpauwatratar · Feb '16

Dziękuję wam obu za wyjaśnienia.

Co do Prime or Not - zacząłbym od testu Millera-Rabina. Jeżeli to nie zadziała, to preprocessing albo sito Eratostenesa z wheel factorization (nie znam polskiego odpowiednika tej nazwy). Fajne zadanko, może zacznę rozwiązywać coś poza polskim SPOJem Tak czy siak jestem daleki od stosowania dla tego zadania BigInt. Moje pytanie kierowane jest ciekawością a nie zadaniami algorytmicznymi.

To była dygresja. Wracając do tematu; ostatnia rzecz jaką nie do końca rozumiem, to dlaczego w takim razie rozmiar jest narzucony na sztywno? Czy nie byłoby lepiej, gdyby maksymalny rozmiar możliwej do zaalokowania pamięci zależał od dostępnego na komputerze RAMu? Czy też może tak właśnie jest, ale ja jestem niedoinformowany? Wspomniane przez narbeja firmy mają lepszy sprzęt i mogą trochę więcej, na przykład mogą zapewne pomieścić w tablicy 10^12 elementów w sensie mają dostateczną ilość pamięci do tego celu. Czy one także są ograniczone przez języki programowania i nie mogą tego zrobić bo kompilator zaprotestuje?

tarpauwatratar · Feb '16

Dla potomnych, bo dyskusja zapewne dobieg(ł?)a końca a wątpię by ktoś chciał to wszystko czytać:

Nie można tworzyć dowolnie dzikich rozmiarowo tablic: tab[999999999999999999999999999999999999] odpada,
Polecam uwagę quenthui o dysku 4TB

I wreszcie:
4. int tab[maksymalny akceptowany przez kompilator rozmiar] działa. Ale już int tab[maksymalny akceptowany przez kompilator rozmiar] oraz int tab_2[maksymalny akceptowany przez kompilator rozmiar] - nie. Przynajmniej u mnie.

Zapewne dla wielu obecnych (myślę, że głównie programistów) moje zapytanie było idiotyczne z definicji. Niemniej osoby nie związane w żaden sposób z informatyką i programowaniem mogą, jak ja, zdziwić się zwłaszcza czytając punkt 3.

narbej · Feb '16

Co w tym dziwnego? Przecież kompilatory, interpretery, biblioteki i cała ta otoczka to także "zwykłe" programy komputerowe. Sam mógłbyś napisać swój własny kompilator i stworzyć swój własny język dostosowany do twoich potrzeb i do możliwości twojego komputera. Mógłbyś także wymyśleć zupełnie abstrakcyjny i przyszłościowy i dostosowany do nieistniejących jeszcze komputerów.

Przecież ciągle powstają nowe. Język C++ powstał, bo język C nie oferował pewnych możliwości, a istniejące języki, który je oferowały, były za wolne czy też miały inne wady. I tak jak programy komputerow [i systemy operacyjne] ewolują, rozwijają się, umierają i powstają nowe, tak i kompilatory [i języki programowania] nie stoją w miejscu. C, C ANSI, C++, C++11, C++14 itd.
A w między czasie inżynierowie od sprzętu, też nie śpią i dostarczają więcej mocy, pamięci i możliwości, więc "języki", a raczej kompilatory i biblioteki, muszą się dostosowywać. Ale co będzie nawet w niedalekiej przyszłości?

Więc cierpliwości, może kiedyś ....

tarpauwatratar · Feb '16

"Dziwność" jest związana z przyzwyczajeniami. W biol-chem nie brakuje przyszłościowych rozważań, wybiegania w przyszłość o lata i pytania o rzeczy niewykonalne a następnie obalanie tezy o niewykonalności (ile osób uważało, że poznanie genomu ludzkiego jest niewykonalne / wykonalne w ciagu 100 wzwyż lat). Zaś programiści są strasznie pragmatyczni. Program ma po prostu działać, co oznacza realizowanie żądanego celu. Nie ma miejsca to po co tworzyć obsługę tablic takiego rozmiaru. To dla mnie dziwne - w biologii wszystko ogląda się pod mikroskopem, analizuje, gdyba o prehistorycznych organizmach... nikt nawet nie myśli o tym, że mamutów już nie ma. A tutaj krótko: nie da się bo nie ma miejsca i po co tworzyć coś na przyszłość skoro jak na razie nie starczy miejsca?

Trudno mi to wytłumaczyć więc streszczę to krótko, choć przez to nie do końca słusznie: w biologii ani razu nie widziałem podejścia praktycznego. A w programowaniu wszystko jest praktyczne.

sig · Feb '16

Nie zapominaj że ilość błędów jest wprost proporcjonalna do ilości linii kodu, a stopień skomplikowania kompilatora przypominał by pewnie stopień skomplikowania co najmniej średniego samolotu. Przy czym trzymając się analogii np kolor dywanika przy wejściu może mieć wpływ na wszystko ze sterami i pracą silników włącznie.

Wracając do tematu, podejrzewam że tego typu rzeczy są w systemach na superkomputery, i w razie czego zostaną przeniesione na mniejsze maszyny. Obecnie zwyczajnie nie ma powodu do takiej migracji i związanych z nią problemów

narbej · Feb '16

Na pewno masz dużo racji i programowanie to praktyczna działka informatyki. Ale Informatyka to nie tylko programowanie. To także teoria i prace badawcze, nie koniecznie [od razu] praktyczne - jakie, ja jestem praktykiem więc Ci nie odpowiem.
A obliczenie liczby PI z dokładnością do wielu miejsc po przecinku, czy szukanie największej liczby pierwszej i pewnie jeszcze kilka takich przykładów, toż to czysta abstrakcja. Nawet w podróżach międzygalaktycznych taka dokładność liczby Pi nie jest chyba potrzebna - abstrachując, że takie podróże są możliwe.

sig · Feb '16

Co do pi to znamy ją chyba z taką dokładnością, że ze względu na nierówności powodowane przez atomy nie da się zrobić aż tak "idealnego" kółka. Tak więc to już "sztuka dla sztuki"

ps do autora tematu. To może dodaj do tej własnej arytmetyki własny typ tablicowy?

tarpauwatratar · Feb '16

Pi i idealne koła to rzeczywiście bardzo dobry przykład na abstrakcję w informatyce. Zgadzam się, że sztuką dla sztuki jest wyznaczanie dziwnych liczb z gigantyczną dokładnością.

Co do typu tablicowego to po namyśle i lekturze tematu stwierdzam, że jest on słabej jakości rozwiązaniem - chyba lepiej poszperać w książkach i artykułach naukowych jak najlepiej radzić sobie z dużymi liczbami, a nie próbować tworzyć własny język programowania z dzikimi rozmiarami tablic.

Wielkie tablice wielkich liczb w C i C++

created

last reply

replies

views

users

links

Suggested Topics

Want to read more? Browse other topics in Tutoriale, poradniki or view latest topics.

Wielkie tablice wielkich liczb w C i C++

created

last reply

replies

views

users

links

Suggested Topics

Want to read more? Browse other topics in Tutoriale, poradniki or view latest topics.

share a link to this topic