Tom´aˇs Holan, dlouha.txt, Verse: 19. u ´nora 2006.
Dlouh´ aˇ c´ısla Uˇz zn´ ame datov´e typy pro representaci cel´ ych ˇc´ısel i typy pro representaci desetinn´ ych ˇc´ısel. Co ale dˇelat, kdyˇz n´am ˇz´adn´ y z dostupn´ ych datov´ ych typ˚ u nevyhovuje? Moˇzn´ a potˇrebujeme pˇresnˇe poˇc´ıtat cel´a ˇc´ısla o velikosti pˇresahuj´ıc´ı rozsah typ˚ u integer i longint, jindy zase m˚ uˇzeme potˇrebovat desetinn´a ˇc´ısla s vˇetˇs´ım poˇctem platn´ ych ˇc´ıslic, neˇz nab´ızej´ı real, double i extended. V takov´em pˇr´ıpadˇe nezb´ yv´a, neˇz si vytvoˇrit vlastn´ı representaci ˇc´ısel a naprogramovat vlastn´ı prov´ adˇen´ı aritmetick´ ych operac´ı na naˇsem nov´em typu. Pˇri volbˇe zp˚ usobu represenatce bychom si mˇeli poloˇzit a zodpovˇedˇet n´asleduj´ıc´ı ot´ azky: – budeme reprezentovat pouze nez´ aporn´ a nebo i z´ aporn´ a ˇc´ısla? – pokud z´ aporn´ a, budeme je ukl´adat se znam´ enkem nebo v doplˇ nkov´ em k´ odu? – budeme reprezentovat ˇc´ısla cel´ a nebo i desetinn´ a? – pokud desetinn´ a, s pevnou nebo pohyblivou ˇ r´ adovou ˇ c´ arkou? – na kolik m´ıst budeme ˇc´ıslo ukl´adat? – pouˇzijeme pro ukl´ ad´ an´ı pole nebo spojov´ y seznam? – jakou ˇ c´ ast ˇ c´ısla bude obsahovat jeden prvek naˇs´ı datov´e reprezentace? Pokud m´ ame ˇreˇsit konkr´etn´ı u ´lohu, potˇrebujeme jeˇstˇe rozhodnout, jak´e operace budeme na naˇsem datov´em typu potˇrebovat — a ty potom naprogramovat. Ukaˇzme si vˇse na konkr´etn´ım pˇr´ıkladu.
1
Pˇ r´ıklad
Zad´ an´ı Napiˇste program, kter´ y spoˇcte a vytiskne hodnotu Eulerovy konstanty e s pˇresnost´ı na 1000 desetinn´ ych m´ıst. Pro v´ ypoˇcet pouˇzijte vzorce e=
∞ X
1/i!
i=0
Zaˇcnˇeme reprezentac´ı dat a kladen´ım a zodpov´ıd´an´ım ot´azek. Pˇrijdeme na to, ˇze n´ am staˇc´ı ˇc´ısla nez´ aporn´ a, desetinn´ a, s pevnou ˇ r´ adovou ˇ c´ arkou. U ot´ azky poˇctu m´ıst se zaraz´ıme. Je zˇrejm´e, ˇze chceme-li zn´at v´ ysledek s pˇresnost´ı na 1000 desetinn´ ych m´ıst, nebude staˇcit prov´adˇet v´ ypoˇcty tak´e s touto pˇresnost´ı, protoˇze kdybychom kaˇzd´ y prvek sˇc´ıtan´e ˇrady oˇr´ızli za 1000-t´ ym desetinn´ ym m´ıstem, souˇcet vˇsech takto oˇr´ıznut´ ych hodnot by mohl zp˚ usobit, ˇze hodnota na nˇekolika posledn´ıch desetinn´ ych m´ıstech vyjde jin´a, neˇz by mˇela vyj´ıt. Budeme tedy muset poˇc´ıtat o nˇeco pˇresnˇeji. O kolik, to se pokus´ıme odhadnout (v praxi to ovˇsem pokaˇzd´e odhadnout nedok´aˇzeme a tedy se budeme muset
spokojit s t´ım, ˇze zkus´ıme prov´est v´ ypoˇcet pro r˚ uzn´ y poˇcet m´ıst nav´ıc a uvid´ıme, kam aˇz sahaj´ı zmˇeny plynouc´ı ze zmˇeny poˇctu m´ıst). V tomto pˇr´ıpadˇe se ale o odhad m˚ uˇzeme pokusit. Kdybychom vˇedˇeli, kolik ˇclen˚ u ˇrady budeme sˇc´ıtat, mohli bychom poˇc´ıtat s nejhorˇs´ım pˇr´ıpadem, ˇze totiˇz uˇr´ıznut´a ˇc´ast obsahuje sam´e dev´ıtky a vyˇslo by n´ am, ˇze pro jeden ˇclen souˇctu bychom potˇrebovali jedno m´ısto nav´ıc, pro deset ˇclen˚ u dvˇe m´ısta, pro sto tˇri m´ısta. . . neboli ˇze poˇcet m´ıst, o kter´a mus´ıme zv´ yˇsit pˇresnost odpov´ıd´ a logaritmu poˇctu prvk˚ u sˇc´ıtan´e ˇrady, zvˇetˇsen´emu o jedniˇcku. Hrub´ y odhad poˇctu prvk˚ u m˚ uˇzeme potom prov´est takto: – – – – – – – – – –
staˇc´ı sˇc´ıtat jen ty prvky, kter´e v naˇs´ı reprezentaci nebudou rovny nule i-t´ y prvek ˇrady bude i-kr´at menˇs´ı neˇz jeho pˇredch˚ udce pro i alespoˇ n 10 to znamen´a, ˇze dalˇs´ı prvek bude alespoˇ n desetkr´at menˇs´ı pro i alespoˇ n 100 to znamen´a, ˇze dalˇs´ı prvek bude alespoˇ n stokr´at menˇs´ı prvky pro i=10..99 tedy posunou nenulov´e hodnoty ve sˇc´ıtanci alespoˇ n o 90*1 ˇc´ıslic doprava (vydˇel´ı nejm´enˇe 1090 ) prvky pro i=100..999 tedy posunou nenulov´e hodnoty ve sˇc´ıtanci alespoˇ no 900*2 ˇc´ıslic doprava (vydˇel´ı nejm´enˇe 101800 ) 1000-t´ y prvek tedy nebude vˇetˇs´ı neˇz 1/101890 1000-t´ y prvek tedy bude jistˇe na prvn´ıch 1890 desetinn´ ych m´ıstech obsahovat nuly 1000-t´ y prvek n´ as tedy z hlediska souˇctu ˇrady urˇcitˇe nebude zaj´ımat urˇcitˇe tedy nebudeme sˇc´ıtat v´ıce neˇz 1000 prvk˚ u
Proto n´ am staˇc´ı, kdyˇz pro v´ ypoˇcet budeme poˇc´ıtat a pˇresnost´ı na 1004 desetinn´ ych m´ıst. ˇ ısla budeme representovat jako ˇc´ısla s pevnou ˇr´adovou ˇc´arkou (vˇsechna C´ budou m´ıt 1004 desetinn´ ych m´ıst), pˇred desetinnou ˇc´arkou n´am staˇc´ı jedin´e m´ısto (podv´ ad´ıme, protoˇze v´ıme, ˇze cel´ y souˇcet nekoneˇcn´e ˇrady nepˇrekroˇc´ı ˇc´ıslo e, jehoˇz hodnotu 2, 7 . . . zn´ ame z matematiky. Jeˇstˇe se rozhodneme, ˇze ˇc´ıslo budeme ukl´adat v poli a ˇze kaˇzd´ y prvek bude obsahovat pouze jedinou des´ıtkovou ˇc´ıslici. Z hlediska pamˇeti i (strojov´eho) ˇcasu to nen´ı pˇr´ıliˇs v´ yhodn´e, jeden prvek pole zab´ır´a nejm´enˇe jeden byte a do jednoho byte bychom mohli um´ıstit hodnoty 0..99, pˇr´ıpadnˇe do prvk˚ u typu word um´ıstit hodnoty 0..9999 nebo do typu longint hodnoty 0..999999999 (jeˇstˇe o jednu des´ıtkovou ˇc´ıslici v´ıce neˇz dvojn´asobek). Protoˇze n´am ale ted’ z´aleˇz´ı v´ıce na pˇrehlednosti a pochopitelnosti programu, budeme v prvc´ıch ukl´adat jednotliv´e ˇc´ıslice. Deklarace typu tedy bude vypadat takto: const MAX = 1000+4; type TCislo = array[0..MAX] of 0..9;
Nult´ y prvek bude obsahovat hodnotu odpov´ıdaj´ıc´ı poˇctu cel´ ych jednotek, od prvn´ıho prvku zaˇc´ınaj´ı desetinn´a m´ısta. Intervalov´ y typ 0..9 m´ısto prost´eho byte pouˇzijeme proto, abychom se dozvˇedˇeli o pˇr´ıpadn´ ych chyb´ ach pˇreteˇcen´ı. Dalˇs´ı u ´kol, kter´ y n´ as ˇcek´a, je v´ ybˇer a implementace aritmetick´ ych operac´ı. Na prvn´ı pohled se m˚ uˇze zd´at, ˇze budeme potˇrebovat operace jako sˇc´ıt´an´ı, n´ asoben´ı, dˇelen´ı nebo alespoˇ n pˇrevr´acenou hodnotu. . . Kdyˇz odol´ ame pokuˇsen´ı zaˇc´ıt hned programovat, uˇsetˇr´ıme si hodnˇe pr´ace, protoˇze pˇrijdeme na to, ˇze kaˇzd´ y dalˇs´ı ˇclen ˇrady m˚ uˇzeme spoˇc´ıtat z pˇredchoz´ıho ˇclenu a to vydˇelen´ım hodnotou i. A dˇelit dlouh´e ˇc´ıslo hodnotou typu integer je snazˇs´ı (pro v´ ypoˇcet i pro program´atora) neˇz dˇelen´ı dlouh´ ym ˇc´ıslem. Koneˇcn´ y seznam operac´ı, kter´e potˇrebujeme prov´adˇet potom bude: – dosazen´ı jedniˇcky – souˇcet – vydˇelen´ı hodnotou typu integer A mohli bychom pˇridat jeˇstˇe test, jestli je dlouh´e ˇc´ıslo rovno nule, zat´ım, neˇz se zase zamysl´ıme. Ted’ uˇz m˚ uˇzeme napsat hlavn´ı program: var
Soucet, Prvek: TCislo; i: integer; begin Dosad1( Prvek ); Soucet := Prvek; { ano, i dlouh´ a c ˇ´ ısla m˚ uˇ zeme dosazovat } { zaˇ cneme od souˇ ctu rovneho 1/0! a od i=1 } i := 1; while ...JeNula( Prvek )... do begin Pricti( Prvek, Soucet ); i := i+1; Vydel( Prvek, i ) end; { uz jen tisk: } write( Soucet[0],’.’ ); for i:=1 to 1000 do write( Soucet[i] ) end. Sch´ az´ı n´ am procedury Dosad1, Pricti, Vydel a oteˇckovan´a funkce JeNula urˇcuj´ıc´ı, zda je hodnota dlouh´eho ˇc´ısla rovna nule. Zaˇcnˇeme procedurami Dosad1 a Pricti:
procedure Dosad1( var Kam: TCislo ); var i: integer begin Kam[0] := 1; for i:=1 to MAX do Kam[i] := 0 end; procedure Pricti( var Co, Kam: TCislo ); { >Co< pˇ red´ av´ ame tak´ e odkazem, kv˚ uli rychlosti } var i: integer; x, prenost: integer; begin prenos := 0; for i:=MAX downto 0 do begin x := Co[i] + Kam[i] + prenos; Kam[i] := x mod 10; prenos := x div 10 end; { tady by mohla b´ yt kontrola, zda opravdu prenos=0 } end; Za koncem cyklu v proceduˇre Pricti bychom mohli kontrolovat, zda opravdu prenos obsahuje nulu. V t´eto u ´loze v´ıme, ˇze souˇcet pˇret´eci nem˚ uˇze, ale jistota. . . Urˇcen´ı ukl´ adan´e ˇcislice a pˇrenosu bychom mohli zapsat n´azornˇeji takto: x := Co[i] + Kam[i] + prenos; if x < 10 then begin Kam[i] := x; prenos := 0 end else begin Kam[i] := x-10 prenos := 1 end Varianta vyuˇz´ıvaj´ıc´ı mod a div je rychlejˇs´ı a kratˇs´ı, zvolte si sami. Nezkouˇsejte uˇsetˇrit pomocnou promˇennou x! Pokud jde o dˇelen´ı, jeˇstˇe jednou vyjadˇruji radost nad t´ım, ˇze n´am staˇc´ı dˇelit hodnotou typu integer a konkr´etnˇe (na tom z´aleˇz´ı!) hodnotou menˇs´ı neˇz 1000.
Pˇri dˇelen´ı budeme proch´ azet dˇelen´e ˇc´ıslo odpˇredu, postupnˇe si pomoc´ı Hornerova sch´ematu skl´ adat jeho hodnotu (a pozdˇeji aktu´aln´ı zbytek po dˇelen´ı) a to, ˇze v´ıme, ˇze budeme dˇelit hodnotou menˇs´ı neˇz 1000, n´am zajiˇst’uje, ˇze dˇelen´a hodnota bude menˇs´ı neˇz desetin´ asobek — a tedy se n´am tak´e vejde do typu integer. Algoritmus dˇelen´ı tedy bude takov´ y, ˇze budeme postupnˇe odleva proch´azet dˇelen´e dlouh´e ˇc´ıslo, v promˇenn´e zbytek si budeme poˇc´ıtat aktu´aln´ı zbytek po dˇelen´ı, v kaˇzd´em kroku ho vyn´asob´ıme deseti a pˇriˇcteme dalˇs´ı ˇc´ıslici (Hornerovo schema) a vydˇel´ıme dˇelitelem. Celoˇc´ıseln´ y pod´ıl (0..9) zap´ıˇseme m´ısto pr´avˇe pouˇzit´e ˇc´ıslice dˇelen´eho dlouh´eho ˇc´ısla, zbytek uloˇz´ıme do promˇenn´e zbytek a tak d´al: procedure Vydel( var Co: TCislo; Cim: integer ); var i: integer; zbytek: integer; begin zbytek := 0; for i:=0 to MAX do begin zbytek := 10*zbytek + Co[i]; Co[i] := zbytek div Cim; zbytek := zbytek mod Cim end end; Zb´ yv´ a n´ am uˇz jen test, zda je ˇc´ıslo (v hlavn´ım programu promˇenn´a Prvek) rovno nule. To by ˇslo snadno, ale. . . Pod´ıvejme se jeˇstˇe na proceduru Vydel. Jak bude postupovat v´ ypoˇcet prvk˚ u ˇrady, na zaˇc´ atku Prvku bude jistˇe pˇrib´ yvat nul. Upravme proceduru Vydel tak, aby nuly na zaˇc´ atku pˇreskoˇcila: procedure Vydel( var Co: TCislo; Cim: integer ); var i: integer; zbytek: integer; begin zbytek := 0; i := 0; while (i<=MAX) and (Co[i]=0) do Inc( i ); for i:=i to MAX do begin zbytek := 10*zbytek + Co[i]; Co[i] := zbytek div Cim; zbytek := zbytek mod Cim end end;
T´ım urˇcitˇe nic nezkaz´ıme, protoˇze kaˇzd´ y krok tohoto pˇridan´eho cyklu n´am uˇsetˇr´ı jeden krok cyklu poˇc´ıtaj´ıc´ıho n´asoben´ı deseti a dˇelen´ı a v´ ypoˇcet zbytku po dˇelen´ı. Pojd’me ale jeˇstˇe d´ al a uloˇzme si pozici prvn´ı nenulov´e ˇc´ıslice do zvl´aˇstn´ı promˇenn´e PNC (jako Prvn´ıNenulov´aCislice): ... i := 0; while (i<=MAX) and (Co[i]=0) do Inc( i ); PNC := i; for i:=PNC to MAX do ... end; A uˇz zb´ yv´ a si jen vˇsimnout, ˇze hodnota PNC se mezi jednotliv´ ymi vol´an´ımi procedury Vydel nikdy nem˚ uˇze zmenˇsovat, protoˇze vydˇelen´ım ˇc´ısla, kter´e m´a na zaˇc´ atku (PNC-1) nul urˇcitˇe dostaneme ˇc´ıslo, kter´e bude m´ıt poˇcet nul na zaˇc´ atku stejn´ y nebo vˇetˇs´ı. Promˇenn´ a PNC tedy m˚ uˇze b´ yt glob´aln´ı a prvn´ı nenulovou ˇc´ıslici staˇc´ı hledat aˇz od n´ı: procedure Vydel( var Co: TCislo; Cim: integer ); var i: integer; zbytek: integer; begin zbytek := 0; i := PNC; while (i<=MAX) and (Co[i]=0) do Inc( i ); PNC := i; for i:=PNC to MAX do begin zbytek := 10*zbytek + Co[i]; Co[i] := zbytek div Cim; zbytek := zbytek mod Cim end end; T´ım (promˇenn´ a PNC mus´ı na zaˇc´atku dostat hodnotu 0!) nejen uspoˇr´ıme proch´ azen´ı nulov´ ych ˇc´ıslic pˇri kaˇzd´em dˇelen´ı, ale tak´e z´ısk´ame bezplatnˇe pˇr´ıznak toho, zda Prvek jeˇstˇe neobsahuje sam´e nuly! Hlavn´ı program tedy bude vypadat takto: var
Soucet, Prvek: TCislo; i: integer;
PNC: integer; begin Dosad1( Prvek ); Soucet := Prvek; { ano, i dlouh´ a c ˇ´ ısla m˚ uˇ zeme dosazovat } { zaˇ cneme od souˇ ctu rovneho 1/0! a od i=1 } PNC := 0; i := 1; while PNC <= MAX do begin Pricti( Prvek, Soucet ); i := i+1; Vydel( Prvek, i ) end; { uz jen tisk: } write( Soucet[0],’.’ ); for i:=1 to 1000 do write( Soucet[i] ) end.
2
Dalˇ s´ı. . .
Operace odˇc´ıt´ an´ı prob´ıh´ a podobnˇe jako operace sˇc´ıt´an´ı, nezapomeˇ nte ale na to, ˇze pˇri odeˇc´ıt´ an´ı dvou ˇc´ısel se stejn´ ym znam´enkem (jinak se odeˇc´ıt´an´ı mˇen´ı ve sˇc´ıt´ an´ı) mus´ıme vˇzdy nejprve porovnat absolutn´ı hodnoty obou ˇc´ısel a vˇzdy odeˇc´ıtat ˇc´ıslo menˇs´ı (v absolutn´ı hodnotˇe) od ˇc´ısla vˇetˇs´ıho (v absolutn´ı hodnotˇe). Za u ´vahu stoj´ı i pˇrev´est odeˇc´ıtan´e ˇc´ıslo na des´ıtkov´ y doplnˇek (vˇsechny ˇc´ıslice doplnit do dev´ıtky a nakonec pˇriˇc´ıst 1) a ten pˇriˇc´ıtat. Algoritmus n´ asoben´ı vˇsichni zn´ame. Dˇelen´ı dvou dlouh´ ych ˇc´ısel prob´ıh´a podobnˇe jako jsme vidˇeli pˇri dˇelen´ı hodnotou typu integer, jenom zbytek bude dlouh´e ˇc´ıslo a operace div a mod mus´ıme prov´ adˇet odhadem a/nebo postupn´ ym odeˇc´ıt´an´ım.
