Test prvočíselnosti
Přihlásit se
Test prvočíselnosti (8/9) · 6:34

Kompromis mezi pamětí a časem Jaké jsou hranice paměti? Jak můžeme šetřit časem na úkor prostoru?

Navazuje na Moderní šifrování.
Přináším aktuální informace: Oslovil jsem technické oddělení v NASA a zjistil jsem, že nová průzkumná sonda využívá stejnou paměťovou platformu jako Curiosity. Curiosity byla vybavena dvěma počítači, ale aktivní byl vždy pouze jeden z nich. Měl následující specifikace: 2 gigabajty paměti flash 256 megabajtů RAM paměti a 256 kilobajtů ROM paměti, která měla na starosti klíčové systémové funkce. Chceme být schopni uskladnit celý náš program v RAM paměti, avšak jelikož musíme tenhle prostor sdílet s jinými programy, je nám přiděleno 5% RAM, což představuje maximum, které můžeme využít. Jde o přibližně 12.8 megabajtů. Tuhle úvahu jsem započal, protože vás chci seznámit s myšlenkou "kompromisu času a paměti". Nebo kompromisu paměti a času. Jde o velice často používaný pojem u výpočetní techniky. Procházel jsem si program vytvořený IV46, který využíval pole složené z miliónu prvočísel, což umožňovalo jejich algoritmu postupovat pouze po prvočíslech tak daleko jak to jen šlo, když potřebovali dělat test prvočíselnosti. Nabízí se otázka: proč jednoduše nemít uložena všechna prvočísla do daného limitu v poli místo přímého počítaní, jestli se jedná o prvočíslo na místě? V předchozím videu jsme zmínili, že tohle by bylo optimálni pro rozklad dělením. Ačkoliv můžete vidět, že tento algoritmus nevyužívá hodně kroků, postupně zpomaloval až nakonec program spadl před dosažením hranice počtu kroků. Nebyl schopen vyřešit problém pro velikostí, které jsme si dříve definovali. V tomto případě zaměňovali čas v podobě opakovaných testů dělitelnosti na úkor prostoru -- paměti potřebné pro uchování pole. Proč to tedy nefungovalo? Udělejme si hrubý výpočet s využitím získaných vědomostí abychom zjistili, jestli je možné využit tenhle způsob pro omezenou paměť, která nám byla přidělena. Pamatujte, že to musí zvládnout pracovat s čísly většími než 9 biliard a naše algoritmy pro rozklad dělením testují jen do odmocniny hledaného čísla a pokud se dostanou až do odmocniny bez nalezení jakýchkoliv dělitelů, dá se jednoznačně říct, jestli se jedná o prvočíslo. Kolik tedy existuje prvočísel do odmocniny našeho limitu? Kde odmocnina z 9 biliard je 94,9 milióna, tedy prvočísel menších než 95 milionů? Naštěstí můžeme nalézt matematické řešení využitím teorie prvočíselnosti pro přibližné vyjádření odpovědi. Kolik prvočísel je menších než 'x'? Jde o 'x' děleno přirozený logaritmus čísla 'x'. A pokud 'x' je něco přes 94,9 milióna, zjišťujeme, že počet prvočísel je roven přibližně 5,1 miliónu. Jelikož potřebujeme někam tato prvočísla uložit, potřebujeme znát velikost největšího prvočísla, v našem případě cca 5,1 milióntého prvočísla. Víme, že půjde o číslo menší než 94,9 miliónu. Vyhledal jsem to v tabulce a přesná hodnota hledaného prvočísla, největšího prvočísla, které bychom museli uložit, protože se vešlo do naší hranice pod odmocninou je 89 078 611. Kolik paměti takhle velké číslo zabere? Abychom to zjistili, převeďme si jej do dvojkové soustavy, která představuje způsob reprezentace čísel v počítačích, využitím malinkých přepínačů v paměti. Tomuto se věnujeme ve videu o pamětech. V bitech vypadá největší číslo takhle: Jenom tohle jedno číslo zabírá 24 bitů, nebo 3 bajty. Řekněme, že chceme uložit v paměti všechna čísla a když teď víme, že největší z nich potřebuje 24 bitů, můžeme si představit dlouhý seznam 24-bitových bloků, z nichž v každém je uloženo jedno prvočíslo. Kolik bitů potřebujeme pro celý náš seznam? Potřebná paměť se vypočítá vynásobením počtu hodnot, neboli počtu prvočísel krát prostor, který využije jedna hodnota. Máme přibližně 5,1 miliónu hodnot, vynásobeno 24 bity na hodnotu nám dá něco přes 124 milionů bitů. Převedeno na bajty je to 14,7 miliónu, nebo téměř 15 megabajtů. Není tedy ani možné uložit si seznam čísel v naší omezené paměti. Vidíme, že uložení všech prvočísel do odmocniny našeho relativně malého limitu není uskutečnitelné pro paměť, která nám byla přidělena. Tímhle způsobem to nepůjde. Co kdyby klesly ceny řádově v tisícech nebo deseti tisícech? Moderní kryptografické systémy využívají 512 bitů velké, nebo dokonce větší čísla, čím se vyhledávání a výčet stává nemožným. Kdyby vás někdo požádal abyste udělali seznam všech prvočísel až do hodnot, které jsou 200 číslic dlouhá, neměli byste na to vůbec pomýšlet! Protože pevný disk potřebný pro uskladnění těchto prvočísel by byl těžší než hmota pozorovatelného vesmíru. Nechám ať si výpočet vyzkoušíte až někdy budete v restauraci s pastelkama, obklopeni lidma. Ale pamatujte, v pozorovatelném vesmíru je 10^80 atomů, to je 80-místné číslo. Existuje podstatní hranice udávající k jakému velkému prostoru nebo paměti můžeme přistupovat, není důležité kolik času to zabere. Pořád tu však je rozpor jestli klást důraz na prostor nebo čas při řešení problémů. Když ale chceme vyřešit problém zjišťování prvočíselnosti rychle, s využitím malého prostoru v paměti a šetřením času, budeme k němu muset přistupovat zcela novým způsobem.
video