Dokumentace k projektu pro předměty IZP a IUS
Iterační výpočty projekt č. 2
22. listopadu 2010
Autor:
Milan Seitler,
[email protected] Fakulta Informačních Technologií Vysoké Učení Technické v Brně
Obsah 1
Úvod ................................................................................................................................... 1
2
Analýza problému .............................................................................................................. 1 2. 1 Zadání problému .................................................................................................... 1 2. 2 Obecný logaritmus ................................................................................................. 1 2. 3 Hyperbolický tangens............................................................................................. 2 2. 4 Vážený aritmetický průměr .................................................................................... 2 2. 5 Vážený kvadratický průměr ................................................................................... 3
3
Návrh řešení problému ....................................................................................................... 3 3. 1 Obecný logaritmus ................................................................................................. 3 3. 1. 1 Rekurentní vztah ................................................................................................ 4 3. 2 Hyperbolický tangens............................................................................................. 4 3. 3 Vážený aritmetický a kvadratický průměr ............................................................ 5 3. 4 Počet platných číslic............................................................................................... 5
4
Specifikace testů................................................................................................................. 5
5
Popis řešení ........................................................................................................................ 7 5. 1 Ovládání programu................................................................................................. 7 5. 2 Datové typy ............................................................................................................ 8 5. 3 Vlastní realizace ..................................................................................................... 8
6
Závěr................................................................................................................................... 8
A
Metriky kódu ...................................................................................................................... 9
1
Úvod
Tento dokument obsahuje popis návrhu a implementace programu, který pomocí iteračních algoritmů zpracovává číselná data zadaná uživatelem a provádí matematické operace obecný logaritmus a hyperbolický tangens. Se stejnými daty počítá také vážený aritmetický průměr a vážený kvadratický průměr.
2
Analýza problému
2. 1
Zadání problému
Výsledný program musí být schopen provádět matematické operace hyperbolický tangens a obecný logaritmus. U obou operací určuje přesnost uživatel zadáním parametru sigdig. U obecného logaritmu uživatel navíc zadává také základ logaritmu. Druhým požadavkem je výpočet statistických funkcí – vážený aritmetický průměr a vážený kvadratický průměr. Uživatel zadává na standardní vstup posloupnost hodnot, které jsou v programu zpracovány a každé této hodnotě přísluší jedna hodnota z výstupní posloupnosti, která je vypisována na standardní výstup. U statistických funkcí je vstupní posloupnost interpretována jako dvojice hodnot a výstupní posloupnost je tedy poloviční délky vstupní posloupnosti. Program musí být schopen ověřit, zda zadané parametry a vstupní hodnoty vyhovují matematické definici daných operací a musí umět ošetřit výjimečné případy za použití hodnot INFINITY a NAN.
2. 2
Obecný logaritmus
Logaritmická funkce (v projektu jako logax) je funkcí inverzní k funkci exponenciální, jejím výsledkem (y) je číslo nazývané logaritmus, pro nějž platí vztahy:
y = log a x , a y = x
(1)
Prvním krokem při tvorbě vlastní funkce pro výpočet logaritmu je určení definičního oboru hodnot proměnné x a také základu logaritmu a.
Obrázek 1: Graf logaritmické funkce
1
Z obrázku 1 vyplývají následující omezení hodnot x a základu a:
a ∈ R + \ {1}, x ∈ R +
(2)
Dále je potřeba určit způsob, jakým se bude obecný logaritmus počítat. Vzhledem k vlastnostem obecných logaritmů jsem použil vzorec
log a x =
log x ln x = log a ln a
(3)
Výsledný logaritmus tedy vyjádřím jako podíl přirozeného logaritmu čísla x a přirozeného logaritmu čísla a. Přirozený logaritmus je takový logaritmus, ve kterém je jako základ použito tzv. Eulerovo číslo (2,71828 18284...).
2. 3
Hyperbolický tangens
Hyperbolický tangens je hyperbolická funkce, v projektu označená zkratkou tanh. Definičním oborem funkce tanh jsou všechna reálná čísla, oborem hodnot je interval (-1, 1).
Obrázek 2: Graf funkce hyperbolický tangens Hyperbolický tangens lze definovat vztahem
tanh x = 2. 4
sinh x cosh x
(4)
Vážený aritmetický průměr
Vážený aritmetický průměr se od aritmetického průměru odlišuje tím, že každá hodnota statistického souboru má přiřazenu odpovídající váhu. Výsledný vážený aritmetický průměr lze pak spočítat následovně:
x=
x1w1 + x2 w2 + x3 w3 + ... + xn wn w1 + w2 + w3 + ... + wn 2
(5)
kde x je hodnota ze statistického souboru a w je odpovídající váha této hodnoty. Pokud mají všechny váhy stejnou hodnotu, lze výsledný vážený průměr považovat za aritmetický průměr.
2. 5
Vážený kvadratický průměr
Pro vážený kvadratický průměr platí stejná pravidla jako pro vážený aritmetický průměr (viz. 2. 4), vzorec pro výpočet je následující:
x=
x12 w1 + x22 w2 + x32 w3 + ... + xn2 wn w1 + w2 + w3 + ... + wn
3
Návrh řešení problému
3. 1
Obecný logaritmus
(6)
Vzhledem k využití přirozeného logaritmu při výpočtu obecného logaritmu (viz. vzorec 3) bylo nutné sestavit vzorec pro výpočet přirozeného logaritmu. Vzhledem k zadání, ve kterém bylo zdůrazněno použití iteračních výpočtů, jsem se rozhodl použít Taylorovu řadu pro přirozený logaritmus:
x − 1 ( x − 1) 3 ( x − 1) 5 ln x = 2 + + + ... 3 5 x + 1 3 ( x + 1 ) 5 ( x + 1 )
(7)
Dle matematické definice lze v tomto vzorci použít hodnoty x > 0, v rámci optimalizace jsem se však rozhodl počítat pouze s hodnotami v intervalu <0.1, 2>, kde řada konverguje nejrychleji. Nepoužil jsem interval (0, 2>, neboť pro nízké hodnoty x (např. 0.000001) nebyl výpočet zcela přesný. Aby bylo možno tuto řadu použít pro všechna x, je nutné hodnoty, které do intervalu nenáleží, do intervalu převést. K tomuto účelu slouží vzorec
ln x = ln r + m × ln e
(8)
kde x je původní hodnota, která je dělena Eulerovým číslem (e), dokud výsledný podíl r nenáleží do intervalu <0.1, 2>. M je pak počet dělení. Vzhledem k definici
ln e = 1
(9)
pak lze vzorec 8 zjednodušit takto:
ln x = ln r + m
(10)
Tento vztah lze použít pouze pro hodnoty x > 2, pro 0 < x < 0.1 je operace dělení nahrazena násobením a ve vztahu je nutno změnit znaménko před m na -.
3
3. 1. 1 Rekurentní vztah Nekonečnou řadu ze vzorce 7 je potřeba převést na rekurentní vztah:
citatel y −1 × ( x − 1) 2 Yi = Yi −1 + 2 jmenovatel × ( x + 1) 2 × ( k + 2) y −1
(11)
citatel 0 = ( x − 1), jmenovatel 0 = ( x + 1), k = 1 Y0 = 2
3. 2
x −1 x +1
(12)
Hyperbolický tangens
Pro výpočet této funkce (vzorec 4) jsou potřeba dvě Taylorovy řady:
x3 x5 sinh x = x + + + ... 3! 5!
(13)
x2 x4 cosh x = 1 + + + ... 2! 4!
(14)
pro které jsem sestavil následující rekurentní vztahy:
sinh : Yi = Yi −1 +
citatel y −1 × x 2 jmenovatel y −1 × ( k × ( k − 1))
|k =k +2
(15)
Y0 = x, citatel 0 = x, jmenovatel 0 = 1, k = 1 cosh : Yi = Yi −1 +
citatel y −1 × x 2 jmenovatel y −1 × ( k × ( k − 1))
Y0 = 1, citatel 0 = 1, jmenovatel 0 = 1, k = 0
4
|k =k +2 (16)
3. 3
Vážený aritmetický a kvadratický průměr
Pro výpočet statistických funkcí je nezbytné průběžně ukládat hodnoty součtů ve jmenovateli a čitateli vzorce 5, resp. 6. Aktuální průměr se pak vypočítá vztahem
xi =
citatel i −1 + xi wi jmenovatel i −1 + wi
(17)
citatel 0 = 0, jmenovatel 0 = 0 pro vážený aritmetický průměr, jeho kvadratickému ekvivalentu náleží obdobný vzorec
xi =
citatel i −1 + xi2 wi jmenovatel i −1 + wi
(18)
citatel 0 = 0, jmenovatel 0 = 0 3. 4
Počet platných číslic
Výše uvedené iterační vztahy tvoří nekonečně dlouhou řadu, kde se k celkovému součtu přičítají jednotlivé členy, které se postupně zmenšují. Aby bylo možné tyto vztahy použít, je nutné stanovit určitou hodnotu posledního členu, který bude ve výpočtu použit. K určení této hodnoty jsem použil parametr sigdig a zároveň tak určuji také přesnost výsledku. Výpočetní cyklus před každým opakováním testuje, zda je již dosaženo požadované přesnosti a pokud ano, výpočet ukončí. Podmínka na začátku cyklu vypadá takto:
Yi − Yi−1 ≤ ε
ε = 0.1sigdig
4
(19)
Specifikace testů
Při testování jsem se zaměřil především na různé varianty chybných vstupních hodnot či parametrů. Test 1: Neplatná hodnota parametru sigdig (počet platných číslic) → Program vypíše chybové hlášení na stderr a ukončí se. -5 3a blabla
5
Test 2: Parametr a (základ logaritmu) nevyhovuje matematické definici → Program vypíše chybové hlášení na stderr a ukončí se. 1 -10 x8 Test 3: Neplatný znak na standardním vstupu → Program vypíše na standardní výstup hodnotu výsledku NAN, vypíše chybové hlášení na stderr a ukončí se. abc 3a !@ Test 4: Hodnoty logaritmu pro a > 1, 0 < a < 1 → správný výsledek. 4. a: --logax 10 5 2 → 4.3067655807e-01 3.4 → 7.6037442772e-01 15 → 1.6826061945e+00 4. b: --logax 10 0.5 6 → -2.5849625007e+00 1.302 → -3.8072944850e-01 100 → -6.6438561898e+00 Test 5: Hodnoty tanh pro x ∈ R → správný výsledek. -6.08 → -9.9998952855e-01 4.000068 → 9.9932939092e-01 42 → 1.0000000000e+00 Test 6: Posloupnost čísel a jejich odpovídající váhy u váženého aritmetického průměru → posloupnost průběžných výsledků. standardní vstup: 1 5 8 4 6 3 4 2 standardní výstup: 1.0000000000e+00 4.1111111111e+00 4.5833333333e+00 4.5000000000e+00
6
Test 7: Posloupnost čísel a jejich odpovídající váhy u váženého kvadratického průměru → posloupnost průběžných výsledků. standardní vstup: 1 5 8 4 6 3 4 2 standardní výstup: 1.0000000000e+00 5.3851648071e+00 5.5452682532e+00 5.3519021986e+00 Test 8: Speciální případy, konstanty ± INFINITY a NAN → správný výsledek. 8. a: --logax 10 5 inf → inf -inf → nan nan → nan 8. b: --logax 10 0.3 inf → -inf -inf → nan nan → nan 8. c: Speciální hodnoty základu logaritmu --logax 10 inf → 0 --logax 10 –inf → chybný vstup --logax 10 nan → nan 8. d: --tanh 10 inf → 1.0000000000e+00 -inf → -1.0000000000e+00 nan → nan
5
Popis řešení
Tato kapitola popisuje vlastní realizaci teoretických podkladů uvedených v kapitolách 2 a 3.
5. 1
Ovládání programu
Celá aplikace je ovládána prostřednictvím příkazového řádku (konzole), pro zobrazení nápovědy je nutno zadat parametr –h. Následuje seznam dalších možných parametrů: --logax sigdig a (obecný logaritmus o základu a s přesností na sigdig čísel) --tanh sigdig (hyperbolický tangens s přesností na sigdig čísel) --wam (vážený aritmetický průměr) 7
--wqm (vážený kvadratický průměr) Program očekává na standardním vstupu posloupnost vstupních hodnot, jejichž zpracované výsledky jsou vypisovány na standardní výstup, vstup i výstup lze směrovat z a do souboru, např: --logax 10 15 < "vstup.txt" > "vystup.txt"
5. 2
Datové typy
Vzhledem k zadání úlohy všechny funkce kromě main vracejí hodnotu typu double. Stejně tak je většina proměnných typu double. Několik proměnných typu unsigned int je použito při zpracovávání parametrů z příkazové řádky, případně při práci s iteračními výpočty. V programu jsem vytvořil strukturu s názvem stat_hodnoty, která slouží k uchování průběžných součtů ve statistických funkcích. Tato struktura obsahuje dvě položky typu double. Druhou použitou strukturou je struktura parametry, kterou tvoří dvě položky typu double, dvě položky typu unsigned int a jedna položka ukazatel na datový typ char.
5. 3
Vlastní realizace
Funkce main se dělí na dvě části. V první části jsou ve funkci nacti_parametry zpracovány parametry příkazové řádky, pokud některý z nich nevyhovuje požadované formě či rozsahu (viz. kapitola 4), program vypíše chybové hlášení na stderr a ukončí se. Druhou část funkce tvoří jeden cyklus, který zajišťuje načítání hodnot ze standardního vstupu a jejich předání do odpovídající funkce, která je dále zpracuje. Všechny výpočetní funkce vracejí hodnotu výsledku, který je pak na konci cyklu vypsán na standardní výstup. Funkce muj_logax a muj_tanh zpracovávají pouze jednu hodnotu, pro funkce wam a wqm je nutné ještě načíst druhou hodnotu (váhu). Uvnitř těchto funkcí probíhá kromě samotného výpočtu také ověření parametrů funkce (např. u funkce muj_logax jsou to parametry cislo, eps, a), přesněji kontrola rozsahu a definičního oboru. V případě, že uživatel zadá na standardním vstupu nepovolený znak nebo je některý z parametrů příkazové řádky chybný, funkce vypis_chybu vypíše odpovídající chybové hlášení a ukončí program.
6
Závěr
Program počítá operace hyperbolický tangens a obecný logaritmus a statistické funkce vážený aritmetický průměr a vážený kvadratický průměr. Veškeré výsledky mých funkcí jsem porovnával s výpočty knihovních funkcí, oba výsledky byly na vzhledem k požadované přesnosti stejné. Při analýze zadání bylo nutné pochopit princip jednotlivých matematických operací a stanovit jejich definiční obory a obory hodnot. Dalším důležitým krokem bylo zvolit nejlépe konvergující Taylorovu řadu a případně ji omezit na nějaký interval, ve kterém konverguje nejrychleji. Výsledná aplikace byla testována v operačních systémech MS Windows a GNU / Linux, v obou případech fungovala bez problémů a vypisovala odpovídající hodnoty.
8
POUŽITÉ ZDROJE [1] BARTSCH, H.-J.: Matematické vzorce. Praha: Mladá fronta, třetí vydání, 1996, 831 s., ISBN 80-204-0607-7. Grafy funkcí byly vytvořeny v programu Microsoft Math.
A
Metriky kódu
Počet souborů: 1 Počet funkcí: 12 (včetně funkce main) Počet řádků zdrojového kódu: 352 Velikost statických dat: 368B Velikost kódu programu: 5428B Velikost spustitelného souboru: 16079B (systém Linux, 64bitová architektura, překlad bez ladících informací)
9
