*ísla v po*íta*i

Report
Čísla v počítači
Přednáška z předmětu Počítače I
Dana Nejedlová
Katedra informatiky EF TUL
1
Celá čísla
• Jejich jiný název je čísla s pevnou řádovou čárkou (fixedpoint numbers).
• Mají pevný maximální počet míst před i za desetinnou
čárkou.
– Když je tento maximální počet míst dostatečně nízký, je
nejvýhodnější čísla v počítači ukládat jako celá čísla.
– Číslo v desítkové soustavě se vynásobí konstantou rovnou 10 na
maximální počet desetinných míst.
– Například pro maximálně 4 desetinná místa
• 1,23 se uloží jako 12300.
• 0,456 se uloží jako 4560.
• Pro zobrazení čísla použijeme konstantu 104.
– Dělíme uložené číslo 10000, tedy
– umístíme desetinnou čárku pevný počet míst od konce uloženého čísla.
• Aritmetické operace lze provádět s takto uloženými čísly
bez využití informace o maximálním počtu desetinných
míst.
– Takže se dál budeme bavit jen o celých číslech.
2
Reprezentace kladných celých čísel
• Uchovávají se v určitém počtu bajtů.
– 1 bajt (byte) má 8 bitů.
• Číslo se převede do dvojkové (binární) soustavy a z levé
strany se doplní nulami.
– 11 v desítkové soustavě je 1011 binárně.
– V 8 bitech se uloží jako 0000 1011.
• Převod čísla c do binární soustavy
– Využijeme vzorec c = 2 ∙ d + z, kde
• d je výsledek celočíselného dělení (kolikrát se 2 vejde celé do c),
• z je zbytek po celočíselném dělení.
–
–
–
–
–
11 = 2 ∙ 5 + 1 – binárně 1011 = 10 ∙ 101 + 1
5 = 2 ∙ 2 + 1 – binárně 101 = 10 ∙ 10 + 1
2 = 2 ∙ 1 + 0 – binárně
10 = 10 ∙ 1 + 0
1 = 2 ∙ 0 + 1 – binárně
1 = 10 ∙ 0 + 1
1110 = 10112
• Převod zpět: 1110 = 1∙23 + 0∙22 + 1∙21 + 1∙20 = 8+2+1
3
Sčítání
•
•
•
•
Procesor má pro jeho provedení obvod.
11 = 0000 1011
7 = 0000 0111
18 = 0001 0010
• 11 = 0000 1011
• 24 = 0001 1000
• 35 = 0010 0011
4
•
•
•
•
•
Odčítání
Má v matematice jiný algoritmus než sčítání.
11 = 0000 1011
–7 = – 0000 0111
4 = 0000 0100
Procesor by pro odčítání dle algoritmu shodného s
matematickým musel mít jiný obvod.
• Efektivnější je ale využít i pro odčítání sčítací obvod.
– Je to možné?
– Ano, pokud budeme záporná čísla správně reprezentovat.
• Jak má v počítači vypadat záporné číslo?
– Může se od kladného odlišovat tím, že by mělo nejvyšší bit
roven 1 místo 0.
• Potom by se ale pro odčítání nemohl použít stejný algoritmus jako pro
sčítání.
– Záporná čísla lze reprezentovat tak, aby odčítání A – B bylo v
počítači realizováno jako A + (reprezentace záporného B).
• Výsledky budou zase buďto kladná čísla nebo reprezentace záporných 5
čísel.
Reprezentace záporných celých čísel
• Nejefektivnější vzhledem k algoritmizaci je
takzvaný dvojkový doplněk (two's
complement).
• Jeho teoretickým základem je modulární
aritmetika, kde se čísla v řadě periodicky
opakují.
• V následující řadě se cyklicky opakují poslední
3 bity po 8 hodnotách.
6
Binární čísla a cyklická řada
0000
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
-4
0101
5
-3
0110
6
-2
0111
7
-1
1000
0
0
1001
1
1
1010
2
2
1011
3
3
1100
4
-4
1101
5
-3
• Souvislá řada binárních čísel
• Každému binárnímu číslu
přiřadíme dekadickou hodnotu
jeho nejnižších 3 míst.
• Každému binárnímu číslu
přiřadíme záporné číslo, pokud je
jeho 3. nejnižší bit roven 1, tak,
aby vznikla souvislá řada od
nejnižšího čísla (-4) k nejvyššímu
číslu (3).
7
Binární čísla a cyklická řada
0000
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
-4
0101
5
-3
0110
6
-2
0111
7
-1
1000
0
0
1001
1
1
1010
2
2
1011
3
3
1100
4
-4
1101
5
-3
• Budeme počítat v cyklické aritmetice s 8 možnými
hodnotami 0 až 7 nebo -4 až 3.
• Bude to tedy aritmetika modulo 23.
• Stejný výpočet uvedeme nejdřív v periodické řadě
nezáporných čísel a potom v něm nahradíme všechny
hodnoty hodnotami na stejném řádku v řadě
znaménkových čísel.
• 2+4=6
• 2 – 4 = –2
• 2 + 7 = 1 (Ne 9, protože to je mimo náš rozsah.)
• 2–1=1
• 6 + 7 = 5 (Ne 13, protože to je mimo náš rozsah.)
• –2 – 1 = –3
• Pokud byla čísla v rozsahu, tak výsledky byly správné.
• Máme tedy systém, kde odčítání realizujeme
sčítáním. V tomto systému se dá i násobit.
• Sčítají se nebo násobí binární vyjádření čísel.
• Periodicita je vyjádřena ignorováním 1. bitu (neboli 4.
nejnižšího bitu).
8
• Zbývá dořešit převod kladného čísla na záporné.
Převod na dvojkový doplněk čísla
0000
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
-4
0101
5
-3
0110
6
-2
0111
7
-1
1000
0
0
1001
1
1
1010
2
2
1011
3
3
1100
4
-4
1101
5
-3
• U všech bitů kladného čísla
změníme (přehodíme) hodnotu a
k výsledku přičteme 1.
• V následujících příkladech
budeme počítat s 3 nejnižšími
bity.
• 5 = 101 → 010 + 1 = 011 = 3.
• 4 = 100 → 011 + 1 = 100 = –4.
• 3 = 011 → 100 + 1 = 101 = –3.
• 1 = 001 → 110 + 1 = 111 = –1.
• 0 = 000 → 111 + 1 = 000 = 0.
9
Dvojkový doplněk v počítači
•
•
•
•
•
•
•
•
•
8 bitové celé číslo –11
1111 0101 = dvojkový doplněk čísla 11
+ 0000 1011 = číslo 11
1 0000 0000 = 28
16 bitové celé číslo –11
1111 1111 1111 0101 = dvojkový doplněk 11
+ 0000 0000 0000 1011 = číslo 11
1 0000 0000 0000 0000 = 216
Záporné číslo je uloženo jako
– 2 na počet bitů – kladné číslo.
• Dvojkový doplněk čísla c v n bitech = 2n – c.
10
Výpočty s dvojkovým doplňkem
• Na příkladech s 8 bitovými čísly
• 0001 1000 = 24
• + 1111 0101 = –11 neboli dvojkový doplněk 11
• 1 0000 1101 = 13 + 28, 28 není součástí výsledku
• 0000 1011 = 11
• + 1110 1000 = –24 neboli dvojkový doplněk čísla 24
• 0 1111 0011 = –13 neboli dvojkový doplněk čísla 13
• 1111 0101 = –11 neboli dvojkový doplněk čísla 11
• + 1110 1000 = –24 neboli dvojkový doplněk čísla 24
• 1 1101 1101 = –35 neboli dvojkový doplněk čísla 35 + 28, 28
není součástí výsledku.
• Takže vše můžeme počítat v 8 bitech a bity, které se do nich
při součtech nevejdou, můžeme zahodit.
11
Detekce chyb při výpočtech
• Je založena na tom, že čísla ve dvojkovém doplňku mají nejvyšší bit
roven 1. Podle něj lze chybu detekovat.
• Chyba může vzniknout jen při součtu 2 čísel se stejným znaménkem.
• Přetečení (overflow)
•
0110 0100 = 100
• + 0011 0010 = 50
• 0 1001 0110 = 150
– Pokud je výsledek interpretován neznaménkově, je výpočet správně.
– Pokud je výsledek interpretován znaménkově, vyjde záporné číslo,
dvojkový doplněk čísla 106, protože 8. bit je roven 1.
– Součet dvou kladných čísel vyjde záporně.
– 150 + 106 = 256 = 28 = modulo tohoto sčítání.
• Podtečení (underflow)
•
1001 1100 = –100
• + 1100 1110 = – 50
• 1 0110 1010 = 28 + 106, 28 není součástí výsledku.
– Součet dvou záporných čísel vyjde kladně.
– –150 – 106 = –256 = –28.
12
Rozsah dvojkového doplňku v 8 bitech
•
•
•
•
•
Maximální číslo 127 = 27 – 1 = 0111 1111
1
1=
20 = 0000 0001
0
0 = 20 – 1 = 0000 0000
–1
–1 = 28 – 1 = 1111 1111
Minimální číslo –128 =
27 = 1000 0000
• Čísla ve více bitech jsou tomu analogická.
13
Co je třeba umět do testu
• Převést konkrétní celé číslo na jeho dvojkový
doplněk.
• Jaké chyby vznikají při výpočtech s celými
čísly?
14
Reálná čísla
• Jejich jiný název je čísla s pohyblivou řádovou čárkou (floating-point
numbers).
• Potřebujeme jediným datovým typem reprezentovat čísla s velkým
rozsahem počtu míst před nebo za desetinnou čárkou.
– čísla blížící se nekonečnu, neboli s velkou vzdáleností od nuly na reálné
ose
– čísla blížící se nule, neboli s velkým záporným řádem
• Datový typ
– Je určitý formát, ve kterém je uložena informace v počítači.
– Určuje
• přípustné hodnoty informace a
• přípustné operace, které se s informací mohou provádět.
– Celá čísla v určitém počtu bitů a s určitým rozsahem (znaménková,
neznaménková) jsou určitým datovým typem neboli formátem.
– Reálná čísla mají také své formáty.
– Je záležitostí dohody mezi výrobci technologií neboli standardem.
– Nejrozšířenější standard pro reprezentaci reálných čísel ve výpočetních
systémech je IEEE 754.
15
Teoretické základy standardu IEEE 754
• Semilogaritmický tvar (vědecká notace) čísla
– Počítače nebo kalkulačky tak zobrazují příliš malá nebo
velká čísla.
• Zápis čísla se skládá ze
–
–
–
–
znaménka,
mantisy (significand),
exponentu a
základu umocňování.
• 23,125 = 2,3125 ∙ 101 = 2312,5 ∙ 10–2 = 0,23125 ∙ 102 …
– Číslo může být zapsáno mnoha způsoby.
• Může být různé umístění čárky a různý základ exponentu.
• Tyto různé možnosti mohou být standardizovány.
• IEEE 754
– Před čárkou je 1 místo.
• normalizace
– Základ exponentu je 2.
16
Mantisa (significand) v IEEE 754
• Když je základ exponentu 2, tak se mantisa skládá z řetězce nul a
jedniček a vždy začíná na 1. Proto se vynechá, aby se ušetřil 1 bit.
– leading bit convention, implicit bit convention, hidden bit convention
• Převedeme číslo 3,8125 do binární soustavy:
–
–
–
–
–
Bude se převádět zvlášť část čísla před čárkou a za čárkou.
3=2∙1+1
1=2∙0+1
Před čárkou je 11.
Zlomková část binárního čísla se řídí vzorcem
• c = k–1 ∙ 2–1 + k–2 ∙ 2–2 + k–3 ∙ 2–3 + k–4 ∙ 2–4 + ...
• k = {0, 1}
• Násobení číslem 2 způsobí, že před desetinnou čárku se dostane
koeficient čísla 2–1.
–
–
–
–
–
–
0,8125 ∙ 2 = 1,625
0,625 ∙ 2 = 1,25
0,25 ∙ 2 = 0,5
0,5
∙2=1
Za čárkou je 1101.
3,8125 = 11,1101 = 1,11101 ∙ 21. Zelené hodnoty se uloží.
17
Znaménko a exponent v IEEE 754
• Znaménko je uloženo v prvním bitu čísla.
– 1 znamená mínus, 0 znamená plus.
• Exponent je celé číslo, které může být kladné nebo
záporné.
– Neukládá se jako dvojkový doplněk, aby šla jednodušeji
porovnávat jeho velikost.
– K jeho skutečné hodnotě se připočte kladné celé číslo dané
standardem IEEE 754 zvané posunutí (bias) a potom se
zakóduje jako kladné celé číslo.
• Exponenty v přípustném rozsahu tak jsou vždy kladné.
• Vyšší exponent je vyšší neznaménkové číslo než nižší exponent.
– Maximální exponent určuje rozsah čísla neboli jeho
maximální vzdálenost od nuly.
• Komponenty formátu IEEE 754 jsou v pořadí znaménko,
exponent, mantisa, což umožňuje porovnávání čísel se
stejným znaménkem pomocí obvodů pro celočíselnou
aritmetiku.
18
IEEE 754 a aritmetické operace
• Jsou výpočetně náročnější a proto by se měly
reálné datové typy využívat jen, když jsou
opravdu nutné.
• Vznikají při nich zaokrouhlovací chyby.
– Řádově nejnižší číslice výsledku výpočtu nejsou
správné.
– Nemůžeme testovat rovnost reálných čísel.
• Místo (a = b) se musí testovat stylem abs(a – b) < 0,00001.
• Počet bitů vyhrazený pro exponent je konečný,
takže může vzniknout i přetečení.
• Podtečení znamená, že číslo se blíží nule.
• Čísla, která mají v jiné třeba desítkové soustavě
konečný počet desetinných míst, nemusí mít
konečný počet míst ve dvojkové soustavě.
19
IEEE 754 a zaokrouhlovací chyby
•
•
•
•
•
•
•
•
•
•
•
Převedeme číslo 0,1 v desítkové soustavě do dvojkové soustavy:
0,1 ∙ 2 = 0,2
0,2 ∙ 2 = 0,4
0,4 ∙ 2 = 0,8
0,8 ∙ 2 = 1,6
0,6 ∙ 2 = 1,2
0,2 ∙ 2 = 0,4 Odtud se to opakuje.
0,4 ∙ 2 = 0,8
0,110 = 0,0 0011 0011 …2
Když číslo opakovaně násobíme 2 a ztratí se z něj desetinná část, tak je číslo ve
dvojkové soustavě vyjádřitelné bez chyb.
Násobení nebo dělení
– Vynásobí se mantisy a sečtou nebo odečtou se exponenty.
•
Sčítání a odčítání
–
–
–
–
–
–
–
–
Dochází při něm k větším zaokrouhlovacím chybám než u násobení.
Číslo s nižším exponentem se musí denormalizovat.
1,2345 ∙ 105 + 6,78 ∙ 10–2 =
= 1,234500000 ∙ 105
+ 0,000000678 ∙ 105
= 1,234500678 ∙ 105
Výsledek se nemusí vejít do mantisy, takže se uříznou řádově nejnižší číslice.
Může se stát, že číslice řádově nižšího sčítance se uříznou všechny.
20
Rozdíl mezi sousedními hodnotami
reálných čísel
• V matematice je nekonečně malý.
• Formát IEEE 754 má fixní počet bitů pro mantisu.
• Máme například mantisu, kam se vejde jen 5 číslic:
– 1,2345 ∙ 105 má sousední vyšší číslo 1,2346 ∙ 105.
• Rozdíl je 0,0001 ∙ 105.
– 1,2345 ∙ 10–5 má sousední vyšší číslo 1,2346 ∙ 10–5.
• Rozdíl je 0,0001 ∙ 10–5.
– Na rozdíl od celočíselných datových typů je rozdíl mezi
sousedními reálnými čísly různý.
• Reálná čísla by se neměla používat jako řídící proměnná cyklu nebo
index prvku pole.
• Čím větší je počet bitů vyhrazený pro mantisu, tím blíže
se může číslo uložené v počítači přiblížit teoretické
matematické hodnotě čísla.
– Velikost mantisy určuje přesnost čísla.
21
Co je třeba umět do testu
• Jaké chyby vznikají při výpočtech s reálnými
čísly?
• Jaká část formátu IEEE 754 určuje
– rozsah čísla a
– přesnost čísla?
• Rozpoznat, zda je dané reálné číslo v desítkové
soustavě reprezentovatelné v počítači ve
formátu IEEE 754 bez ztráty přesnosti.
• Jak se liší rozdíl mezi sousedními možnými
hodnotami čísla ve formátu IEEE 754 od čísla
ve formátu dvojkového doplňku?
22
Znaky
• Znak (character) je počítačová reprezentace
jednotlivého písmena tak, aby byla možná
práce s textem, například vyhledávání.
• Abeceda znaků, znaková sada (character set),
mapuje množinu znaků na množinu celých
čísel.
– Čísla jsou kódy znaků.
• Stejný znak může být počítačem zobrazen
různou velikostí, tvarem, fontem (například
tučně, kurzívou…).
• Na světě je spousta abeced a spousta
mapování znaků na čísla, neboli kódování.
23
Kód ASCII
• American Standard Code for Information Interchange
• Vznikl v 60. letech 20. století.
• Byl původně určen pro dálnopis a tiskárny.
– Proto jsou jeho součástí řídící znaky s kódem 0-31.
• Je 7 bitový.
– Mapuje 128 znaků.
• interpunkce
• číslice (0-9)
• znaky anglické abecedy
– velké (uppercase letters) A-Z
– malé (lowercase letters) a-z
• Je to nejstarší kód rozšířený v informačních a
komunikačních technologiích.
– Omezení se na ASCII zaručí co nejmenší komplikace s
kompatibilitou při sdílení dat na různých platformách.
• jména souborů, adresy WWW stránek, adresáře SW projektů…
• Při pojmenovávání souborů je třeba myslet i na pravidla operačních
systémů.
– Nepoužívat mezeru, otazník, hvězdičku, lomítko, dvojtečku …
24
Národní abecedy
• Dle vzoru ASCII vznikaly kódové tabulky národních
abeced, které se někdy také nesprávně nazývaly
ASCII.
• Původně se využívalo jen 7 bitů, takže národní
abecedy musely přemapovat některé často
užívané znaky původního amerického ASCII.
– Vzniklo tak mnoho nekompatibilních kódování.
• Kompatibilní řešení je to, kdy původní ASCII
zůstane zachováno a přidají se k němu znaky
národních abeced.
– Tabulka národní abecedy by měla 8 bitů.
• K původní ASCII tabulce s prvním bitem z 8 rovným nule se
přidá dalších 128 kódů pro národní znaky s prvním bitem z 8
25
rovným jedné.
Tvůrci standardů pro kódování znaků
• Národní organizace
– například ANSI
• Mezinárodní organizace
– například ISO
• Soukromé firmy
– například IBM, Microsoft, Apple
– proprietární standardy závislé na platformě (víceméně
na určitém operačním systému)
• Pro stejnou národní abecedu tak může existovat
více nekompatibilních kódování.
– Nekompatibilita se projeví, když mezi sebou
komunikují různé systémy pracující s odlišným
kódováním.
• Například e-mail je zpracován různými servery a různými
klientskými programy.
26
Problémy národních kódování
• Moderní software
– Vyrábí se pro mnoho národních prostředí.
• lokalizace
• Šíření informace přes Internet
– Když na Internetu začínala služba WWW, byly nutné
různé varianty stránek pro různá kódování nebo se
požadovaná stránka před jejím zobrazením
překódovala nějakým programem.
– V současnosti je kód stránky součástí jejích metadat
pro internetový prohlížeč.
• Elektronické dokumenty odkudkoliv by mělo být
možné číst kdekoliv.
– Software pro jejich zobrazení by měl umět všechna
kódování.
27
Unicode
• Standard pro kódování všech národních abeced v jediné
společné tabulce prvně publikován roku 1991
• Jeho tvůrce je společnost Unicode Consortium sdružující
nejvýznamnější světové firmy z oblasti informačních
technologií.
• Poskytuje prostor pro více než milión kódů.
• Má několik variant.
– UTF-8 má proměnlivou délku kódu.
• V současnosti je to nejpoužívanější kódování pro psaní WWW stránek.
• ASCII znaky jsou kódovány pomocí 8 bitů s nulou na začátku.
– zpětná kompatibilita s ASCII
• Ostatní znaky jsou kódovány pomocí 2 až 4 bajtů.
– UTF-32 má fixní délku kódu.
• Kóduje každý znak pomocí 4 bajtů.
• Reprezentace znaků není efektivní z hlediska potřebné paměti.
• Znaky jsou indexovatelné.
– Díky fixní délce kódu je n-tý znak přímo přístupný pomocí n-tého indexu.
– Přístup k n-tému znaku při kódování s proměnlivou délkou musí být sekvenční,
28
je tudíž výpočetně náročnější.
Řetězce znaků
• vektory (jednorozměrná pole) znaků
reprezentující text
• Mají 2 nejčastější způsoby realizace.
– řetězce ukončené nulou (null-terminated strings)
• Mohou být libovolně dlouhé (omezeny jen dostupnou
pamětí).
– řetězce s předponou určující délku (length-prefixed
strings).
• Délka je omezená maximálním číslem, které se vejde do
fixního počtu bitů určeného pro předponu.
• Řetězec může být binární.
– Binární data mohou kdekoliv obsahovat libovolné hodnoty bajtů.
– Na rozdíl od binárních dat textová data jsou tvořena jen znaky
textu. Žádný znak textu nemá kód rovný nule.
• Je-li předpona jiného (zpravidla delšího) datového typu než
znak (element textu), je řetězec tvořen jako objekt.
29
Co je třeba umět do testu
• Jaké problémy jsou spojeny s používáním
různých kódovacích tabulek pro různé abecedy
národních znaků?
– Jak jsou tyto problémy v současnosti řešeny?
• Jaké kódování má variabilní délku kódu?
• Jak jsou v počítači reprezentovány řetězce?
30

similar documents