“Where shall I begin, please, Your Majesty?” he asked. “Begin at the beginning,” the King said, gravely, “and go on till you come the end. Then stop.” (Lewis CARROLL – Alice in Wonderland)
Úvod Co musí v dnešní době vědět informatik na vysoké profesionální úrovni, aby mohl obstát před skutečně obtížnými problémy? Programovací jazyk? Určitě. Kromě toho mnoho věcí z oboru, který se nazývá matematická informatika. Mnohdy směřovala výuka pouze k umění ovládat počítač a ke znalosti některého programovacího jazyka, vedly se diskuse o tom, zda je vhodné používat ten či onen programovací jazyk, zda je vhodné používat ten nebo onen počítač. Abychom viděli plastičtěji, že v tom je dosti velké nebezpečí, představme si, že se seznamujeme s chemií tak, že se nejdříve obeznámíme s Bunsenovým hořákem, pak postupně v laboratoři objevíme řadu zajímavých přístrojů a začneme dělat pokusy. Zvládnout aparatury moderní chemie v laboratoři vyžaduje zručnost i otevřenou hlavu, předváděné pokusy jsou poutavé a často i vzrušující. Tak se vždy těšíme do laboratoře a odcházíme z ní někdy očouzeni, vždy však spokojeni. Z toho, co víme o chemii, je nám jasné, že se naše seznamování s chemií minulo cílem, protože celá laboratoř a pokusy v ní jsou jenom nástroj ke zkoumání vlastností, složení, vnitřní stavby a přeměny látek. Tzn. cílem toho všeho je dojít k chemickým rovnicím, vzorcům atd. a k umění je používat. Jinak bychom měli k chemii vztah ztělesněný nezapomenutelným strýcem Františkem z Jirotkova Saturnina: … Protože chemii vůbec nerozuměl, byly cesty jeho objevů posety trny a zkropeny potem, ale tím větší byla jeho radost ze získání zkušeností. Nebylo mu lze upřít sportovního ducha. Podobal se člověku, který po zvládnutí malé násobilky prohlásil svým učitelům: Dál už mi nic neříkejte. Nechci nic slyšet o tom, že pan Pythagoras, Eudoxus, Euklides, Archimédes a tak dále, vymyslili to a to. Nepotřebuji týt z toho, co objevili jiní. Dejte mi papír, tužku a kružítko a nechte mne na pokoji. Však já na to přijdu sám. A strýček opravdu na leccos přišel. Tak například zjistil při pokusu, který měl vzrušující průběh, že lít vodu do kyseliny je blbost, a vůbec mu nevadilo, že tento poznatek, korektněji vyjádřený, mohl získat z učebnice chemie pro nižší třídy škol středních, aniž by si přitom popálil prsty a zánovní vestu. Chemie mu byla panenskou pevninou, roztočeným větrným zámkem plným dveří, které se otvíraly tajemnými formulemi. Neznal názvosloví, ignoroval valenční koncovky a žasl, když mu ve zkumavkách a křivulích šuměly prudké chemické reakce. …
Chemických strýců Františků není mnoho, protože není tak jednoduché opatřit si chemickou laboratoř. Informatickým strýcem Františkem se člověk stane snadněji, neboť je velice jednoduché opatřit si vlastní počítač. Vraťme se tedy od chemie k informatice a odpovězme na otázku, kterou jsme poměrně snadno odpověděli v případě chemie. Co je vlastním předmětem informatiky (a speciálně matematické informatiky), jestliže ovládání počítače, znalost programovacích jazyků a speciálního software jsou pouhé nástroje? Odpověď je jednoduchá a jednoznačná – algoritmy. Pojem algoritmus je ústřední pojem informatiky. Algoritmy pronikají téměř všemi oblastmi lidské činnosti. Algoritmické postupy užíváme v denním životě, ve vědecké činnosti, ve výrobě, v řízení podniku atd. Zároveň to ukazuje, že nejde o okrajovou a módní záležitost. Jak jsme uvedli v historii i současnosti matematiky a informatiky (a nejen v nich) hrály a hrají důležitou roli předpisy k řešení konkrétních úloh, např. předpisy pro čtyři základní aritmetické operace s přirozenými čísly zapsanými v desítkové soustavě. Předpisy tohoto charakteru se zabýval počátkem devátého století arabský učenec abú Abdalláh Muhammad ibn Músa, alChwárizmí (nebo al-Chorezmí), al-Madžúsí1, latinské zkomolení části jeho jména uvedlo do 1
Syn v Evropě z Pohádek Tisíce a jedné noci známého bagdádského chalífy Hárúna ar-Rašída chalífa Abdalláh al-Mamún pověřil kolem r. 819 vedením bagdádského „Domu moudrosti“ (což byla tehdejší obdoba jakési akademie věd) abú Abdalláha Muhammada ibn Músu, al-Chvárizmího, al-Mádžusího (Muhammad, syn Músův, otec Abdalláhův, pocházející z Chorezmu; arabsky )أ بو ع بد ال مح مد بن مو سى الخوارز مي, který žil v letech kolem 783 až kolem 850 (prokazatelně žil v letech 813 – 833 v Bagdádu). Jméno al-Chvárizmí označuje, že pocházel z východoperské provincie Chorezm, což byl pozdější sultanát Chiva (nyní součást Uzbekistánu). Pozdější arabští matematici se odkazovali na jeho díla slovy qala al-Chvárizmí, což středověcí evropští matematici překládali do latiny Algorismi dixit (česky tak praví Algorismi). Z jeho díla, které zasahuje do řady vědních oblastí, je pro nás v tomto okamžiku nejzajímavější aritmetika. Ta obsahuje výklad indického početního systému (ztratil se arabský originál, ale existuje latinský překlad z 12. stol.). Al-Chvárizmího kniha seznámila Evropu s desítkovou poziční soustavou, proto se ještě dnes používá pro námi používaná číslice v desítkové soustavě název arabské číslice, i když měla původ v Indii. Právě desítková soustava umožnila snad poprvé v pravém slova smyslu dětské ovládání i velmi složitých početních operací a automatické zkoušek a kontrol, který tkví
evropských jazyků slovo algoritmus. Tento pojem je stěžejní i v matematické informatice. Známe-li etymologii slova, neznamená to, že bychom znali jeho význam. Uveďme filosofické vymezení tohoto pojmu. Algoritmem rozumíme přesný předpis, podle kterého máme vykonat v určitém pořadí konečný počet operací, které vedou k řešení každé úlohy či každého problému daného typu. Uveďme několik příkladů známých algoritmů. (1) Výše zmíněné čtyři základní aritmetické operace s přirozenými čísly zapsané v desítkové číselné soustavě (nebo v soustavě o jiném základu, např. 2). (2) Stará čínská matematika měla pro řešení nejrůznějších typů úloh zásobu algoritmů, které byly pečlivě předávány z generace na generaci. Ke zjištění, zda přirozené číslo n je prvočíslo, měli čínští matematici jednoduchý algoritmus – stačilo zjistit, zda číslo n dělí beze zbytku číslo 2n – 2. Pokud ano, jde o prvočíslo, pokud je zbytek nenulový, jde o číslo složené. Tento algoritmus má jeden kaz, na který staří Číňané nepřišli – jde o nesprávný algoritmus. Nejmenší číslo, které dává chybnou odpověď, je 341, protože číslo 2341 – 2 je dělitelné číslem 341, ale 341 = 11 . 31, tzn. 341 není prvočíslo, ale číslo složené. Existuje obrana proti takovým nepříjemným překvapením? Odpověď nalezneme, srovnáme-li matematické tradice staré Číny se starou řeckou matematikou. V Číně se uvedl předpis a dále se nezkoumal, tj. zasvěcenec předal algoritmus zasvěcenci („program přehrál z paměti do paměti“) a ten jej začal používat. V antickém Řecku následovala ještě fáze – proč algoritmus skutečně dělá to, co se tvrdí? Tj. algoritmus doprovázel důkaz2. (3) Již ve starověku známý Eukleidův3 algoritmus popsat takto: Jsou-li m a n kladná přirozená čísla, potom největšího společného dělitele čísel m a n určíme v následujících postupných krocích. 1. krok – dělme číslo m číslem n. Zbytek dělení označme r (0 ≤ r < n). v samotné soustavě. Muhammad vytvořil první algoritmy pro počítání s čísly, čímž se matematika dostala do škol a do obchodního světa, odkud pak při obchodech Arabů s Evropany také do Evropy. Evropa se tak rovněž seznámila s Indy používanou nulou, která pro Araby byla as sifr (překlad indického prázdnota). Tak k nám proniklo slovo cifra. Až do 19. stol. se obecně nevědělo, jak vzniklo slovo algoritmus, ačkoli se jej používalo již od dob Leibnizových. Předpokládalo se, že jde o zkomolení výrazu logaritmus a rozhodně se uváděla souvislost s řeckým slovem arithmos (číslo). Latinský překlad al-Chvárizmího traktátu Algorithmi de numero indorum (Algorithmiho indická čísla) zavedl do všech evropských jazyků termín algoritmus, který je latinizovaným jménem autora. 2 Tento algoritmus sebou nese poučení, jehož důležitost snad ani nelze dostatečně zdůraznit – i algoritmus, který byl dlouhou dobu používán a testován, může být špatný. A to natolik špatný, že nejrozumnější náprava je jej zahodit a hledat jiný algoritmus. 3 Eukleidés (řecky Εΰκλείδης; kolem r. 365 př. n. l. – kolem r. 300 př. n. l.) – řecký geometr, který žil v Alexandrii. Nevíme toho o něm mnoho, neznáme místo jeho narození ani smrti. Z jeho života nevíme skoro nic. Ale jeho opera magna třináctidílné Základy (řecky Στοιχεῖα,tj. Stoicheia) jsou snad vedle Bible doposud nejvydávanější knihou světa. Toto dílo sloužilo až donedávna bez jakýchkoli zásadních úprav za učebnici geometrie na anglických středních školách. Eukleidovy Základy jsou rozděleny do třinácti knih a vrcholí systémem axiómů, totiž systémem nejjednodušších, dále již nedokazatelných a nerozložitelných základních pravd, na nichž spočívá celá geometrie. První kniha Základů pojednává o trojúhelnících a rovnoběžnících a končí důkazem Pythagorovy věty. Druhá kniha rozvíjí planimetrii, kniha třetí a čtvrtá pokračuje ve výkladu planimetrie a pojednává o kruhu, tětivových a tečnových mnohoúhelnících. Kniha pátá se týká nauky o poměrech, kniha šestá se pak věnuje geometrické podobnosti. V dalších knihách podává výklad teorie čísel, hovoří o prvočíslech a podává důkaz, že prvočísel je nekonečně mnoho. Eukleidés se dostává až k teorii iracionálních čísel. Zde se dostal do značných obtíží kvůli zápisu těchto čísel, kdy teorii čísel budoval pomocí geometrie a délek úseček. Jedenáctá dvanáctá a třináctá kniha se zabývají stereometrií, stejně jako knihy zbývající. Při svých úvahách o objemu těles Eukleidés pracuje tak, jako by znal základy infinitezimálního počtu, který objevili až v 17. století Leibnitz a Newton. Vypráví se o něm pověst, že věnoval své dílo panovníkovi, který ho za toto dílo obdaroval. Zároveň se ho ptal, zda není do tajů geometrie snazší cesta, než jsou Základy. Eukleidés mu podle pověsti odpověděl: „Ne, pane můj. Není královské cesty ke geometrii. Bez práce nejsou ani koláče, ani geometrie.“
2. krok – je-li r = 0, potom n je největší společný dělitel; je-li r > 0, potom pokračujme třetím krokem. 3. krok – dosaďme za m číslo n a za n číslo r a opakujme postup od prvního kroku. Všechny algoritmy lze (alespoň teoreticky) realizovat na počítači, a nic jiného než algoritmy není možné na počítači realizovat. To zase vysvětluje, proč se informatika jako věda o algoritmech rozvinula až v éře počítačů a proč počítače jsou v této éře důležitým nástrojem. Celé nepřeberné bohatství algoritmů, které bylo během lidské historie vytvořeno a po tisíciletí se předávalo od rodičů k dětem, od učitele k žákům, od mistra k učedníkům, od staršího referenta k mladšímu referentovi atd., všechny tyto algoritmy je nyní možno „preparovat“ a realizovat na počítačích, tj. naprogramovat je. Spolu s nimi realizovat navě nalézané algoritmy, které by v předpočítačové éře neměly praktické uplatnění. Pro jednotlivé problémy nás zajímají odpovědi na dvě základní otázky: (a) Existuje algoritmus, který řeší tento problém? (b) Pokud existuje algoritmus řešící daný problém, skončí použití algoritmu v reálném čase? Na otázku (a) lze odpovědět, že existují problémy, které nelze algoritmicky řešit. Na otázku (b) budeme hledat odpověď v části věnované výpočtové složitosti algoritmů.
abú Abdalláh Muhammad ibn Músa, al-Chwárizmí, al-Madžúsí
Eukleidés
Aurea prima sata est aetas, quae vindice nullo,
sponte sua, sine lege fidem rectumque colebat. (OVIDIUS – Metamorphoses)4
1. Čísla a jejich reprezentace v počítači Symbolem N označíme množinu všech kladných celých čísel, symbolem Z množinu všech celých čísel, symbolem Q všech racionálních čísel a symbolem R množinu všech reálných čísel. Základní početní úkony jsou – pokud to posuzujeme z našeho hlediska – jednoduché a nenáročné algoritmy, které se děti snadno naučí ovládat již v prvních letech školní docházky. To je ovšem náš pohled. Jestliže například písemně sčítáme dvojici čísel, používáme řadu „vynálezů“ objevených předchozími generacemi myslitelů – čísla zapisujeme v desítkové číselné soustavě, oba zápisy vhodně umístíme pod sebe, pomocí znaku „+“ budoucímu čtenáři připomeneme, že jde o sčítání, sčítance podtrhneme a pak pomocí výpočtů od nejnižších k nejvyšším řádům zjišťujeme a na příslušná místa zapisujeme cifry, abychom získali zápis hledaného součtu původních sčítanců. Jak je to všechno samozřejmé! Ve skutečnosti vykonáváme vysoce odbornou činnost, která se nám snadnou pouze zdá. Cesta k našemu způsobu zápisu aritmetických výpočtů byla velmi dlouhá. Ani cesta k zápisu práce s proměnnými, jak si vyžadovala rodící se algebra o něco později, nebyla snadná. Podívejme se na počátky písemných aritmetických operací! Svědčí o neustálém hledání nových způsobů řešení, o důležitosti vhodných algoritmů (vlastně optimalizaci metod) nejen pro praxi, ale i jako podmínky k dalšímu zobecňování a rozvoji vědy. V současnosti známe tři metody sčítání (menších) přirozených čísel: pomocí prstů, kuliček na počitadle či kaménků a písemné sčítání. Sčítání zpaměti zde neuvádím, protože jeho počátky jsou rovněž vázány na představy o předmětech (prsty, kuličky...). První dvě metody nemusí být vázány na číselnou soustavu, jde-li o malá čísla. Pak každý prst či kulička značí jeden počítaný předmět. Jestliže dítě na prstech ukazuje, že „dva a jeden jsou tři“, používá právě tuto nejstarší pomůcku pro sčítání. Jiná situace nastane, jakmile prsty či kuličky nemají stejný význam, ale mohou podle potřeby znázorňovat různý počet jednotek. Takové metody používali i negramotní lidé (nebylo třeba nic zapisovat), ale ve svých spisech je doporučovali i významní matematikové. Např. Leonardo Pisánský, zvaný Fibonacci, autor knihy Liber abaci z roku 1202, prvního evropského vskutku systematického výkladu zápisů čísel indoarabskými ciframi (dědečky našich současných cifer), zde konečně uznává nulu (tedy cifru 0, znak pro nic) za plnohodnotné číslo a podrobně zde popisuje, jak výhodně počítat na prstech v pozičním systému. Prsty (digiti) znázorňovaly jednotky, články prstů (articuli) desítky atd. Čísla sama pak dělil na jednotky, desítky a čísla složená. Toto dělení na digiti a articuli užívala středověká aritmetika a anglický název pro jednotky – digits – na středověké označení navazuje. Výpočty pomocí prstů se mohly praktičtěji provádět na početních deskách. „Zapsaná čísla“ byla názornější a mohlo se pracovat též s čísly podstatně většími. Početní desky byly ploché kameny či jiné rovné plošky pokryté vrstvou písku. Do písku se vyryly rýhy vyznačující jednotlivé řády (jednotky, desítky, stovky...). Do těchto rýh se kladly kaménky zvané calculi. Každý kamének znamenal jednotku příslušného řádu.. Do vývoje tohoto prvního „počítacího stroje“ vstoupila i hlava veškerého tehdejšího křesťanstva. Kolem roku 1000 totiž učenec Gerbert, pozdější papež Silvestr II., začal používat místo kaménků značky zvané apices. Byly to na kouscích dřeva či „střípcích“ zapsané cifry.
4
Nejdříve vzešel věk zlatý, kdy bez zákonů a soudců člověk od sebe sám si správně a poctivě vedl. (Ovidius – Proměny; překlad I. Bureš)
Zde uvedená tabulka znázorňující čísla pomocí prstů pochází ze spisu Summa de arithmetica (autorem je matematik Luca Pacioli), všimněme si, že v tomto systému záleželo nejen na poloze prstů, ale též na tom, zda byla použita ruka pravá či levá
Římský abakus
Nejprve se budeme věnovat kladným celým, celým a racionálním číslům a jejich vyjádření v číselných soustavách.
1.1 Číselné soustavy Číselná soustava je způsob reprezentace čísel. Podle způsobu určení hodnoty čísla z dané reprezentace rozlišujeme dva hlavní druhy číselných soustav: poziční číselné soustavy a nepoziční číselné soustavy. V praxi se však také používaly způsoby reprezentace používající postupy z obou těchto druhů. Dnes se obvykle používají soustavy poziční. Čísla se skládají z uspořádané množiny symbolů, nazývaných číslice a z relací mezi čísly definovaných pro jednotlivé aritmetické operace (sčítání, odčítání, násobení a dělení). Základ či báze5 číselné soustavy se značí r a definuje maximální počet číslic, které máme v dané soustavě k dispozici. Mezi číselné soustavy nejčastěji používané patří: (a) Desítková (dekadická, r = 10), má pravděpodobně původ v počtu prstů na obou rukou, jde o takové zobrazení číselných hodnot, při kterém je jako základu použito mocniny čísla 10. Zopakujme, proč je 348 rovno právě 348: je to proto, že tato hodnota obsahuje 3 stovky (stovka = 102), 4 desítky (desítka = 101) a 8 jednotek (jednotka = 100), tj. 3.10 2 + 4.101 + 8.10 0 = 3.100 + 4.10 + 8.1 = 348. Nyní rozšiřme opakování o to, proč je 348,65 rovno právě 348,65: 3.10 2 + 4.101 + 8.10 0 + 6.10 − 1 + 5.10 − 2 = 3.100 + 4.10 + 8.1 + 6.0,1 + 5.0,01 = 348,65. Podotkněme jen, že správně by všechna čísla v tomto odstavci zapisovaná měla být důsledně označena základem své soustavy; místo 348 by tedy mělo být lépe zapsáno (348)10. Zatím však byla použita jen desítková soustava a tedy se „to nepletlo“. Poslední připomenutí: v zápise čísel může být právě tolik různých hodnot daného řádu, kolik je základ soustavy. To znamená např. žádnou stovku, jednu stovku, dvě stovky, ..., osm stovek nebo devět stovek. Deset stovek už ne, protože to by byla jedna tisícovka („přechod přes řád“). Pro vyjádření těchto deseti různých hodnot je zapotřebí deseti různých symbolů. V našich končinách a našem věku bývá zvykem používat symboly 0, 1, 2, ..., 8 a 9. Dekadická soustava je referenční, tzn. většinou převádíme vyjádření do dekadické soustavy. (b) Dvojková (binární, r = 2), je číselná soustava která používá pouze dva symboly – nejčastěji 0 a 1. Dvojková soustava je poziční číselná soustava mocnin čísla 2. Používá se ve všech moderních počítačích, neboť její dva symboly (0 a 1) odpovídají dvěma stavům elektrického obvodu (vypnuto a zapnuto). Číslo zapsané v dvojkové soustavě se nazývá binární číslo. Jde o číselnou soustavu se základem 2. Analogii s desítkovou soustavou začněme „od konce“ – v zápise čísel může být právě tolik různých hodnot daného řádu, kolik je základ soustavy (tj. dvě). To znamená např. žádnou dvojku nebo jednu dvojku; dvě dvojky už ne, protože to by byl „přechod přes řád“. Pro vyjádření těchto dvou různých hodnot je zapotřebí dvou různých symbolů. Bývá zvykem používat symboly 0 nebo O (pro počet žádný) a 1 nebo I (pro počet jeden). Každý zápis číselné hodnoty ve dvojkové soustavě proto může obsahovat pouze symboly 0 a 1. Je tedy např. 1001 jistě zápis číselné hodnoty ve dvojkové soustavě. Aby bylo zcela jasné, že jde o zápis právě ve dvojkové soustavě, zapisuje se hodnota jako (1001)2 nebo (IOOI)2 na rozdíl např. od (1001)10. S ohledem na probíranou problematiku ještě jedna poznámka: obsah jednoho bytu může být interpretován jako zápis právě osmiciferného dvojkového čísla. Nejmenší číselná hodnota je osm nul, tedy nula. Největší číselná hodnota je osm jedniček. Postup uvedený shora dává pro hodnotu (11111111)2 ekvivalent v desítkové (11111111) 2 = 1.2 7 + 1.2 6 + 1.2 5 + 1.2 4 + 1.2 3 + 1.2 2 + 1.21 + 1.2 0 = ( 255) 10 , soustavě všech různých obsahů jednoho bytu je tedy 256. (c) Osmičková (oktalová, r = 8), která se používá při programování. (d) Dvanáctková (r = 12) – dnes málo používaná, ale dodnes z ní zbyly názvy prvních dvou řádů – tucet a veletucet, dvanáctková soustava Sumerů je dávána do spojitosti s 5
anglicky radix
šestiprstou lidskou rasou, která se vyskytuje v mýtech různých národů, druhým prozaičtějším důvodem pro tuto soustavu je pravděpodobně snazší dělení na třetiny proti desítkové soustavě. (e) Šestnáctková (hexadecimální, r = 16), která se podobně jako osmičková soustava používá při programování. (f) Šedesátková (r = 60) – používá se k měření času, číslice 0–59 se obvykle zapisují desítkovou soustavou Každé číslo vyjádřené v těchto soustavách může mít část celočíselnou (před desetinnou čárkou6) a část desetinnou (za desetinnou čárkou). Uvedené soustavy řadíme mezi polyadické, ve kterých se číslo vyjadřuje součtem mocnin základu dané soustavy vynásobených příslušnými platnými číslicemi7. Způsoby zápisu (a) Poziční zápis – představuje pozice každé číslice v daném čísle její relativní váhu významnosti. Obecně platí, že kladné číslo může být zapsáno pozičně následovně: a = ( a k a k − 1 a k − 2 ...a1 a 0 a − 1 a − 2 ...al ) r , kde a k je nejvyšší významová číslice8, n − l nejnižší 4 významová číslice9 a r základ číselné soustavy. Např. číslo v číselné soustavě o 3 základu 10 a s přesností na 5 desetinných míst lze zapsat pozičně následovně: 4 = ( 4,33333) 10 . 3 10 (b) Polynomiální zápis – obecně lze zapsat číslo v číselné soustavě o základu r polynomem následovně:
a=
k
∑
i= − l
ai r i = a k r k + a k − 1 r k − 1 + a k − 2 r k − 2 + ... + a 0 r 0 + a − 1 r − 1 + ... + a − l r − l .
Každá číslice je zde vynásobena vahou danou její pozicí a vyjádřenou mocninou 4 základu r. Např. číslo v číselné soustavě o základu 10 a s přesností na 5 desetinných 3 4 = 4.10 0 + 3.10 − 1 + 3.10 − 2 + 3.10 − 3 + 3.10 − 4 + 3.10 − 5 . míst lze zapsat polynomiálně 3 Převody Pro převod čísla a ze soustavy o základu r do soustavy o základu s lze použít: (a) metodu substituční při použití aritmetiky soustavy o základu s, (b) metoda dělení sn tak, že sn ≤ a < sn+1, (c) pro čísla celá metodu dělení základem a pro čísla desetinná metodu násobení základem. Substituční metoda – zapíšeme-li čísla polynomiálně je základem pro tuto metodu převodu, podle které je číslo a zapsané v soustavě o základu r převedeno do soustavy o základu s v následujících dvou krocích: (a) číslo se vyjádří polynomem v soustavě o základu r, (b) výpočet se provede aritmetikou soustavy o základu s.
6
či tečkou používanou v anglosaských zemích Existují i soustavy, které využívají odečítání. Příkladem budiž trojková soustava, která obsahuje znaky s významem –1, 0, +1. Poziční zápis se vyhodnocuje podobně jako u běžné trojkové soustavy, ale tato soustava 7
umožňuje přímo zapisovat záporná čísla a rozsah čísel o n znacích je obvody s třístavovou logikou. 8 Označuje se MSB 9 Označuje se LSB
3n − 1 . Tato soustava je vhodná pro 2
Substituční metoda je vhodná pro vzájemné převody mezi soustavou binární, oktalovou a hexadecimální, dále pro převod z těchto soustav do soustavy dekadické. Nehodí se však pro převod z dekadické do ostatních. Postup Převodu čísel z různých soustav do soustavy dekadické: (a) nejprve se číslo, které chceme převést, vyjádří v původní číselné soustavě polynomem, (b) následně se, již v aritmetice cílové soustavy, spočtou mocniny čísel, každá mocnina se vynásobí hodnotou příslušné číslice a vše se sečte. Příklad. (10011,011) 2 = 1.2 4 + 0.2 3 + 0.2 2 + 1.21 + 1.2 0 + 0.2 − 1 + 1.2 − 2 + 1.2 − 3 = = 16 + 2 + 1 + 0,25 + 0,125 = (19,375) 10 . n Metoda dělení s je určena zpravidla pro převod celých čísel v desítkové soustavě do soustavy o základu s. Postup Pro kladné celé číslo a určíme přirozené číslo n tak, aby sn ≤ a < sn+1. 1. krok – a : sn = bn + cn, kde 0 ≤ cn < sn, 2. krok – cn : sn-1 = bn-1 + cn-1, kde 0 ≤ cn-1 < sn-1, … n+1-ní krok – c1 : s0 = c1 : 1 = b0, potom a = ( bn bn − 1 ...b1b0 ) s . Příklad. Číslo 109 v desítkové soustavě vyjádříme ve dvojkové soustavě. 109 : 26 = 109 : 64 = 1 + 45, tj. b6 = 1, 45 : 25 = 45 : 32 = 1 + 13, tj. b5 = 1, 13 : 24 = 13 : 16 = 0 + 13, tj. b4 = 0, 13 : 23 = 13 : 8 = 1 + 5, tj. b3 = 1, 5 : 22 = 5 : 4 = 1 + 1, tj. b2 = 1, 1 : 21 = 1 : 2 = 0 + 1, tj. b1 = 0, 1 : 20 = 1 : 1 = 1, tj. b0 = 1, tedy (109 ) 10 = ( b6 b5 b4 b3 b2 b1b0 ) 2 = (1101101) 2 . Metoda dělení základem je určena pro převod celých čísel mezi soustavami. Postup Celé číslo a je vyjádřeno na k+1 platných číslic v soustavě o základu r polynomem a = ( a k a k − 1 a k − 2 ...a 2 a1 a 0 ) r = a k r k + a k − 1 r k − 1 a k − 2 r k − 2 + ... + a 2 r 2 + a1 r 1 + a 0 r 0 . Vztah lze přepsat podle základu s soustavy, do které chceme číslo převést tak, aby se základy vyskytovaly bez mocnin: a = ( a k a k − 1 a k − 2 ...a 2 a1 a 0 ) r = ( ( ...( bn s + bn − 1 ).s + ... + b2 ).s + b1 ).s + b0 = ( bn bn − 1 ...b2 b1b0 ) s . Výsledkem převodu je číslo, které má jednotlivé výsledné číslice zapsané pozičně v soustavě o základu s. Příklad. (109) 10 = ( ( ( ( (1.2 + 1).2 + 0).2 + 1).2 + 1).2 + 0).2 + 1 = = 1.2 6 + 1.2 5 + 0.2 4 + 1.2 3 + 1.2 2 + 0.21 + 1.2 0 = (1101101) 2 . Způsob, jak vyjádřit číslo v požadovaném tvaru (nejnižší významový bit b0 lze nalézt jako zbytek při celočíselným vydělením čísla a základem s): a : s = bn .s n + bn − 1 s n − 1 + ... + b1 s 1 + b0 s 0 : s = bn .s n − 1 + bn − 1 s n − 2 + ... + b1 s 0 + b0 . Celočíselný výsledek dělení je c0 a zbytek je b0 (0 ≤ b0 < s), jde o poslední platnou číslici čísla a zapsanou v soustavě o základu s.
(
)
(
)
Číslo c0 opět dělíme s, zbytek představuje předposlední číslici čísla a zapsanou v soustavě o základu s. Pokračujeme dále až do okamžiku, kdy výsledek je 0, potom zbytek bn představuje první platnou číslici čísla a v soustavě o základu s. Příklad. Číslo 109 v desítkové soustavě vyjádříme ve dvojkové soustavě metodou dělení základem s = 2, tzn. (109) 10 : 2 = ( 54) 10 , zbytek je b0 = 1, ( 54) 10 : 2 = ( 27 ) 10 , zbytek je b1 = 0, ( 27 ) 10 : 2 = (13) 10 , zbytek je b2 = 1, (13) 10 : 2 = ( 6) 10 , zbytek je b3 = 1, ( 6) 10 : 2 = ( 3) 10 , zbytek je b4 = 0, ( 3) 10 : 2 = (1) 10 , , zbytek je b5 = 1, (1) 10 : 2 = ( 0) 10 , zbytek je b6 = 1. Tudíž (109 ) 10 = ( b6 b5 b4 b3 b2 b1b0 ) 2 = (1101101) 2 . Příklad. Číslo 1033 v desítkové soustavě vyjádříme ve dvojkové soustavě metodou dělení základem s = 2, tj. (1033) 10 : 2 = ( 516) 10 , zbytek je b0 = 1, ( 516) 10 : 2 = ( 258) 10 , zbytek je b1 = 0, ( 258) 10 : 2 = (129) 10 , zbytek je b2 = 0, (129) 10 : 2 = ( 64) 10 , zbytek je b3 = 1, ( 64) 10 : 2 = ( 32) 10 , zbytek je b4 = 0, ( 32) 10 : 2 = (16) 10 , zbytek je b5 = 0, (16) 10 : 2 = ( 8) 10 , zbytek je b6 = 0, ( 8) 10 : 2 = ( 4) 10 , zbytek je b7 = 0, ( 4) 10 : 2 = ( 2) 10 , zbytek je b8 = 0, ( 2) 10 : 2 = (1) 10 , , zbytek je b9 = 0, (1) 10 : 2 = ( 0) 10 , zbytek je b10 = 1. Tudíž (1033) 10 = ( b10 b9 b8 b7 b6 b5 b4 b3b2 b1b0 ) 2 = (10000001001) 2 . Příklad. Číslo 1033 v osmičkové soustavě vyjádříme ve dvojkové soustavě. Uvedeme dvě cesty. (a) Číslo 1033 vyjádříme v desítkové soustavě, tj. využijeme polynomiálního tvaru (1033) 8 = 1.83 + 0.8 2 + 3.81 + 3.8 0 = 512 + 24 + 3 = ( 539) 10 . Nyní použijeme metodu dělení základem s = 2, tj. ( 539) 10 : 2 = ( 269) 10 , zbytek je b0 = 1, ( 269) 10 : 2 = (134) 10 , zbytek je b1 = 1, (134) 10 : 2 = ( 67 ) 10 , zbytek je b2 = 0, ( 67 ) 10 : 2 = ( 33) 10 , zbytek je b3 = 1, ( 33) 10 : 2 = (16) 10 , zbytek je b4 = 1, (16) 10 : 2 = ( 8) 10 , zbytek je b5 = 0, ( 8) 10 : 2 = ( 4) 10 , zbytek je b6 = 0,
( 4) 10 : 2 = ( 2) 10 , zbytek je b7 = 0, ( 2) 10 : 2 = (1) 10 , , zbytek je b8 = 0, (1) 10 : 2 = ( 0) 10 , zbytek je b9 = 1. Tudíž (1033) 8 = ( b9 b8 b7 b6 b5 b4 b3b2 b1b0 ) 2 = (1000011011) 2 . (b) Použijeme metodu dělení základem s = 2 přímo (1033) 8 : 2 = ( 415) 8 , zbytek10 je b0 = 1, ( 415) 8 : 2 = ( 206) 8 , zbytek11 je b1 = 1, ( 206) 8 : 2 = (103) 8 , zbytek je b2 = 0, (103) 8 : 2 = ( 41) 8 , zbytek10 je b3 = 1, ( 41) 8 : 2 = ( 20) 8 , zbytek je b4 = 1, ( 20) 8 : 2 = (10) 8 , zbytek je b5 = 0, (10) 8 : 2 = ( 4) 8 , zbytek10 je b6 = 0, ( 4) 8 : 2 = ( 2) 8 , zbytek je b7 = 0, ( 2) 8 : 2 = (1) 8 , , zbytek je b8 = 0, (1) 8 : 2 = ( 0) 8 , zbytek je b9 = 1. Tudíž (1033) 8 = ( b9 b8 b7 b6 b5 b4 b3b2 b1b0 ) 2 = (1000011011) 2 . Poznámka. Je jedno, kterou cestu vybereme. Při přímém výpočtu je potřebné respektovat dělení v soustavě s původním základem. Příklad. Číslo 1000010111 ve dvojkové soustavě vyjádříme v osmičkové soustavě. Uvedeme tři cesty. (a) Číslo 1000010111 vyjádříme v desítkové soustavě, tj. využijeme polynomiálního tvaru (1000010111) 2 = 1.2 9 + 0.2 8 + 0.2 7 + 0.2 6 + 0.2 5 + 1.2 4 + 0.2 3 + 1.2 2 + 1.21 + 1.2 0 = = 512 + 16 + 4 + 2 + 1 = ( 535) 10 . Nyní použijeme metodu dělení základem ( 535) 10 : 8 = ( 66) 10 , zbytek je b0 = 7, ( 66) 10 : 8 = ( 8) 10 , zbytek je b1 = 2, ( 8) 10 : 8 = (1) 10 , zbytek je b2 = 0, (1) 10 : 8 = ( 0) 10 , zbytek je b3 = 1. Tudíž (1000010111) 2 = ( b3 b2 b1b0 ) 8 = (1027 ) 8 . (b) Použijeme metodu dělení základem přímo (100001011) 2 : 8 = (100001011) 2 : (1000) 2 = (1000010) 2 , zbytek je b0 = (111) 2 = ( 7 ) 8 , (1000010) 2 : 8 = (1000010) 2 : (1000) 2 = (1000) 2 , zbytek je b1 = (10) 2 = ( 2) 8 , (1000) 2 : 8 = (1000) 2 : (1000) 2 = (1) 2 , zbytek je b2 = ( 0) 2 = ( 0) 8 , (1) 2 : 8 = (1) 2 : (1000) 2 = ( 0) 2 , zbytek je b3 = (1) 2 = (1) 8 . Tudíž (1000010111) 2 = ( b3 b2 b1b0 ) 8 = (1027 ) 8 . (c) Zřejmě nejjednodušší cesta je přes polynomiální vyjádření (1000010111) 2 = 1.2 9 + 0.2 8 + 0.2 7 + 0.2 6 + 0.2 5 + 1.2 4 + 0.2 3 + 1.2 2 + 1.21 + 1.2 0 =
(
)
(
)
(
)
= 1.2 9 + 0.2 2 + 0.21 + 0.2 0 .2 6 + 0.2 2 + 1.21 + 0.2 0 .2 3 + 1.2 2 + 1.21 + 1.2 0 .2 0 = Je vhodné si uvědomit, že (10 ) 8
: 2 = ( 4) 8 . 11 Je vhodné si uvědomit, že (15) 8 : 2 = ( 6) 8 a zbytek je 1. 10
( )
( )
( )
( )
+ 2. 2 3 + 7. 2 3 = 1.8 3 + 0.8 2 + 2.81 + 7.8 0 = (1027 ) 8 . Tudíž (1000010111) 2 = (1027 ) 8 . Metoda násobení základem je určena pro převod desetinných12 čísel z intervalu ( 0,1) mezi soustavami. Postup Desetinné číslo a větší než 0 a menší než 1 vyjádřené na l platných číslic polynomem v soustavě o základu r má tvar a = ( 0, a − 1 a − 2 ...a − l − 1 al ) r = a − 1 r − 1 + a − 2 r − 2 + ... + a − l − 1 r − l − 1 + a − l r − l . Vztah lze přepsat podle základu s soustavy, do které chceme číslo převést tak, aby se základy vyskytovaly bez mocnin: a = ( 0, a − 1 a − 2 ...a − l − 1 al ) r = s − 1 . b− 1 + s − 1 . b− 2 + ... + s − 1 . b− n − 1 + s − 1 .b− n ... = ( 0, b− 1b− 2 ...b− n − 1b− n ) s . Výsledkem převodu je desetinné číslo, které má jednotlivé výsledné číslice zapsané pozičně. Příklad. ( 0,625) 10 = 2 − 1. 1 + 2 − 1. 0 + 2 − 1. 1 + 2 − 1.1 = 1.2 − 1 + 0.2 − 2 + 1.2 − 3 = ( 0,101) 2 . Způsob jak vyjádřit číslo v požadovaném tvaru (nejvyšší významový bit lze nalézt vynásobením desetinného čísla základem): a.s = s. s − 1 . b− 1 + s − 1 . b− 2 + ... + s − 1 . b− n − 1 + s − 1 .b− n ... = b− 1 + s − 1 b− 2 + ... + s − 1 . b− n − 1 + s − 1 .b− n ... . Platí, že každá číslice je počítána postupným (iteračním) násobením desetinného výsledku předchozí iterace základem soustavy, do které chceme číslo převést. Po každém iteračním kroku se sepisuje celočíselná část výsledku a převod končí, když je výsledek násobení roven nule nebo se nedosáhne požadované přesnosti. Příklad. Číslo 0,625 v desítkové soustavě převedeme do dvojkové soustavy metodou násobení základem s = 2, ( 0,625) 10 .2 = 1,25 = 1 + 0,25 = b− 1 + 0,25, tj. b-1 = 1, ( 0,25) 10 .2 = 0,5 = 0 + 0,5 = b− 2 + 0,5, tj. b-2 = 0, ( 0,5) 10 .2 = 1,0 = 1 + 0,0 = b− 3 + 0,0, tj. b-3 = 1. Tedy ( 0,625) 10 = ( 0, b− 1b− 2 b− 3 ) 2 = ( 0,101) 2 . Příklad. Číslo 0,6875 v desítkové soustavě převedeme do dvojkové soustavy metodou násobením základem s = 2, ( 0,6875) 10 .2 = 1,375 = 1 + 0,375 = b− 1 + 0,375, tj. b-1 = 1, ( 0,375) 10 .2 = 0,75 = 0 + 0,75 = b− 2 + 0,75, tj. b-2 = 0, ( 0,75) 10 .2 = 1,5 = 1 + 0,5 = b− 3 + 0,5, tj. b-3 = 1, ( 0,5) 10 .2 = 1,0 = 1 + 0,0 = b− 4 + 0,0, tj. b-4 = 1. Tedy ( 0,6875) 10 = ( 0, b− 1b− 2 b− 3 b− 4 ) 2 = ( 0,1011) 2 . Příklad. Číslo 0,625 v desítkové soustavě převedeme do osmičkové soustavy metodou násobení základem s = 8, ( 0,625) 10 .8 = 5,0 = 5 + 0,0 = b− 1 + 0,0, tj. b-1 = 5, tedy ( 0,625) 10 = ( 0, b− 1 ) 8 = ( 0,5) 8 . Příklad. = 1. 2 3
3
+ 0. 2 3
(
(
( (
12
anglicky fractional
(
2
1
(
(
(
(
(
0
) ))
)))
) )))
(
(
) )
Číslo 0,6875 v desítkové soustavě převedeme do osmičkové soustavy metodou násobením základem s = 8, ( 0,6875) 10 .8 = 5,5 = 5 + 0,5 = b− 1 + 0,5, tj. b-1 = 5, ( 0,5) 10 .8 = 4,0 = 4 + 0,0 = b− 2 + 0,0, tj. b-2 = 4. Tedy ( 0,6875) 10 = ( 0, b− 1b− 2 ) 8 = ( 0,54) 8 . Příklad. Číslo 0,1011 ve dvojkové soustavě převedeme do osmičkové soustavy převodem užitím polynomiálního tvaru, tj. ( 0,1011) 2 = 1.2 − 1 + 0.2 − 2 + 1.2 − 3 + 1.2 − 4 = 1.2 2 + 0.21 + 1.2 0 .2 − 3 + 1.2 2 + 0.21 + 0.2 0 .2 − 6 =
(
)
( = 5.( 2 ) + 4.( 2 ) 3 −1
3 −2
)
= 5.8 − 1 + 4.8 − 2 = ( 0,54 ) 8 ,
tedy ( 0,1011) 2 = ( 0,54 ) 8 . Poznámka. Pokud by měl být desetinný rozvoj dlouhý ukončíme činnost na osmém desetinném místě. Příklad. Číslo 0,3421 v desítkové soustavě převedeme do dvojkové soustavy metodou násobení základem s = 2, tzn. ( 0,3421) 10 .2 = 0,6842 = 0 + 0,6842 = b− 1 + 0,6842, tj. b-1 = 0, ( 0,6842) 10 .2 = 1,3684 = 1 + 0,3684 = b− 2 + 0,3684, tj. b-2 = 1, ( 0,3684) 10 .2 = 0,7368 = 0 + 0,7368 = b− 3 + 0,7368, tj. b-3 = 0, ( 0,7368) 10 .2 = 1,4736 = 1 + 0,4736 = b− 4 + 0,4736, tj. b-4 = 1, ( 0,4736) 10 .2 = 0,9472 = 0 + 0,9472 = b− 5 + 0,9472, tj. b-5 = 0, ( 0,9472) 10 .2 = 1,8944 = 1 + 0,8944 = b− 6 + 0,8944, tj. b-6 = 1, ( 0,8944) 10 .2 = 1,7888 = 1 + 0,7888 = b− 7 + 0,7888, tj. b-7 = 1, ( 0,7888) 10 .2 = 1,5776 = 1 + 0,5776 = b− 8 + 0,5776, tj. b-8 = 1. Tedy ( 0,3421) 10 = ( 0, b− 1b− 2 b− 3b− 4 b− 5 b− 6 b− 7 b− 8 ) 2 = ( 0,01010111) 2 . Máme-li racionální číslo převést do číselné soustavy o základu s, rozdělíme je na část celou, kterou převedeme užitím metody dělení základem s, a část desetinnou, kterou převedeme metodou násobení základem s. Příklad. Číslo 638,375 v desítkové soustavě převedeme do dvojkové soustavy. Rozdělíme je na celou část 638 a desetinnou část 0,375. (a) Číslo 638 v desítkové soustavě převedeme užitím metody dělení základem s = 2 do dvojkové soustavy ( 638) 10 : 2 = ( 319) 10 , zbytek je b0 = 0, ( 319) 10 : 2 = (159) 10 , zbytek je b1 = 1, (159) 10 : 2 = ( 79) 10 , zbytek je b2 = 1, ( 79) 10 : 2 = ( 39) 10 , zbytek je b3 = 1, ( 39) 10 : 2 = (19) 10 , zbytek je b4 = 1, (19) 10 : 2 = ( 9) 10 , zbytek je b5 = 1, ( 9) 10 : 2 = ( 4) 10 , zbytek je b6 = 1, ( 4) 10 : 2 = ( 2) 10 , zbytek je b7 = 0, ( 2) 10 : 2 = (1) 10 , , zbytek je b8 = 0,
(1) 10 : 2 = ( 0) 10 , zbytek je b9 = 1. Tudíž ( 638) 10 = ( b9 b8 b7 b6 b5 b4 b3 b2 b1b0 ) 2 = (1001111110) 2 . (b) Desetinnou část 0,375 v desítkové soustavě převedeme do dvojkové soustavy metodou násobením základem s = 2 ( 0,375) 10 .2 = 0,75 = 0 + 0,75 = b− 1 + 0,75, tj. b-1 = 0, ( 0,75) 10 .2 = 1,5 = 1 + 0,5 = b− 2 + 0,5, tj. b-2 = 1, ( 0,5) 10 .2 = 1,0 = 1 + 0,0 = b− 3 + 0,0, tj. b-3 = 1. Tedy ( 0,375) 10 = ( 0, b− 1b− 2 b− 3 ) 2 = ( 0,011) 2 . (c) Nyní výsledky z částí (a) a (b) sloučíme. ( 638,375) 10 = ( 638) 10 + ( 0,375) 10 = (1001111110) 2 + ( 0,011) 2 = (1001111110,011) 2 . Tedy ( 638,375) 10 = (1001111110,011) 2 . Dvojková (binární) soustava a její reprezentace v počítači Datový typ označovaný jako byte je takové chápání obsahu jednoho bajtu, při kterém je nazírán jako osmice dvojkových cifer (osmiciferný zápis čísla v dvojkové soustavě) a tedy jako nezáporné celé číslo. Takových různých hodnot je 256, hodnotami datového typu byte jsou všechna čísla od 0 do 255 v desítkové soustavě. Byte: Obsah O O O I O O I Číslo bitu 7 6 5 4 3 2 1 V tabulce je jako datový typ byte zapsáno číslo (10010)2= (18)10
O 0
Datový typ označovaný jako word (také celé číslo bez znaménka) je takové chápání obsahu dvou po sobě jdoucích bytů, při kterém jsou nazírány jako šestnáctice dvojkových cifer (šestnácticiferný zápis čísla v dvojkové soustavě) a tedy jako nezáporné celé číslo. Takových různých hodnot je 65 536, proto hodnotami datového typu word jsou všechna čísla od 0 do 65 535 v desítkové soustavě. Graficky lze jednu hodnotu typu word znázornit např. takto: Celé číslo bez znaménka: Obsah I O O O O I O O O O O I O O O Číslo bitu 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 V tabulce je jako datový typ word zapsáno číslo (1000010000010001)2= (33809)10
I 0
Datový typ označovaný jako integer (také celé číslo se znaménkem) je takové chápání obsahu dvou po sobě jdoucích bytů, při kterém jsou nazírány jako patnáctice dvojkových cifer - bitů předcházených jedním bitem nazíraného jako znaménko (nula jako znaménko +, jednička jako znaménko -). Patnácticiferný zápis dvojkové hodnoty tvoří nezáporné celé číslo; takových různých hodnot je 32 768, proto hodnotami jsou všechna čísla od 0 do 32 767 . Hodnotami datového typu integer jsou všechna čísla od -32 768 do +32 767 v desítkové soustavě13. Graficky lze jednu hodnotu typu integer znázornit např. takto: Celé číslo se znaménkem: Obsah I O O O O I = Číslo bitu 15 14 13 12 11 10 znam. 13
O
O
O
O
O
I
O
O
O
I
9
8
7
6
5
4
3
2
1
0
Nejmenší hodnota by správně měla být -32 767. Při zobrazení doslova popsaném shora tomu tak skutečně je. Pak se ovšem nula v takové množině hodnot vyskytne jednou jako "kladná" nula, jednou jako "záporná" nula. Nula je ovšem nulou, ať má jakékoliv znaménko. Proto hardware počítačů (procesory Intel) umí šetřit, záporná čísla jakoby "o 1 posunou" a získají tak jednu další číselnou hodnotu navíc: právě onu hodnotu -32 768.
V tabulce je jako datový typ integer zapsáno číslo (-10000010001)2= (-1041)10
Datový typ označovaný jako long (také longint, dlouhé celé číslo se znaménkem) je takové chápání obsahu čtyř po sobě jdoucích bytů, při kterém jsou nazírány jako jedenatřicetice dvojkových cifer – bitů – předcházených jedním bitem znaménkovým (analogie typu integer). Hodnoty datového typu se pohybují od trochu méně než -2 miliardy až po trochy více než +2 miliardy. Přesně to je interval − 2147483648,+ 2147483647 . Šestnáctková (hexadecimální) soustava Šestnáctkovým či hexadecimálním14 zápisem čísla15 se rozumí zápis čísla v šestnáctkové číselné soustavě, která používá běžné číslice pro hodnoty 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 a „číslice“ A, B, C, D, E, F pro hodnoty 10, 11, 12, 13, 14, 15. Čísla v tomto zápisu se obvykle označují písmenem H připojeným k číslu v dolním indexu, např. ( 3F8) H , což je číslo, které v běžné desítkové soustavě zapíšeme jako 1016, protože ( 3F 8) H = ( 3F 8) 16 = 3.16 2 + 15.161 + 8.16 0 = 768 + 240 + 6 = (1016) 10 . Hexadecimální zápis čísla se často používá v oblasti kolem počítačů, protože základ této soustavy, číslo 16, je rovno 24, což znamená, že jedna hexadecimální číslice reprezentuje právě 4 bity (jeden nibble). Takže např. všechny hodnoty uložitelné do jednoho bajtu lze vyjádřit právě dvěma šestnáctkovými číslicemi ( 00) H až ( FF ) H , tj. od 0 do 255 v desítkové soustavě. Z podobných důvodů se v některých případech používá také osmičkový či oktalový zápis, tzn. zápis v soustavě o základu 8 = 2³. Příklad. Číslo 1278 v desítkové soustavě vyjádříme ve šestnáctkové soustavě metodou dělení základem s = 16, tj. (1278) 10 : 16 = ( 79) 10 , zbytek je b0 = (14)10 = (E)16, ( 79) 10 : 16 = ( 4) 10 , zbytek je b1 = (15)10 = (F)16, ( 4) 10 : 16 = ( 0) 10 , zbytek je b2 = 4. Tudíž (1278) 10 = ( b2 b1b0 ) 16 = ( 4 FE ) 16 = ( 4 FE ) H . Příklad. Číslo 0,9921875 v desítkové soustavě vyjádříme ve šestnáctkové soustavě metodou násobení základem s = 16, tj. ( 0,9921875) 10 .16 = 15,875 = 15 + 0,875 = b− 1 + 0875, tj. b-1 = (15)10 = (F)16, ( 0,875) 10 .16 = 14,00 = 14 + 0,00 = b− 2 + 0,00, tj. b-2 = (14)10 = (E)16. Tudíž ( 0,9921875) 10 = ( 0, b− 1b− 2 ) 16 = ( 0, FE ) 16 = ( 0, FE ) H . Protože mocniny šestnáctky jsou poměrně velká čísla je výhodná převodní tabulka. Příklad. Číslo 1278,9921875 v desítkové soustavě vyjádříme ve šestnáctkové soustavě tak, že použijeme výsledky dvou předcházejících příkladů, tj. (1278,9921875) 10 = (1278) 10 + ( 0,9921875) 10 = ( 4 FE ) 16 + ( 0, FE ) 16 = ( 4 FE, FE ) 16 = ( 4 FE , FE ) H .
14
Slovo hexadecimální pochází z řeckého slova έξι (hexi) znamenajícího „šest“, a latinského slova decem, které znamená „deset“. 15 V žargonu je zkracován na hex zápis.
Pro převod čísel v rozsahu 0 – 255 v desítkové soustavě (hodnoty uložitelné do jednoho bajtu) lze použít tuto tabulku pro převod do šestnáctkové soustavy (dec uvádí čísla v desítkové soustavě a hex čísla v šestnáctkové soustavě)
1.2 Vyjádření racionálních čísel v semilogaritmickém tvaru Ukládání reálných čísel16 je založeno na vyjádření čísla a semilogaritmickém tvaru17, tj. číslo a zapíšeme ve tvaru a = m.z e , kde a je ukládané číslo, m je mantisa čísla a a e je exponent čísla a při základu z (základ určuje také v jaké číselné soustavě je vyjádřena mantisa i exponent), exponent je celé číslo. Základ z je dán, většinou je z = 2, mantisa musí splňovat 1 ,1 . Pokud základ z = 2, pak mantisa v absolutní hodnotě musí být podmínku m ∈ z v intervalu 0,5;1) , tzn. v tomto případě musí mantisa ve dvojkové soustavě vždy začínat (kromě znaménka) 0,1… Pokud základ z = 10, pak mantisa v absolutní hodnotě musí být v intervalu 0,1;1) , tzn. v tomto případě musí mantisa ve desítkové soustavě vždy začínat (kromě znaménka 0,m-1…, kde m-1 je 1, 2, 3, 4, 5, 6, 7, 8 nebo 9. Příklad. Vezměme jako příklad teplotu 0o Kelvina, tj. absolutní nulu. Tato teplota má v stupních Celsia hodnotu -273,16o, což je běžný číselný zápis, na který jsme si zvykli z každodenního života i
16
Protože ukládáme v počítači pouze konečný rozvoj reálného čísla, ukládáme pouze část racionálních čísel. U čísel s nekonečným rozvojem se uloží pouze počet cifer odpovídající maximálnímu počtu cifer mantisy. 17 Také se toto vyjádření nazývá zápis čísla s pohyblivou desetinnou čárkou (z angl. floating point numbers – doslovný překlad plovoucí desetinná tečka).
ze školní docházky. Pokud bychom chtěli toto číslo zapsat v semilogaritmickém tvaru, lze to vyjádřit takto a = − 273,16 = 0,27316.10 3 , tj. základ z = 10, mantisa m = 0,27316 a exponent18 e = 3. Reprezentace racionálních čísel v semilogaritmickém tvaru v počítači Jde o složitější datový typ, který má vyjadřovat desetinné číslo. Je to takové chápání obsahu několika po sobě jdoucích bytů, při kterém jsou byty nazírány jako tři skupiny bitů. První skupinou je první bit chápaný jako znaménko celého čísla. Druhou skupinou je několik bitů chápaných jako celé číslo se znaménkem, které vyjadřuje exponent e. Třetí skupinou je několik bitů chápaných jako mantisa m. Graficky lze jednu hodnotu typu znázornit na příkladu dvoubytového desetinného čísla např.
Označuje-li e hodnotu exponentu a m hodnotu mantisy (včetně myšlené části 0,1), pak hodnota desetinného čísla je rovna a = m.2e , přičemž číslo a je kladné, je-li první bit zleva (bit č. 15) 0, a je záporné, je-li první bit zleva1, exponent e je kladný, je-li druhý bit zleva (bit č. 14) 0, a je záporný, je-li druhý bit zleva 1. Datový typ označovaný jako single (také krátké desetinné číslo nebo číslo v jednoduché přesnosti) je takové chápání obsahu čtyř po sobě jdoucích bytů (tj. 32 bitů), při kterém je 31. bit považovaný za znaménko čísla, bity 30.–23. za exponent a bity 22.–0. za mantisu. Přesnost zobrazení je 7 až 8 platných cifer, číslo s největší absolutní hodnotou je přibližně 3,4 . 1038, číslo s nejmenší absolutní hodnotou ještě různé od nuly je přibližně 1,4 . 10-45. Datový typ označovaný jako double (také double precision, long real nebo dlouhé desetinné číslo, číslo ve dvojnásobné přesnosti) je takové chápání obsahu osmi po sobě jdoucích bytů (tj. 64 bitů), při kterém je 63. bit považovaný za znaménko čísla, bity 62.–52. za exponent (62. bit je znaménko exponentu) a bity 51.–0. za mantisu. Přesnost zobrazení je 15 až 16 platných cifer, číslo s největší absolutní hodnotou je přibližně 1,8 . 10308, číslo s nejmenší absolutní hodnotou ještě různé od nuly je přibližně 4,9 . 10-324. Aritmetické operace s čísly v semilogaritmickém tvaru Při sčítání a odčítání dvou čísel v semilogaritmickém tvaru převedeme mantisy tak, aby obě čísla měla exponent stejný, který odpovídá číslu s větším exponentem. Při násobení se násobí mantisy a sčítají exponenty. Při dělení se dělí mantisy a odčítají exponenty. Uvedeme několik příkladů, ve kterých pro jednoduchost předpokládáme základ z = 10 a mantisu uvedeme pouze na pět desetinných míst. Tj. uvažujeme čísla taková, že a = m.ze, kde m = 0,m-1 m-2 m-3 m-4 m-5, kde m-1= 1, 2, 3, 4, 5, 6, 7, 8 nebo 9. Příklad. Uvažujme čísla a = 12321 a b = 0,12321 a určíme jejich součet a rozdíl. Obě čísla vyjádříme v semilogaritmickém tvaru, tj. a = 12321 = 0,12321 . 105 a b = 0,12321 = 0,12321 . 100. Abychom čísla mohli sčítat a odčítat, musíme číslo b převést tak, aby exponent byl 5, tzn. b = 0,12321 . 100 = 0,0000012321 . 105, potom a + b = 0,12321 . 105 + 0,0000012321 . 105 = (0,12321 + 0,0000012321) . 105 = 18
Nebo také exponenciální část čísla a.
= 0,1232112321 . 105 = 0,12321 . 105, zde jsme výslednou mantisu uvedli právě na pět desetinných míst, tudíž a + b = a, tzn. chyba ve výpočtu je 0,0000012321 . 105 = 0,12321; a – b = 0,12321 . 105 – 0,0000012321 . 105 = (0,12321 – 0,0000012321) . 105 = = 0,1232087679 . 105 = 0,12320 . 105, i zde jsme výslednou mantisu uvedli právě na pět desetinných míst, tudíž chyba ve výpočtu je 0,0000087679 . 105 = 0,87879. Příklad. Uvažujme čísla a = 12321 a b = 0,12321 a určíme jejich součin a podíl. Obě čísla vyjádříme v semilogaritmickém tvaru, tj. a = 12321 = 0,12321 . 105 a b = 0,12321 = 0,12321 . 100. Potom a . b = 0,12321 . 105 . 0,12321 . 100 = (0,12321)2 . 105 = 0,0151807041 . 105 = = 0,151807041 . 104 = 0,15180 . 104, zde jsme výslednou mantisu uvedli právě na pět desetinných míst, tj. chyba ve výpočtu je 0,000007041 . 104 = 0,07041; 0,12321.10 5 a :b = = 1.10 5 = 0,1.10 6 , v této situaci je chyba 0. 0 0,12321.10 Příklad. Mějme čísla a = 123,45, b = 5,6789 a c = 0,009. Spočteme (a + b) + c a a + (b + c). Všechna tři čísla vyjádříme v semilogaritmickém tvaru, tj. a = 0,12345 . 103, b = 0,56789 . 101 a c = 0,80000 . 10-2. Nejprve určíme součet a + b. Číslo b vyjádříme s exponentem 3, tj. b = 0,0056789 . 103, potom a + b = 0,12345.10 3 + 0,0056789.10 3 = ( 0,12345 + 0,0056789).10 3 = = 0,1291289.10 3 = 0,12912.10 3. Pro určení součtu (a + b) + c musíme číslo c vyjádřit s exponentem 3, tj. c = 0,000008 . 103, potom ( a + b ) + c = 0,12912.10 3 + 0,000008.10 3 = 0,129128.10 3 = 0,12912.10 3 = 129,12. Nejprve určíme součet b + c. Číslo c vyjádříme s exponentem 1, tj. c = 0,00080 . 101, potom b + c = 0,56789.101 + 0,00080.101 = ( 0,56789 + 0,00080 ).101 = 0,56869.101. Pro určení součtu a + (b + c) musíme číslo b + c vyjádřit s exponentem 3, tj. b + c = 0,056869 . 103, potom a + ( b + c ) = 0,12345.10 3 + 0,0056869.10 3 = 0,1291369.10 3 = 0,12913.10 3 = 129,13. Tyto dva výsledky se liší o 0,01. Výhody a nevýhody vyjádření čísel v semilogaritmické tvaru Výhodou semilogaritmického vyjádření čísel je zejména jeho vysoká flexibilita. Tato reprezentace totiž umožňuje zápis čísel jednoduchým způsobem bez ohledu na jejich absolutní hodnotu. Zápis velmi malého čísla je na počet použitých číslic stejně náročný jako zápis velmi velkého čísla. Tuto flexibilitu umožňuje právě použití exponentu, který vyjadřuje řád čísla, zatímco mantisa uvádí jenom pozici v rámci tohoto řádu. „Malé“ číslo bude mít např. velmi malý exponent (příp. záporný), zatímco „velké“ bude mít hodnotu exponentu velkou. Jako příklad si vezměme čísla 2000000 a 0,000000002. Jde o čísla, která se v absolutní hodnotách od sebe významně liší. Použijeme-li vyjádření v semilogaritmickém tvaru dostáváme 2000000 = 0,2 . 107 a 0,000002 = 0,2 . 10-7, mantisa je stejná, rozdíl je pouze v exponentu. Tato vlastnost odstraňuje nedostatky čísel s pevnou desetinnou čárkou a zápis s pohyblivou desetinnou čárkou je jednoznačně výhodnější pro použití ve vnitřní počítačové reprezentaci racionálních čísel. Při použití semilogaritmického vyjádření čísel jsou čísla zatížena zaokrouhlovací chybou: (a) při vkládání údajů do počítače (tam jsme schopni tuto chybu vyčíslit a identifikovat),
(b) při provádění aritmetických operací (zde je obtížné je sledovat a vyčíslit). Pokud chceme zmenšit tuto zaokrouhlovací chybu, musíme ukládat více cifer mantisy, tzn. vyhradit ukládanému číslu místo 4B například prostor 8B (typ proměnných double). Zaokrouhlovací chyby vznikající při provádění aritmetických operací se liší podle typu aritmetických operací a typy ukládaných čísel. Při ukládání celých čísel a operací sčítání, odčítání a násobení, je výsledek zase celočíselný, potom pokud výsledek je v rozsahu ukládaného typu, pak se spočte a uloží přesně. U operace dělení může být výsledek být neceločíselný a pak pro něj platí, že může při ukládání vzniknout zaokrouhlovací chyba v případě, že mantisa obsahuje více cifer než je možné uložit. Při operacích s čísly vyjádřenými v semilogaritmickém tvaru jsou zaokrouhlovací chyby zpravidla: (a) při sčítání a odčítání, pokud součet má rozsah mantisy větší než maximální rozsah mantisy, toho dosáhneme zejména v případě, že exponenty obou čísel se liší o více než počet cifer mantisy, jestliže například sečítáme číslo 12345 a číslo 0,12345 a chceme-li výsledek uložit v pohyblivé čárce s kapacitou mantisy 5 cifer, pak výsledek je 12345 a je zřejmé, že druhé číslo se vůbec nepřičetlo; (b) při násobení se násobí mantisy a sčítají exponenty, při násobení mantis může dojít k navýšení platných cifer až dvojnásobně, proto při ukládání mantisy zřejmě dojde ke ztrátě platných cifer mantisy, při sčítání exponentu nedojde k chybě pokud výsledek nepřekročí maximální hodnoty exponentu; (c) při dělení se dělí mantisy a odčítají exponenty, dělením mantis může dojít k navýšení platných cifer mantisy o teoreticky neomezený počet, uložením mantisy opět může dojít ke zkreslení výsledku, odečítání exponentů (tedy celých čísel) je bez chyby, pokud nedojde k překročení maximálního počtu cifer exponentu výsledku. Při výpočtech na počítači dochází tedy k zaokrouhlovacím chybám a pokud těchto výpočtů provádíme velký počet, mohou se tyto zaokrouhlovací chyby kumulovat a pak dojít k znehodnocení celkového výsledku. Omezení vlivu zaokrouhlovacích chyb na výsledek se dosáhne zvýšením rozsahu mantisy pro uložení výsledku (typ ukládání double), případně úpravou algoritmu výpočtu. Cvičení (1) Vyjádřete číslo a, které je v desítkové soustavě, ve dvojkové, osmičkové i šestnáctkové soustavě, jestliže (a) a = 3036; (b) a = 2500; (c) a = 0,75; (d) a = 0,8125; (e) a = 3036,75; (f) a = 3036,8125; (g) a = 2500,75; (h) a = 2500,8125. Výsledky cvičení (1) (a) a = (3036)10 = (101111011100)2 = (5734)8 = (ACB)16 = (ACB)H ; (b) a = (2500)10 = (100111000100)2 = (4704)8 = (9B4)16 = (9B4)H ; (c) a = (0,75)10 = (0,11)2 = (0,6)8 = (0,B)16 = (0,B)H ; (d) a = (0,8125)10 = (0,1101)2 = (0,64)8 = (0,C)16 = (0,C)H ; (e) a = (3036,75)10 = (101111011100,11)2 = (5734,6)8 = (ACB,B)16 = (ACB,B)H ; (f) a = (3036,8125)10 = (101111011100,1101)2 = (5734,64)8 = (ACB,C)16 = (ACB,C)H ; (g) a = (2500,75)10 = (100111000100,11)2 = (4704,6)8 = (9B4,B)16 = (9B4,B)H ; (g) a = (2500,8125)10 = (100111000100,1101)2 = (4704,64)8 = (9B4,C)16 = (9B4,C)H .
