ARITMETICKÉ
OPERACE

 

 

"Kolik číslic má číslo devět na devátou na devátou?", ptá se účastník internetovského matematického fóra (The Math Forum, Ask Dr. Math). Odpovídají odborníci (25. září 1997, Re: 9 ^ 9 ^ 9) a ... odpovídají špatně. Na mnohaciferná čísla nejsme zvyklí; neumíme si je představit; neumíme je efektivně používat. Jazyk Rexx umožňuje provádět výpočty s velikou přesností. Jediným omezením je obvykle rozsah operační paměti. V tomto příspěvku bych chtěl ukázat, jak neobvyklé možnosti jazyka mohou vést k neobvyklým úvahám nad úlohou, ve svém výsledku i k neobvyklým algoritmům a dokonce k překvapujícím výsledkům.

Zápis čísla

Chceme-li znát přesně dobu výpočtu fragmentu programu, můžeme využít vestavěnou funkci TIME. Program DUEL porovnává rychlost provedení dále popisovaných funkcí STANDARD a HIGMAN. Funkce TIME je v něm nejprve vyvolána jako podprogram s argumentem "R" - analogie stisknutí stopek při startu. Následující vyvolání (opět s argumentem "R") je pak analogií stisknutí stopek po proběhnutí cílem; volání funkce v tomto přirovnání vrací dobu běhu v sekundách.

/* DUEL */
numeric digits 1000; Chyba = ""
do until DATATYPE(N, "W") & N >= 0
  say Chyba || "Zadejte nezáporné celé číslo."
  parse pull N
  Chyba = "[" || N || "] eh? "
end
call TIME "R"; Vysledek1 = STANDARD(N); say TIME("R") "sec"
call TIME "R"; Vysledek2 =   HIGMAN(N); say TIME("R") "sec"
exit

Pomocí vestavěné funkce DATATYPE se v programu DUEL testuje, zda zadaná hodnota N je celé číslo ("W" z anglického whole number). Toto číslo musí být zároveň (operátorem konjunkce je symbol &) větší nebo rovno nule.

Podmínky splňuje např. hodnota 200 zapsaná jako 200 nebo 200.0 nebo 2E+2 (tj. 2 . 102 v exponenciální notaci mantisaEexponent) a to s libovolným počtem mezer na začátku a na konci. Voláním vestavěné funkce DATATYPE(řetězec, třída) je možné dále otestovat, zda řetězec je zápisem desítkového čísla (N - number), dvojkového čísla (B - binary), šestnáctkového čísla (X - heXadecimal) apod.

Cvičení 1

Napište program Stopky, který vám umožní změřit si, například, jak dlouho vydržíte bez dechu.

Počítá jako my

Kolik je (1/0!) + (1/1!) + (1/2!) + ... + (1/N!) pro N >= 0? Úloha souvisí s výpočtem základu přirozeného logaritmu, označovaného, na památku Leonarda Eulera, symbolem e. V řadě učebnic se můžeme setkat s doporučením, které popisuje funkce STANDARD (výpis 2).

/* STANDARD - vnitřní funkce */
STANDARD: procedure
Suma = 1; Clen = 1
do J = 1 to ARG(1)
  Clen = Clen / J; Suma = Suma + Clen
end
return Suma

V jazyce Rexx se aritmetické operace sečítání (operátor +), odčítání (-), násobení (*), dělení (/), celočíselné dělení (% - mnemotechnika: operátor dělení má vždy jen jeden znak) a zbytek po celočíselném dělení (//) provádějí v podstatě podle týchž pravidel, která používáme při výpočtu na papíře nebo na tabuli.
Požadovaná přesnost se zadává příkazem numeric digits. Pro libovolné číslo A a libovolné číslo B <> 0 platí: A + 0 = (A % B) * B + (A // B). Přičtení nuly (A + 0) zajistí, že oba výrazy budou vyčísleny se stejnou přesností.
Při výpočtu hodnoty výrazu 1/6 s přesností na 4 platné číslice určíme nejprve jednotlivé číslice podílu 0.16666 a pak výsledek zaokrouhlíme na 0.1667. Aby totéž provedl interpret jazyka, stačí zadat numeric digits 4; say 1/6.
Nikdo z nás by však při výpočtu výše uvedené řady nepostupoval jako funkce STANDARD, tj. neurčil by už hodnotu čtvrtého členu řady na tisíc platných číslic jako 0.166 ... 67. S využitím vestavěné funkce COPIES můžeme tuto hodnotu zapsat jako hodnotu výrazu 0.1 || COPIES(6, 998) || 7. Člověk řešící zadanou úlohu by postupně počítal hodnoty čitatele a jmenovatele částečných součtů řady a teprve na závěr by provedl jediné dělení s požadovanou přesností. Tento postup použil při výpočtu přibližné hodnoty čísla e Bryan Higman ve své knize Porovnávacia štúdia programovacích jazykov (Alfa Bratislava, 1973) a popisuje jej funkce HIGMAN. Na PC s procesorem IBM MMX 233 MHz, 32 MB RAM s demem Personal REXXu od Quercus Systems trvá, pro N = 100, provedení funkce STANDARD 0.38 sec a provedení funkce HIGMAN 0.06 sec.

/* HIGMAN - vnitřní funkce */
HIGMAN: procedure
Citatel = 1; Jmenovatel = 1
do J = 1 to ARG(1)
  Citatel = Citatel * J + 1
  Jmenovatel = Jmenovatel * J
end
return Citatel / Jmenovatel

Porovnání čísel

Relačními operátory jsou >, <, = a jejich kombinace. Obecně se operace porovnání zahájí úpravou hodnot operandů - odstraněním mezer na začátku a na konci. Nejsou-li oba operandy čísla, kratší z nich se doplní mezerami zprava a porovnají se znak po znaku. V případě čísel se operandy odečtou s přesností na D - F platných číslic, přesnost je definována příkazy numeric digits D (implicitně D = 9) a numeric fuzz F (implicitně F = 0). Hodnotou výrazů D a F musí být celá čísla, D > F >= 0. Je-li rozdíl operandů záporný, pak výsledkem operace s operátory <, <=, <> je pravda (v jazyce Rexx je pravda reprezentována znakem 1 a nepravda znakem 0); je-li nula, pak výsledkem operace s operátory >=, <=, = je pravda; je-li kladný, pak výsledkem operace s operátory >, >=, <> je pravda (TRUE). Přehledně to ukazuje následující tabulka.

Je-li rozdíl operandů pak výsledkem operace je
záporný <, <=, <> TRUE
nula >=, <=, = TRUE
kladný >, >=, <> TRUE

Porovnáme-li v programu DUEL hodnoty Vysledek1 a Vysledek2, například příkazem

say Vysledek1 = Vysledek2

zjistíme, že se nerovnají - zobrazí se nula. Protože hodnotou výrazu Vysledek1 - Vysledek2 je 0.00 ... 04, zobrazí se po provedení příkazů

numeric fuzz 1; say Vysledek1 = Vysledek2

hodnota jedna (pravda).

Jiné číselné soustavy

Díky vestavěným funkcím B2X (Binary to heXadecimal), D2X (Decimal to heXadecimal), X2B, X2D můžeme v jazyce Rexx provádět aritmetické operace i s dvojkovými nebo šestnáctkovými čísly. Například součet šestnáctkových čísel, které jsou uloženy v proměnných Hex1 a Hex2, je výsledkem výrazu

D2X(X2D(Hex1) + X2D(Hex2))

Dvojková čísla nejprve převedeme na čísla šestnáctková (funkcí B2X), sečteme už známým způsobem a teprve výsledek převedeme na dvojkové číslo (funkcí X2B). Součet binárních hodnot v proměnných Bin1 a Bin2 tedy určíme výrazem:

X2B(D2X(X2D(B2X(Bin1)) + X2D(B2X(Bin2))))

Chceme-li vynechat nuly na začátku zápisu binárního čísla, aby zápis dvojkového čísla začínal jedničkou, můžeme využít vestavěnou funkci STRIP. Volání funkce STRIP(řetězec, volba, znak), vrací hodnotu řetězce bez znaků znak na začátku i na konci (je-li volba rovna B; zkratka both); jen na začátku (je-li volba rovna L; zkratka leading); jen na konci (je-li volba rovna T; zkratka trailing).

Cvičení 2

Napište program, který by dokázal vyluštit šifru: Edgar Allan Poe (narozen MDCCCIX - zemřel MDCCCXLIX).

Operace umocnění

K aritmetickým operacím v jazyce Rexx patří také umocnění (operátor **) s celočíselným exponentem.

V manuálech je algoritmus výpočtu mocniny XZ podrobně popsán. Protože i Rexx je nejen jazykem pro komunikaci člověka s počítačem, ale také člověka s člověkem, místo popisu slovy použiji popis následujícím fragmentem programu. Omezuji se jen na případ Z >= 0. Pro záporná Z a X <> 0 bychom počítali hodnotu 1 / XABS(Z).

/* Popis algoritmu umocnění (X ** Z) */
Vysledek = 1
BinarZ = STRIP(X2B(D2X(Z)), "Leading", 0)
do J = LENGTH(BinarZ) to 1 by -1
  if SUBSTR(BinarZ, J, 1) then Vysledek = Vysledek * X
  X = X * X
end
say "X ** Z =" Vysledek

Algoritmus pochází ze starověké Indie. Indové měli zálibu ve velkých číslech od nepaměti. Používali zvláštní slova pro čísla až do sta miliard. Buddha (asi 563 - 483 př. n. l.) prý sám pokračoval ve tvoření těchto číslovek až do 1054.     

Dále uvedená funkce MOCNINA je překladem starobylého algoritmu z kapitoly 4.6.3 knihy D. E. Knutha The Art of Computer Programming (díl 2, Addison-Wesley 1969) do jazyka Rexx. Upraveným programem DUEL (X = 15; Z = 959; numeric digits 1128) můžete porovnat rychlost provedení příkazů Vysledek1 = X ** Z a Vysledek2 = MOCNINA(X, Z). Hodnoty Vysledek1, Vysledek2 jsou zcela shodné. Přitom v systému AS/400 trvalo provedení prvního příkazu téměř dvakrát déle než druhého!

/* MOCNINA - vnitřní funkce */
MOCNINA: procedure; X = ARG(1); Z = ARG(2)
Vysledek = 1
do forever
  if Z // 2 then Vysledek = Vysledek * X
  Z = Z % 2
  if Z = 0 then return Vysledek
  X = X * X
end

Tuto překvapující skutečnost jsem představil účastníkům elektronické konference o jazyku Rexx pomocí listserveru REXXLIST svým e-mailem z 16.1.1998. Z jejich reakcí vznikla následující unikátní tabulka. Mnohem zajímavější než samotný rozdíl rychlosti provedení operace ** a funkce MOCNINA je porovnání rychlosti stejného výpočtu v různých implementacích jazyka Rexx, v různých prostředích. Srovnejte si například rychlost interpretace s provedením přeloženého programu (REXX370 kompilátor versus interpret) nebo výkonnost sálového počítače současnosti (IBM/390) s výkonností PC nebo pracovní stanice.

Počítač Systém Rexx ** MOCNINA Díky za informaci
mainframe IBM CMS REXX370 compiler 0.0013 0.0017 Plungjan M.
mainframe IBM TSO REXX370 compiler 0.0013 0.0018 Plungjan M.
PC Windows NT 4.0 Object REXX 6.0 0.2100 0.2800 Stuurman J.
mainframe IBM CMS REXX370 interpret 0.2349 0.1694 Plungjan M.
mainframe IBM TSO REXX370 interpret 0.2884 0.1520 Plungjan M.
PC Pentium 166 OS/2 Warp 4 Classic Rexx 0.3700 0.2500 Kazimirchik V.
PC Pentium 90 Linux REXX/imc 0.4583 0.5062 Gurski A.F.
PC 486/33 OS/2 Warp 4 Object REXX 1.3000 1.8600 Vermo B.
Sun Sparc 2 Solaris 2.5.1 REXX/imc 1.6d 1.8500 2.1000 Collier I.
PC Windows NT 4.0 Regina rychlejší pomalejší Saxton J.M.

Číselní obři a trpaslíci

V praxi nepracujeme s čísly, která by obsahovala na začátku zápisu stovky nul. K vyjádření velkých čísel užíváme mocnin deseti a k vyjádření malých čísel mocnin deseti se záporným exponentem. Přibližnou hmotnost zeměkoule v kilogramech zapíšeme v exponenciální notaci 6E+24 a hmotnost vodíkového atomu v gramech 2E-24.

Předpokládejme provedení příkazu numeric digits D. Jestliže výsledkem aritmetického výrazu je velké číslo, které má před desetinnou tečkou více jak D číslic; nebo jestliže výsledkem je malé číslo, které má za desetinnou tečkou minimálně D + 1 nul a celkem má za desetinnou tečkou více než 2 * D číslic, pak interpret jazyka pro urychlení výpočtu a lepší využití paměti převede toto číslo do exponenciální notace automaticky.

Poznámka

Ian Collier (přečtěte si Exponential notation, with Ian Collier´s reply), implementátor jazyka v prostředí operačního systému SunOs a UNIX (REXX/imc), ukázal, že tato definice je shodná s definici uvedenou v manuálech jazyka Rexx. Mě osobně se zdá jednodušší a jasnější. Porozumíme jí i bez detailní znalosti termínu platná číslice.

Porovnejme hodnoty Vysledek1 = STANDARD(N) a Vysledek2 = HIGMAN(N). Rozdíl Vysledek1 - Vysledek2 je roven číslu 0.000 ... 04 s 999. nulami. V přehlednější formě (4E-999) bude vyjádřen buď pomocí vestavěné funkce FORMAT nebo provedením příkazů:

Rozdil = Vysledek1 - Vysledek2; D = 9
numeric digits D; say Rozdil + 0

Přičtení nuly (násobení jedničkou apod.) je nutné, aby se uplatnilo nové nastavení přesnosti příkazem numeric digits.

Cvičení 3

Jakou minimální a maximální hodnotu může mít proměnná D (viz výše uvedený řádek programu), aby se zobrazilo 4E-999?

Bernoulli...

Celočíselný exponent (v exponenciální notaci a v operaci umocnění) nesmí mít více číslic než určuje příkaz

numeric digits

maximálně však 9. V roce 1728 Daniel Bernoulli dokázal, že číslo e je rovno limitě posloupnosti (1 + 1/N)N, pro N jdoucímu k nekonečnu. Řádkem programu s maximální možnou hodnotou N:

/* BERNOULLI počítá e, 1. verze */
numeric digits 50; N = 999999999
say "e =" (1 + 1/N) ** N

se zobrazí e = 2.7182818270... Přesnější výsledek ale nedostaneme, protože pro větší N skončí provádění programu chybovým hlášením Invalid whole number. Využijeme-li však funkci MOCNINA, program:

/* BERNOULLI počítá e, 2. verze */
numeric digits 50; Z = 1E+40
X = 1 + 1 / Z; say "e =" MOCNINA(X, Z)

doběhne a zobrazí číslo e = 2.71828182845904523560287...

Cvičení 4

Epocha(č. 3, 1905): Pomocí pouhých tří číslic lze zapsat číslo tak ohromné, že si je ani nedovedeme představit. Číslo to .. jest devět na devátou na devátou. Počet číslic, jichž je třeba pro napsání tohoto čísla, je mezi 369 690 000 a 369 790 000. Kdybychom je chtěli napsat, a to tak, aby na délku 1 dm přišlo 20 číslic, povstala by tak řádka dlouhá skorem 1848.5 km (asi vzdálenost Lipsko - Helsinki). Kolik číslic je skutečně zapotřebí?

Cvičení 5

Počet všech černobílých fotografií o rozměru 10 x 15 cm, vytvořených z černých a bílých teček velikosti 0.1 x 0.1 mm (tečky nebudou rozeznatelné pouhým okem a fotografie tak budou dostatečně kvalitní) je

21500000

Při zápisu tohoto čísla by povstala řádka dlouhá skorem 2.3 km. Dobře, ale co bude na těch fotografiích?

Řešení cvičení:

Cvičení 1

/* STOPKY - program */
say "Enter = Start"; pull Enter
call TIME "R"; say "Teď! ..."
say "Enter = Stop"; pull Enter
say "Uběhlo:" TIME("R") "sec"

Cvičení 2

Funkce R2D (Roman to Decimal) dokáže rozluštit tuto záhadu. Pro zadaný řetězec MDCCCIX (nebo třeba mDccCIx) vrací 1809 a pro MDCCCXLIX vrací 1849.

/* R2D (Roman to Decimal) vnitřní funkce */
R2D: procedure
parse upper arg Roman .
RtoD.I = 1; RtoD.V = 5; RtoD.X = 10; RtoD.L = 50;
RtoD.C = 100; RtoD.D = 500; RtoD.M = 1000
Decimal = 0; Rdigit = LEFT(Roman, 1)
Ddigit = RtoD.Rdigit
do J = 2 to LENGTH(Roman)
  Rdigit = SUBSTR(Roman, J, 1); Next = RtoD.Rdigit
  if Next > Ddigit then Decimal = Decimal - Ddigit
    else Decimal = Decimal + Ddigit
  Ddigit = Next
end
return Decimal + Ddigit

Cvičení 3

Hledané číslo D musí splňovat podmínku 2 * D + 1 <= 999. A protože z hodnoty proměnné Rozdil chceme vidět jen poslední platnou číslici, je jeho minimální hodnota 1 a maximální 499.

Cvičení 4

say 9 ** (9 ** 9) zobrazí 4.28124773...E+369693099 (celkem tedy 369693100 číslic). Nesmí však být předtím proveden příkaz numeric digits D, kde D < 9.

Cvičení 5

Eduard Fuchs odpovídá ve skriptech Teorie množin (UJEP Brno 1974) takto:


Budou na nich portréty všech lidí, kteří již dávno zemřeli nebo se narodí někdy v budoucnosti, jejich fotografie ve všech úsecích jejich života; budou zde všechna díla vědecká i umělecká v překladech do všech jazyků; logaritmické tabulky i fotografie, které teprve v budoucnu odešlou vesmírné sondy, partitury všech symfonií, které teprve budou napsány a stavby, které již dávno neexistují atd. atd. Většina těchto fotografií pak bude pouhý "šum", nepředstavující nic nám známého.

Poznámky a poděkování

V tomto článku byly použity moje maily z Archive of REXXLIST (Surprise for REXXperts 98/01/16, Exponential notation 98/10/05, How many digits has 9**(9**9) 98/10/20, 98/10/23)

Dále pak literatura:

M. F. Cowlishaw: The REXX Language - A Practical Approach to Programming

Prentice-Hall, inc., Engelwood Cliffs, New Jersey 1985

REXX/400 Reference
SC24-5664-00, IBM Corp. 1994

Helps from Personal REXX for Windows(tm)
Version 3.50, Quercus Systems

Rád bych poděkoval Gerardu Schildbergerovi, který opravil řadu chyb v tomto článku.


Kam dál ... hlavní str. english

od 1. ledna 2000, naposledy změněno 13. dubna 2018
Copyright © 2000-2018 Vladimír Zábrodský, RNDr.
 
mail