Dlouhá čísla - poznámky k úkolu

Rozvažujeme-li reprezentaci dlouhých čísel, je dobré se zamyslet nad několika otázkami. V našem případě odpovíme takto:

• Potřebujeme čísla nezáporná nebo i záporná? Jak ve které úloze. Většinou stačí nezáporná, ale doporučuji vám rozmyslet si to i pro záporná.
• Stačí nám čísla celá, nebo potřebujeme i desetinná? Stačí celá.
• Jak, resp. v jaké soustavě budeme číslo ukládat? Pro jednoduchost jsme se shodli, že většinou v desítkové (zápis v soustavě s nižším základem je delší na počet cifer - a zase soustavám s vyšším základem nestačí číselné cifry a nám se s ciframi hezky počítá). (Jen v úloze Dvojkové zápisy čísel se vám může hodit jiná soustava. ;))
• Na kolik míst budeme číslo ukládat? Pro každou úlohu si rozmyslete, kolik nejvýše cifer může mít vaše dlouhé číslo. Podle toho změňte konstantu MAX určující počet cifer.
• Použijeme pro ukládání pole nebo spojový seznam? Pole, neboť spojový seznam ještě neznáme (bere se až v letním semestru). ;) Ale i tak je to výhodnější, neboť pole zde bohatě stačí a o něco lépe se s ním pracuje.
• Jakou část čísla bude obsahovat jeden prvek naší datové reprezentace? Jednu cifru (v dané soustavě).

Nyní tedy víme, že budeme číslo reprezentovat v poli o velikosti MAX, kde typ prvků pole bude cifra 0..9. Dále nás ale zajímá několik dalších věcí:

• Na jaké pozice budeme ukládat jaké cifry?
  • Jedna možnost je ukládat čísla odpředu - tedy ta s nejvyšším řádem na první pozici. Jaké to má výhody? Načítání bude snadné. Přesně po cifrách nám bude stačit číslo ukládat do pole. Jaké to má nevýhody? Všechno ostatní. Musíme rozlišit, kde číslo končí (nestačí tam mít nuly, potřebujeme znát počet jeho cifer). Při sčítání školním algoritmem srovnáváme cifry pod sebe. To zde znamená, že bychom je museli vhodně posunout. Když k číslu něco přičteme - a zvýší se nám počet cifer, tak na to musíme nějak zareagovat (cifry posunout).
  • Rovnat stejně významné řády pod sebe. Tedy např. 10⁰ ukládat do pole s indexem 0, analogicky 10ⁱ do pole s indexem i.
• Jak budeme reprezentovat záporná čísla?
  • Znaménkovým bitem. Navíc si k číslu pamatovat boolean, zda je číslo kladné či ne. Jaké to má výhody? Je to podobné našemu uvažování i zápisu. Opět se to i hezky načítá. Jaké to má nevýhody? Téměř všechny ostatní. Realizace všech operací bude vyžadovat spoustu podmínek ošetřujících, zda pracujeme s čísly kladnými či zápornými apod. Ale pokud se Vám tato reprezentace zdá nejpochopitelnější, tak ji můžete v tomto úkolu použít.
  • Jedničkovým doplňkem. To znamená, že máme-li kladné číslo c v soustavě o základu z, tak záporné k němu vytvoříme tak, že invertujeme všechny cifry, tedy každou cifru odečteme od z. Díky tomu nespotřebujeme navíc žádnou paměť kromě našeho pole. Zkuste si rozmyslet, jak se pak pozná jednoznačně číslo kladné a jak záporné. A logicky by nám to nějak mělo zmenšit rozsah kladných čísel - o kolik a jak? Tato reprezentace není moc výhodná - např. má dvě nuly (jak číslo ze samých 0, tak číslo ze samých cifer z). Ale výhoda je, že již velmi podobná reprezentace je vhodná.
  • Dvojkový doplněk. Oproti jedničkovému doplňku akorát při tvorbě záporného čísla k číslu přičteme 1. Na první pohled se tím zbavíme dvou reprezentací čísla 0. Dále si můžete rozmyslet, jak ve dvojkovém doplňku budou vypadat operace sčítání, odčítání, násobení, apod. Především se zaměřte na odčítání (nápověda je, že nám budou stačit jen dvě operace - invertování (jakoby vynásobení -1) a sčítání - a nezajímá nás, které číslo je kladné či záporné. Více k tomuto bude na cvičení.
• Jak to všechno zapsat v Pascalu? Základem bude vytvoření vlastního typu TCislo pro naše dlouhé číslo (první písmeno T naznačuje, že se jedná o námi definovaný typ.)

      const MAX = 302;
      type  TCifry = array[0..MAX] of 0..9;
      type TCislo = record
  	cifry : TCifry;
  	delka : 0..MAX;
      end;
      

  Proč nejsou jednotlivá políčka pole TCifry typu integer nebo menší byte? Nepoužít integer je vhodné kvůli šetření s pamětí, ale jinak je výhodné, že máme takto zajištěnou kontrolu přetečení. Možná si říkáte - co je v tom za výhodu, že napíšu program, který bude padat na přetečení? Kupodivu je výhoda značná. Budete mít alespoň nápovědu, kde hledat problém. Že jste v nějaké operaci např. zapomněli použít operaci mod 10. Není totiž nic protivnějšího, než mít nefunkční program, o kterém netušíte, proč je nefunkční - a co hůř ani neznáte vstup, na kterém nefunguje... ;)

       procedure Nacti( var A : TCislo );

       function Secti( var A,B : TCislo ):TCislo;

Nakonec pár zajímavých odkazů:

• Reprezentace záporných binárních čísel - v obrázcích I.
• Reprezentace záporných binárních čísel - v obrázcích II.
• Reprezentace záporných binárních čísel - v obrázcích III.
• Reprezentace záporných binárních čísel - v obrázcích IV.
• Reprezentace čísel s desetinnou čárkou - v obrázcích I.
• Reprezentace čísel s desetinnou čárkou - v obrázcích II.
• Reprezentace čísel s desetinnou čárkou - v obrázcích III.
• Velmi užitečný text o dlouhých číslech od RNDr. Tomáše Holana.