Kompromis czasu i pamięci

Nowa wiadomość. W dziale inżynieryjnym w NASA powiedziano mi, że nowy łazik używa tej samej platformy pamięci co „Curiosity”. Łazik „Curiosity” miał dwa komputery, działające na zmianę. Parametry miał takie: 2 gigabajty pamięci flash, 256 megabajtów RAM-u i 256 kilobajtów pamięci tylko do odczytu, podtrzymującej podstawowe operacje systemowe. Chcielibyśmy przechowywać cały program w pamięci RAM, ale ponieważ musimy dzielić to miejsce z innymi programami, przydzielają nam 5% RAM-u i to jest maksimum do wykorzystania. To jakieś 12,8 megabajta. Mówię o tym, bo chcę zwrócić uwagę na związek między wielkością pamięci a czasem wykonywania programów. Przejrzałem program napisany przez IV46. Z tabelą miliona liczb pierwszych. Zatem algorytm mógł posuwać się jedynie po liczbach pierwszych, jak najdalej, przeprowadzając test pierwszości metodą próbnych dzieleń. Narzuca się pytanie: „Może by przechowywać potrzebne nam liczby pierwsze, do jakiejś granicy, w tabeli, zamiast znajdować je na bieżąco?”. Wspomnieliśmy w poprzednim odcinku, że byłoby to optymalne dla algorytmu próbnych dzieleń. Choć, zauważcie, jego algorytm nie używa wielu kroków, bardzo zwolnił i przestał działać jeszcze przed granicą. Nie mógł szybko rozwiązać problemu z wielkością, określonego wcześniej. W tym przypadku zyskiwali czas w postaci powtarzanych testów podzielności, kosztem przestrzeni, czyli pamięci do trzymania tabeli. Dlaczego to się nie udało? Obliczmy to z grubsza, używając tego, co już wiemy, by określić, czy to możliwa metoda przy danym ograniczeniu pamięci. Pamiętajcie: mamy sobie radzić z liczbami powyżej 9 biliardów. Algorytmy próbnych dzieleń będą sprawdzać czynniki do pierwiastka kwadratowego z danej liczby, a gdy nie znajdą, to mogą powiedzieć w 100%, czy ta liczba jest pierwsza. Ile jest liczb pierwszych do pierwiastka z tej granicy, gdzie pierwiastek z 9 biliardów to 94,9 mln? Ile jest liczb pierwszych mniejszych od 95 mln? Na szczęście mamy metodę pozwalającą znaleźć przybliżone rozwiązanie problemu: twierdzenie o liczbach pierwszych. Ile jest liczb pierwszych mniejszych od x? To x podzielone przez logarytm naturalny z x. A jeśli x przekracza 94,9 mln, widzimy, że liczb pierwszych jest około 5,1 mln. Ponieważ przechowujemy te liczby pierwsze, musimy znać wielkość największej z nich, czy, w tym przypadku, liczby pierwszej nr, ok. 5,1 mln. Wiemy, że będzie to liczba mniejsza niż 94,9 mln. Sprawdziłem w tabeli. Prawdziwa wartość tej liczby, największej, którą trzeba przechowywać, poniżej pierwiastka z granicy, to 89078611. Ile pamięci potrzebuje ta jedna liczba pierwsza? Zapiszmy ją w notacji binarnej, bo tak komputer będzie ją przechowywał, używając małych przełączników w pamięci. Uczyliśmy się o tym w odcinku o pamięci komputera. W bitach, największa liczba pierwsza wygląda tak. 24 bity lub 3 bajty są potrzebne do przechowania tej jednej liczby. Powiedzmy, że chcemy przechować w pamięci każdą liczbę, a skoro wiemy, że największa wymaga 24 bitów, to możemy sobie wyobrazić długą listę bloków 24-bitowych przechowujących każdą liczbę pierwszą. Ile trzeba bitów do całej listy? Potrzebna pamięć to liczba wartości, albo liczb pierwszych, razy miejsce na wartość. Mamy około 5,1 mln wartości razy 24 bity na wartość, a to jest trochę więcej niż 124 mln bitów. Jeśli przeliczymy to na bajty, wyjdzie jakieś 14,7 mln. Czyli prawie 15 megabajtów. Nie da się przechować nawet listy tych liczb w pamięci, przy danym ograniczeniu. To był tylko przykład, nie doszacowaliśmy naprawdę potrzebnego miejsca. Np. tabela potrzebuje miejsca na wskaźnik każdej jednostki, a każdy wskaźnik w 32-bitowej maszynie to 4 bajty. Zatem rzeczywista potrzebna ilość pamięci znacznie przekracza 15MB. Czyli przechowywanie wszystkich liczb pierwszych aż do pierwiastka kwadratowego z tej niskiej granicy nie jest możliwe przy naszym ograniczeniu. W ten sposób tego nie zrobimy. A może, kiedy spadną ceny, 1000 razy albo 10 000 razy…? Nowoczesne systemy kryptograficzne używają 512 bitów, a nawet większych liczb, co uniemożliwia wyszukiwanie i wyliczanie. Jeśli ktoś poprosi, żebyście zrobili listę liczb pierwszych, aż do 200-cyfrowych, nawet się nie zastanawiajcie, bo twardy dysk potrzebny do przechowania tych liczb byłby cięższy niż masa obserwowalnego wszechświata. Spróbujcie to sobie obliczyć, kiedy będziecie w restauracji, mając ołówek i papier na całym stoliku. Pamiętajcie, w obserwowalnym wszechświecie jest 10 do potęgi 80 atomów. To liczba 80-cyfrowa. Wiedzcie, że jest granica dostępnego miejsca czy pamięci. Nieważne, ile czasu by to zajęło, Zawsze konieczny jest kompromis między wykorzystaniem miejsca a czasem na rozwiązywanie zadań. Żeby rozwiązać to zadanie, test pierwszości, przy użyciu małej ilości miejsca i w krótkim czasie, będziemy musieli podejść do niego w zupełnie nowy sposób. Myślcie nietuzinkowo.