• Začalo to nějak takto
• Algoritmus pro genrování binárního čísla
• Algoritmus pro genrování hexadecimálního čísla
• Algoritmus pro genrování dekadického čísla
• Stažení programu
• Online verze programu

Začalo to nějak takto

V předmluvě Stopařova průvodce se praví: „Vesmír je velký, fakt velký, ani by jste nevěřili, jak hrozně moc úžasně velký je; a tak dále. Také se tam praví, že pokud se zhluboka nadechnete, můžete ve vesmírném vakuu přežít asi 30 vteřin. Ovšem vzhledem k té velikosti je pravděpodobnost, že vás během té doby někdo zachrání rovna jedna ku dvěma na dvě miliardy sedmdesát devět miliónů čtyřista šedesát tisíc třista čtyřicátou sedmou, což je náhodou také telefoní číslo izlingtonského bytu, kam se Arthur vydal na maškarní večírek a potkal dívku, kterou se mu nepodařilo sbalit.

Vzdělanější z vás poznali, že se jedná o úryvek z filmu Stopařův průvodce po galaxii. Ono číslo 2^{2 079 460 347} mě fascinovalo a inspirovalo k vytvoření tohoto programu. Řekl jsem si, že toto číslo by bylo zajímavé si vyčíslit. A tak jsem začal pracovat na jeho vyčíslení. Aby to však nebylo tak jednoduché, vzal jsem to obecněji a vytvořil jsem univerzální generátor mocnin dvojky od 2⁰ do 2^{4 294 967 296} s tím, že vygenerované číslo se uloží do textového souboru. A jako třešničku jsem k tomu dodal ještě soubory BIN.TXT a HEX.TXT, které tak zadané číslo uloží kromě dekadické soustavy také v binární a hexadecimální.

Při tvorbě programu jsem však zjistil, že kromě toho, že nemám dostatečně dobrý hardware na odzkoušení plné funkce programu (momentálně mě tížil nedostatek místa na disku, takže soubor s binárním číslem 2^{150 000 000} se mi na disk vešel jen tak tak. Po dopsání algoritmu na generování dekadického čísla jsem pak zjistil, že doba generování je exponenciálně závislá na velikosti zadaného exponentu, takže zatímco číslo 2^{10 000} mi vyplivl asi po 3 sekundách, číslo 2^{100 000} se generovalo asi minutu, generování 2^{1 0000 000} jsem po asi hodině zastavil.

Účel programu, zhmotnit číslo 2^{2 079 460 347}, sice nebyl naplněn, nicméně program je hotov a co je hlavní, uveřejňuji zde jeho zdrojové kódy (ty jsou ovšem jen pro silnější povahy!).

Binární číslo

Zapsat binární číslo bylo to nejjednodušší, proto tím také začínám. Máte-li totiž číslo 2ⁿ, pak zapsáno binárně je vlastně tvořeno tolika ciframi, kolik je exponent n. Samozřejmě, že binární číslo začíná vždy jedničkou, takže ji tam stačí prostě vepsat. Tím by byl algoritmus hotov: Vypíšeme jedničku a za i n nul. Pro přehlednost (má-li u kupy nul přehlednost vůbec smysl) jsem použil i oddělovač číslic, klasicky binárně po čtveřicích. Podstatně se tak algoritmus zrychlil, protože je rychlejší vypsat tisíckrát ‚ 0000‘ než čtyřtisíckrát ‚0‘.

Aby však byl zápis validní, musel jsem si číslo na čtveřice rozdělit a zjistit co mi zbyde a to dát na začátek (například číslo 2⁶D=100 0000B). Tento zbytek se určí opravdu doslova – v 7. řádku se prostě vypíše po jedné tolik nul, kolik zbývá (počítá se zbytek po celočíselném dělení – 8. řádek) do kompletní čtveřice a teprve potom už se vypíšou kompletní čtveřice (řádek 11).

 

Hexadecimální číslo

U hexa čísla je situace podobná jako u binárního. Ve své podstatě stačí říci, že každé 4 cifry binárně jsou 1 cifra hexadecimálně. Tím pádem má-li binární číslo třeba 1000 kompletních čtveřic, v hexa soustavě to bude rovných 250 cifer. Všechny (až na jednu) kompletní binární čtveřice jsou však nulové a tak se opět do hexadecimálního soubru zapíše n-krát ‚ 00‘, neboť hexadecimální čísla se oddělují po dvojicích cifer.

Ovšem problém nastal u té nekompletní úvodní dvojice cifer (například 2²³D=80 00 00H) neboť ta narozdíl od binárního čísla není pouze 1 a několik nul. Nabývá hodnot 1H (dvojnásobek je) 2H (další dvojnásobek je) 4H (pak) 8H (poté pozor, nikoliv 16H, ale) 10H, 20H, 40H, 80H a 1 00H, tedy 1H a další kompletní dvojice.

O vygenerování tohoto začátku se starají řádky 9 až 23. Nejdříve si opět určí zbytek, stejně jak u binárního čísla (jen pochopitelně s jiným dělitelem), a poté by stačilo vyčíslit 2^{tento zbytek} a převést toto číslo do hexadecimální soustavy. Číslo by sice by nebylo moc velké (nejvyšší hodnota by byla 80H, 128D), takže by tomuto postupu moc nebránilo. Ale to málo je jednak, fakt, že jazyk C nenabízí moc funkcí k umocňování (funkce pow nefungovala, tak jak měla) a pro převody číslených soustav neznám žádnou, a navíc by to bylo zbytečně časově náročné, když to jde i trošku „oprasit“.

Prostě se zeptá jestli ten zbytek je v hexa soustavě jednociferný (řádek 12), a pokud je, tak tu 1 cifru vyčíslí a vypíše. Pokud není, je tedy dvojciferný, vyčíslí tu první cifru a za ni vepíše nulu. Poslední řádek (25.) pak doplní zbývající, kompletní dvojce.

 

Dekadické číslo

Algoritmus pro generování dekadického čísla je z této trojice nejšílenější a proto si jej nechávám úplně na závěr. Dvojkový a šestnáctkový měly totiž základ, který určitým způsobem stál na čísle 2, jehož mocniny jsme chtěli zpracovávat. Ale desítka, ta je sice pětinásobkem dvojky, ale ta pěkta nám tam pořád hapruje a dělá velké problémy.

První myšlenka algoritmu měla fungovat asi nějak tak, že cyklus n-krát (kde n je počet mocnin), prodvojnásobí číslo počínaje jedničkou ( přičemž nás zajímá pouze poslední cifra, zbytek se ignrouje) ale po každé, když přeteče do vyššího řádu, zinkrementuje se (už jenom kvůli tomuto názvu jsem to chtěl napsat 😉 registr postupných inkrementací, jehož obsah by se pak předal dál a stejným způsobem násobil a násobil, a toto celé by se pak nějak opakovalo, až by se došlo do stavu, kdy by byl RPI prázdný, tedy už by nemělo co přetékat.

Bohužel tento systém selhal a tak mě napadl druhý, a to ten, že jsem zjistil, že čísla se v každém řádu opakují – pro řád jednotek je to (1), 2, 4, 8, (1)6, (3)2, a znovu. Opakují-li se takto čísla v jednotkách, opakují se i v desítkách, stovkách, tisících … Jenže perioda tohoto opakování rostla exponenciálně s řádem (pro jednotky zmiňované 4 čísla, pro desítky 20, pro stovky 100, pro tisíce 500, …) a navíc mě nenapadlo, jak ty data získat.

Jedinná použitelná metoda byla průběžné násobení a přičítání přetečení, tedy metoda, jakou to počítají děti na základní škole. Opravdu, musel jsem si vytvořit (dynmické) pole, ve kterém jsou uloženy jednotlivé cifry. Vzhledem k tomu, že ukládat 1 číslici, tedy číslo 0 až 9 na 4Byty dávalo účinnost asi 0,000002‰, tak mě napadlo, že když tam dám místo jedné cifry 3, nejen že se zjednoduší oddělování tisíců, ale možná to bude i rychlejší.

Doba generování 2^{100 000} snížíla z cca 57 sekund na pouhých 23. Jen tak z hecu jsem tam zkusil uložit těch cifer šest (čímž se ovšem naprosto brutálně zkomplikoval výpis do souboru a počet cifer se také musí celý přepočítávat) avšak když jsem zjistil, že čas je ještě téměř poloviční (14 vteřin), a paměti je také potřeba polovina, zmlkl jsem a nechal to tak.

Popis funkce algoritmu

Algoritmus tedy začne zalokováním paměti do zásoby (1 tisíc prvků). Poté začne násobit dvěma prvky pole (řádek 15), z nichž první začíní čislem 1 (řádek 9) a když už bude větší než 1 000 000 (řádek 17), tak uloží do proměnné carry jedničku (řádek 19), která se přičte v dalším „řádu“ (v další šestici). Jakmile dojede jednou (projde všechny číslice), ptá se, jestli přetekl i ten poslední řád (řádek 22)(třeba přechod z 512 na 1024), a tak zvýší počet řádů, které má procházet (řádek 29), automaticky tam zapíše tu jedničku, která do něj přetekla (řádek 28), ale to až po té, co si je jist, že ještě sem může zapisovat (že má ještě zalokovaný dostatek paměti; jinak si musí zabrat místo na dalších 2 000 prvků).

Jakmile číslo vygeneruje, musí poměrně složitě to, co má v paměti vypsat do souboru, tak aby to nějak vypadalo. To znamená, že čísla rozdělí na první a zbývající 3 cifry, které vypíše po sobě, avšak první musí vypsat bez bezvýznaných nul ( a to se v 34. řádku rozhoduje jestli tak má učinit u té první nebo až zbývající trojice). Součastně se musí hlídat, aby nevypsal dvakrát to samé nebo se nepokusil vypsat data, která už nepatří tomuto programu. S poslední šesticí cifer jsem měl problém vypsat ji v cyklu na 37 řádku a tak ji vypisuji zvlášť o řádek níž.

Tím, že v proměnné pocet majíce původně sloužit k uchování počtu cifer je uložen počet šestic cifer, je třeba určit přesný počet cifer. Ty se určují tak, že vezme první šestici a postupně ji provnává s mocninami desíti.

 

Stažení programu

Program jsem tvořil v mém IDE C write’n’run 1 (verze 2 je ke stažení zde) na Ubuntu, takže je primárně optimalizován na linuxové operační systémy. Při jeho tvorbě jsem s ním však měl nemalé problémy (proto jsem jej také tvořil měsíc) a při tom jsem jej zkoušel i na Windows, takže dodám i Windows verzi.

Nicméně zatím zde dodávám alespoň zdrojový kód:

Stažení zdrojového kódu generátoru mocnin dvojky.

a automatickou instalačku pro linux (stačí uložit a spustit):

Instalačka pro Linux ZDE

 

On-line verze programu

Ještě před tím, než jsem začal psát tento program v jazyce C, vytvořil jsem jej v PHP. Tuto prvotní verzi algoritmu samozřejmě dodávám také. Akorát on-line verze je omezena na exponent 5 000.

On-line verze zde