VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ

ˇ V YSOKÉ U CENÍ T ECHNICKÉ V B RN Eˇ ˇ FAKULTA I NFORMA CNÍCH T ECHNOLOGIÍ

ˇ ˇ U ˚ IZP A IUS D OKUMENTACE K PROJEKTU 2 DO P REDM ET

ˇ ˇ I TERA CNÍ VÝPO CTY ˇ B C . P ETR Š AFA RÍK xsafar14

B RNO 2010

Obsah 1

Úvod

2

Analýza problému a princip jeho rˇešení 2.1 Funkce poˇcítající tanh( x ) . . . . . . . . 2.1.1 Definice funkce . . . . . . . . . 2.1.2 Použití dílˇcích funkcí . . . . . . 2.1.3 Algoritmické rˇ ešení faktoriálu 2.2 Funkce poˇcítající loga ( x ) . . . . . . . . 2.2.1 Tayloruv ˚ rozvoj funkce ln( x ) . 2.2.2 Užití rˇ etˇezových zlomku˚ . . . . 2.2.3 Poˇcítání binárního logaritmu . 2.3 Funkce poˇcítající statistické informace 2.3.1 Vážený aritmetický prumˇ ˚ er . . 2.3.2 Vážený kvadratický prumˇ ˚ er . .

3

1

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Návrh rˇešení problému 3.1 Funkce poˇcítající tanh( x ) . . . . . . . . . . . 3.2 Funkce poˇcítající loga ( x ) . . . . . . . . . . . 3.2.1 Výpoˇcet binárního logaritmu lb( x ) 3.3 Statistické funkce . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

. . . .

. . . . . . . . . . .

2 2 2 3 3 3 4 5 5 5 6 6

. . . .

7 8 8 9 10

4

Specifikace testu˚

11

5

Popis vlastního rˇešení 5.1 Ovládání programu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Implementace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 14

6

Závˇer

15

Literatura

16

A Metriky kódu

I

B Grafy

II

C Schémata

IV

i

Seznam obrázku˚ B.1 log( x ) vypoˇctený více algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Graf funkce tanh() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Graf funkcí log0.5 ( x ), log2 ( x ) a log10 ( x ) . . . . . . . . . . . . . . . . . . . . . C.1 C.2 C.3 C.4 C.5 C.6 C.7 C.8

Schéma volání jednotlivých subroutin z funkce main() . . Schéma práce iteraˇcních funkcí . . . . . . . . . . . . . . . . Schéma výpoˇctu tanh( x ) . . . . . . . . . . . . . . . . . . . . ˇ Rešení výpoˇctu ex pomocí funkcí izpexpfact a izpexplim Schéma výpoˇctu logaritmu . . . . . . . . . . . . . . . . . . . Schéma výpoˇctu binárního logaritmu lb( x ) . . . . . . . . . Schéma výpoˇctu desetinné cˇ ásti binárního logaritmu lb( x ) Schéma volání statistických funkcí . . . . . . . . . . . . . .

ii

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

II III III IV V VI VII VIII IX X XI

Typografická konvence • Kurzivou jsou psány zásadní termíny cˇ i podstatná slova. • Neproporciální písmo je použito v pˇrípadˇe názvu˚ vlastních funkcí, promˇenných a cˇ ástí kódu. Dále je užit v URLs. • [Neproporciální font] v hranatých závorkách je použit pro klávesové zkratky. • Šedé pozadí je použito pro zvýraznˇení prvních slov poznámek. • Matematické funkce a konstanty jsou sázeny antikvou. • Kaligrafický F ont je užit pro sazbu definiˇcního oboru (R, N , . . . ).

iii

ˇ výpocty ˇ Projekt 2 – Iteracní

Bc. Petr Šafaˇrík

Kapitola 1

Úvod Dokumentace k druhému projektu do pˇredmˇetu˚ IZP – základy programování, a IUS – Softwarové inženýrství, vyuˇcovaným na VUT v Brnˇe, fakultˇe informaˇcních technologií. Výsledný program má nˇekolik separátních funkcí – poˇcítá logaritmus libovolného cˇ ísla o libovolném základˇe a hyperbolický tangens – oboje s pˇredem definovanou pˇresností. Dále program umožnuje ˇ poˇcítat vážený prumˇ ˚ er ze vstupních hodnot a to bud’to vážený aritmetický prumˇ ˚ er a nebo vážený kvadratický prumˇ ˚ er. Jelikož se jedná o tˇri vzájemnˇe nesouvisející subroutiny, je rˇ ešení každé z nich ve vˇetšinˇe kapitol této dokumentace vˇenována vlastní podkapitola. Bude zde postupnˇe probrán návrh každé subroutiny, její implementace a pˇrípadné problémy a nebo omezení. Výsledný program je pouze konzolový (CLI), pˇriˇcemž o vybrané funkci rozhodne uživatel už pˇri spuštˇení programu pomocí parametru. Pro informace o parametrech staˇcí spustit program s pˇrepínaˇcem -h, který vypisuje na terminál základní nápovˇedu. Poté program naˇcítá data ze standardního vstupu a po zpracování je vypisuje opˇet na standardní výstup. Chybová hlášení se vypisují na standardní chybový výstup. Algoritmy jsou pˇredevším rˇ ešeny jako iteraˇcní s podmínkou pˇresnosti, jak bude vysvˇetleno dále. Krom výše popsaných funkcí byly v rámci rˇ ešení naprogramovány i další knihovní funkce, jako je výpoˇcet x y , kde y je celé cˇ íslo, poˇcítání factoriálu a nebo funkce ˇ exp(). Rešení je zpracováno v jazyce C, aˇckoli se pro matematické výpoˇcty více hodí programovací jazyk Fortran (FORmula TRANslator), který je pro matematické výpoˇcty rychlejší a efektivnˇejší. Na druhou stranu zadání se snaží reflektovat skuteˇcné možné problémy programátora (a je pomˇernˇe irelevantní, ve kterém jazyce programátor pracuje) s iteraˇcními výpoˇcty a rˇ ešení ve Fortranu by si vyžádalo podobné konstrukce – pouze s nejspíše vyšší efektivitou pˇri výpoˇctech plynoucí z vlastního jazyka.

1



Kapitola 2

Analýza problému a princip jeho rˇešení Pro použití maker NAN a INFINITY je nutné použít knihovnu math, proto je v nˇekterých pˇrípadech pˇrítomné preprocesové makro #include <math.h>. Ovšem nejsou používány funkce z této knihovny s výjimkou funkce double fabs(double x).

2.1 2.1.1

Funkce poˇcítající tanh( x ) Definice funkce

Funkce hyperbolického tangentu je z definice (Bartsch, 1996) definován vztahem (2.1) tanh( x ) =

e x − e− x . e x + e− x

(2.1)

Pomocí roznásobení ex − e− x je možné vztah (2.1) pˇrevést na vztah tanh( x ) =

e2x − 1 , e2x + 1

(2.2)

který je v routinách dále použit. Graf funkce tanh( x ) je na obrázku B.2. Na rozdíl od trigonometrických (a cyklometrických) funkcí nevychází hyperbolické funkce z "jedniˇckové kružnice", ale z hyperboly, pˇriˇcemž základem jsou funkce sinh() a cosh() a funkce tanh() a coth() jsou z tˇechto funkcí zkonstruovány. Definiˇcní obor funkce tanh( x ) je celá reálná osa – e2x + 1 nikdy nenabude hodnoty 0. Obor hodnot je interval h−1; 1i. Hodnot 1, −1 funkce tanh() nabývá v bodˇe ∞, resp. −∞. Pro výpoˇcet funkce exp( x ) (ˇci exp(2x )) je možné využít dvou aproximativních vztahu. ˚ První vychází z jedné z možných definic funkce exp( x ), druhá z taylorovského rozvoje ˇ funkce. Rešení úlohy tanh( x ) tedy pˇredstavuje správné vyˇcíslení hodnoty exp( x ). Poznámka: Od jisté hodnoty (v použitém rˇ ešení je tato hodnota ±5) není hodnota tanh( x ) poˇcítána, ale rovnou se vrací hodnota 1.0, tedy asymptotickou hodnotu. Další omezení je nutné aplikovat na pˇresnost – algoritmy pro poˇcítání jsou aproximativní a podobnˇe jako v pˇrípadˇe hodnoty x by vedly k pˇríliš 2



dlouhým cˇ asum ˚ pˇri výpoˇctu. V pˇrípadˇe pˇredkládaného programu pˇresnost limitována na 10 míst.

2.1.2

Použití dílˇcích funkcí

Jak bylo napsáno o nˇekolik rˇ ádku˚ výše, pro urˇcení hodnoty tanh( x ) je nutné urˇcit hodnotu funkce exp( x ). Možností vyˇcíslení hodnoty exp( x ) je nˇekolik, pro algoritmizaci se ovšem nejlépe hodí dva následující. První vychází z infinitezimálního poˇctu x n ex = lim 1 + . (2.3) n→∞ n Rovnice (2.3) ovšem není rekurzivního, rekurentního a ani iteraˇcního typu, takže pro dosažení požadované, pˇredem neznámé pˇresnosti není možné použít pˇredchozího výsledku a tím pádem je cˇ as potˇrebný na výpoˇcet delší. Ovšem netrpí pˇreteˇcením – což je naopak neduh u druhé metody vycházející z taylorova rozvoje funkce exp( x ), kde platí vztah ex = 1 + x +

∞ x2 x3 x4 xi + + +··· = ∑ . 2! 3! 4! i! i =0

(2.4)

Silnou nevýhodou tohoto rozvoje je velká nároˇcnost na pamˇet’ pˇri výpoˇctu faktoriálu, který pˇri vyšších cˇ íslech snadno zpusobí ˚ pˇreteˇcení. Naopak pro hodnoty v intervalu (−1, 1) se jedná o velice rychle konvergující funkci, kde pro "rozumnou" pˇresnost nehrozí pˇretecˇ ení. Pokud je požadována pˇresnost vyšší, je použit algoritmus pomalejší, leˇc "bezpeˇcnˇejší".

2.1.3

Algoritmické rˇešení faktoriálu

Poˇcítání faktoriálu patˇrí mezi nejˇcastˇejší rekurzivní vztahy a úlohy. Faktoriál samotný je definován Bartsch (1996) rekurzivnˇe F (0) = 1 , F ( n ) = n · F ( n − 1)

| ( n ∈ N0 ) .

Místo funkce F (n) se ovšem obvykle používá znaˇcení "n!". Z výše napsaného plyne, že n! = 1 · 2 · 3 · · · · · (n − 2) · (n − 1) · n . Pˇrehledové hodnoty faktoriálu˚ cˇ ísel od 1–15 jsou uvedené v tabulce 2.1.

2.2

Funkce poˇcítající loga ( x )

Matematická funkce loga ( x ) je definována ekvivalencí (2.5) loga ( x ) = y ⇔ ay = x .

(2.5)

Logaritmus je inverzní funkce k funkci y = ex a definován pouze pro x ∈ R+ , tedy kladná cˇ ísla reálné osy X. Dále je napˇríklad z grafu funkce (na obrázku B.3) vidˇet, že funkce loga ( x ) je vždy rovna nule v pˇrípadˇe, že x = 1; neboli loga (1) = 0. 3



Dále platí: ( lim loga ( x ) =

+∞ a ∈ (0, 1) ,

(2.6)

−∞ a ∈ (1, ∞) .

x → 0+

Aby byl výpoˇcet logaritmu univerzální, co se týˇce volby základu logaritmu a, je nutné zmínit ještˇe jednu vlastnost – pˇrevod ruzných ˚ logaritmu˚ mezi ruznými ˚ základy. Platí totiž loga ( x ) =

logb ( x ) . logb ( a)

(2.7)

Rovnice (2.7) vyplývá ze tˇrí základních pravidel pro práci s logaritmy: log x m = m log x , log( x · y) = (log x ) + (log y) , x log = (log x ) − (log y) . y

(2.8)

Nyní již je nutné najít nejvhodnˇejší algoritmus pro definování (libovolné) hodnoty logaritmu – díky rovnici (2.7) se logaritmy mezi ruznými ˚ základy jednoduše pˇrevedou. Mezi uvažované algoritmy patˇril tayloruv ˚ rozvoj funkce ln( x ) (logaritmus o základˇe e) a binární logaritmus (logaritmus o základˇe 2) a rˇ ešení ln( x ) rˇ etˇezovými zlomky.

2.2.1

Tayloruv ˚ rozvoj funkce ln( x )

Tayloruv ˚ rozvoj je vztah pro aproximaci hodnoty funkce f v bodˇe a, který má podobu f ( x ) = f ( a) +

f 0 ( a) f (n) ( a ) f (2) ( a ) ( x − a) + ( x − a )2 + · · · + ( x − a)n . 1! 2! n!

(2.9)

Pro pˇrípad pˇrirozeného logaritmu ln je možné udˇelat rozvoj funkce ln( x + 1) a z taylorova rozvoje dostaneme ∞ x2 x3 xn ln( x + 1) = x − + − . . . = ∑ (−1)(n+1) . (2.10) 2 3 n n =1 Bohužel tayloruv ˚ rozvoj funguje v pˇrípadˇe ln jen pro blízké okolí – v pˇrípadˇe logaritmu je možné jej použít jen pro interval x ∈ (0; 2) a to pˇri nekoneˇcném množství iterací dle rovnice (2.10) – v praxi je použitelná pˇresnost pro x ∈ (0; 1, 5). Ovšem i pˇri maximálním (nekoneˇcném) poˇctu kroku˚ je pˇresný pouze pro polovinu hodnoty základu e. n

n!

n

n!

n

n!

1 2 3 4 5

1 2 6 24 120

6 7 8 9 10

720 5 040 40 320 362 880 3 628 800

11 12 13 14 15

39 916 800 479 001 600 6 227 020 800 87 178 291 200 1 307 674 368 000

Tabulka 2.1: Tabulka hodnot vypoˇcteného faktoriálu cˇ ísel 1–15 4


2.2.2


Užití rˇetˇezových zlomku˚

V knize Cuyt et al. (2008) autor mimo jiné uvádí i užití rˇ etˇezových zlomku˚ pro rˇ ešení pˇrirozeného logaritmu ln( x + 1). Algoritmus v knize pracuje dle rovnice ln( x + 1) =

2x . −(m − 1)2 x2 2+x+ ∑ m=2 (2m − 1)(2 + x ) ∞

(2.11)

Algoritmus byl testován, bohužel se ukázalo, že pro vˇetší hodnoty x není s to dosáhnout požadované pˇresnosti. Rozdíl hodnoty ln( x ) spoˇctené pomocí tohoto algoritmu oproti správným hodnotám jsou v grafu B.1 na stranˇe II.

2.2.3

Poˇcítání binárního logaritmu

Binární logaritmus lb = log2 – tedy logaritmus o základˇe a = 2 – je pro poˇcítaˇc nejvhodnˇejší možné rˇ ešení. Všechna data jsou v poˇcítaˇcích uložena jako jedniˇcky a nuly. Jak již bylo napsáno, není podstatné, jestli bude algoritmus používat základ 10, e a nebo 2 – díky vztahu (2.7) se spoˇcítá logaritmus x a logaritmus požadovaného základu a vzájemnˇe se podˇelí.

2.3

Funkce poˇcítající statistické informace

Statistika a statistické funkce jsou nutností pˇri zpracování snad všech reálných dat – reálná data jsou vždy zatíženy chybami, které rozlišujeme na dva druhy: Systematické chyby jsou takové chyby, které vznikají nevhodným cˇ i pˇrímo špatným postupem pˇri získávání dat (napˇr. špatná kalibrace pˇrístroje) a data jsou tak systematicky špatnˇe. Vyhnout se systematickým chybám není vždy jednoduché, ale vždy je možné. Náhodné chyby jsou ovšem chyby vlastní každému mˇerˇ ení a jejich odstranˇení není možné – vznik tˇechto nepˇresností je dán zákony (kvantové) fyziky. Ve vˇedeckých výpoˇctech (a nejen v nich) se tedy než s jednotlivými daty pracuje se statistickými informacemi. Program proto umí zpracovávat i nˇekteré statistické údaje o vstupních hodnotách. Jsou to dvˇe základní verze poˇcítání váženého prumˇ ˚ eru – aritmetický vážený prumˇ ˚ er a kvadratický vážený prumˇ ˚ er. Vážený prumˇ ˚ er je složitˇejší a o nˇeco sofistikovanˇejší verzí statistického prumˇ ˚ eru. Zatímco statistický prumˇ ˚ er pˇredpokládá, že všechna jednotlivá vstupní cˇ ísla jsou stejnˇe podstatná, tak pˇrikládáním ruzných ˚ vah vstupním údajum ˚ pˇrikládáme ruznou ˚ duležitost ˚ tˇemto hodnotám – váha je tak definována jako nezáporné reálné cˇ íslo. V jistém smyslu je možné považovat statistický prumˇ ˚ er (at’ statistický aritmetický pru˚ mˇer nebo statistický kvadratický prumˇ ˚ er) za speciální verze váženého prumˇ ˚ eru, kde mají všechny vstupní hodnoty stejnou váhu. Není možné definovat nic jako definiˇcní obor statistických funkcí – je možné dˇelat statistiku ze všeho. V pˇrípadˇe programu je definiˇcním oborem hodnot w celá reálná osa – neboli w ∈ R – a oborem hodnot vah h je celá kladná cˇ ást reálné osy (h ∈ R+ ).

5


2.3.1


Vážený aritmetický prumˇ ˚ er

Aritmetický prumˇ ˚ er w z hodnot (w1 , w2 , . . . , wn ) je matematicky definován (Bartsch, 1996) vztahem (2.12) 1 n w = ∑ wi . (2.12) n i =1 Pokud je tˇreba pracovat i s vahami hodnot, upraví se vztah (2.12) na (2.13) n

∑ wi · h i

w=

i =1

n

.

(2.13)

∑ hi

i =1

2.3.2

Vážený kvadratický prumˇ ˚ er

Kvadratický prumˇ ˚ er je statistická veliˇcina poˇcítána jako druhá odmocnina z aritmetického prumˇ ˚ eru druhých mocnin z daných hodnot Bartsch (1996). s n w2 (2.14) w= ∑ i . n i =1 Pokud bude do vztahu (2.14) zaˇclenˇena i práce s vahami, je vztah následující v u n u w2 · h u∑ i i u w = u i =1 n . t ∑ hi

(2.15)

i =1

V programu je zapracován i algoritmus pro pˇrípad h = 0 – nulová váha odpovídá nulové duležitosti ˚ hodnoty w. Ta je proto ignorována, pouze se vytiskne pˇredchozí výsledek. Výjimku tvoˇrí první dvojice hodnot, kde nejen záporná, ale i nulová váha znamená ukonˇcení bˇehu programu.

6



Kapitola 3

Návrh rˇešení problému Volání programu musí vyhovovat zadání projektu1 . Jednotlivé možnosti jsou shrnuty v tabulce 3. Program musí provést testy vstupních parametru˚ (vizte kapitolu 4) na jejich správnost, pˇrípadnˇe se s chybovým hlášením ukonˇcí. Pokud jsou vstupní parametry v poˇrádku, program vyhodnotí, kterou subroutinu spustit. Jsou-li zvolenou subroutinou statistické funkce, volá pˇrímo modul pro statistické funkce. V pˇrípadˇe vyˇcíslení funkce tanh( x ) a nebo loga ( x ) se pˇrímo z hlavního tˇela funkce volají funkce pro získání cˇ ísla, které se pˇredává pˇríslušné funkci. Funkce poˇcítající loga ( x ) a tanh( x ) vrací spoˇctenou hodnotu, kterou program pˇrímo tiskne. Práce s matematickými funkcemi tanh( x ) a loga ( x ) je uzavˇrena do smyˇcky, jejíž opuštˇení je EOF na vstup programu2 . Vývojový a rozhodovací diagram hlavní funkce main() je na obrázku C.1. Tento nezachyvuje testování vstupních hodnot. Pro poˇcítání tanh( x ) a loga ( x ) bude použit vztah (2.2) s podmínkou pˇresnosti sigdig platných míst. Takto definovaná pˇresnost znamená, že se dvˇe po sobˇe jdoucí iterace ite1 https://www.fit.vutbr.cz/study/courses/IZP/private/projekty/proj2.html 2 Pˇri

naˇcítání hodnot ze standardního vstupu se v UNIX-like systémech jedná o klávesovou zkratku c s by to mˇela být klávesová zkratka Ctrl+Z – program nikdy nebyl tesCtrl+D, v pˇrípadˇe M$ Windows tován na tomto nesystémovém operátoru. Pozor, v pˇrípadˇe použití Ctrl+Z na UNIX-like systému proces pouze pˇresunete na pozadí, pˇriˇcemž návrat na popˇredí je možný napˇr. pˇríkazem fg (Bíbr and Šafaˇrík, 2010).

Funkce

Pˇrepínaˇc

Nápovˇeda tanh( x ) loga ( x ) warit.

proj2 -h proj2 --tanh sigdig proj2 --logax sigdig a proj2 --wam

wkvadr.

proj2 --wqm

Popis Vytiskne nápovˇedu k použití programu. sigdig - pˇresnost sigdig - pˇresnost; a - základ logaritmu Hodnoty váženého aritmetického prumˇ ˚ eru již naˇctené posloupnosti hodnot. Hodnoty váženého kvadratického prumˇ ˚ eru již naˇctené posloupnosti hodnot.

Tabulka 3.1: Parametry pˇri spuštˇení programu

7



raˇcního vztahu se na pozici sigdig+1 nezmˇení. Uvažujeme-li o pˇresnosti na 3 platná desetinná místa, poté bude testováno 4. platné místo, nikoli tˇretí! Každé spoˇctené cˇ íslo tedy vynásobíme hodnotou 10 N +1 a každé dvˇe iterace od sebe odeˇcteme. Je-li absolutní hodnota rozdílu vˇetší než nula, je tˇreba udˇelat další krok. Pokud je menší než jedna (tedy rozdíly jsou pouze zlomky z požadované pˇresnosti), je splnˇena výše definovaná podmínka pˇresnosti a výpoˇcet muže ˚ být ukonˇcen. Algoritmy izptanh a logax pracují dle schémata na obrázku C.2, více v pˇríslušných podkapitolách této kapitoly.

3.1

Funkce poˇcítající tanh( x )

Jak bylo napsáno v cˇ ásti 2.1 na stranˇe 2, je k výpoˇctu funkce tanh( x ) potˇreba spoˇcíst e2x − 1 . e2x + 1 Jedná se o pˇrímou aplikaci iteraˇcního algoritmu, jehož schéma je na obrázku C.2 na stranˇe V. V pˇrípadˇe, že výsledek nedosahuje požadované pˇresnosti, volá opˇet funkci pro výpoˇcet e2x , ovšem s požadavkem na vyšší pˇresnost. Z rozboru dvou možných rˇ ešení funkcí pro výpoˇcet ex plyne, že v intervalu (−1, 1) je vhodnˇejší použít rychleji konvergující funkci využívající taylorova rozvoje (vizte cˇ ást 2.1.2 na stranˇe 3), naopak pro interval x ∈ (−∞, 1i ∪ h1, ∞) je výhodnˇejší použití definice ex = limn→∞ (1 + x/n)n . Funkce izpexp bude pracovat podle jednoduchého schématu na obrázku C.4a na stranˇe VII. Dvˇe volané funkce budou pracovat podle schémat C.4b pokud je x ∈ (−1, 1) a nebo C.4c, pokud abs( x ) ∈ h1; 5i. V pˇrípadˇe, že funkce izpexpfact není schopna dosáhnout požadované pˇresnosti, je volána funkce druhá izpexplim. tanh( x ) =

3.2

Funkce poˇcítající loga ( x )

Výpoˇcet binárního logaritmu je velmi dobˇre známý a je tedy takˇrka nemožné vyhnout se nejrozšíˇrenˇejším zdrojum ˚ informací Knuth (2008, str. 24–26)3 . Je zˇrejmé, že použitý algoritmus a i implementace je velmi podobná implementaci z tˇechto velkých zdroju˚ informací. Výpoˇcet logaritmu musí akceptovat tyto pˇrípady a dávat správné výsledky, aniž by bylo nutné výsledky poˇcítat: • x < 0 – výsledek musí být NAN • x = 0 ∧ a > 1 – výsledek je: −∞ • x = 0 ∧ a < 1 – výsledek je: +∞ V pˇrípadˇe, že je základ a = 2, není nutné pˇrepoˇcítávat výsledek logaritmu pomocí vztahu (2.7), ale staˇcí vypoˇcítat jen lb( x ). Pro výpoˇcet obecného logaritmu o libovolném základˇe se využije obecný algoritmus na obrázku C.2 na stranˇe V. Konkrétní podoba algoritmu je na schématu C.5 na stranˇe VIII. Volaná funkce izplgx() poˇcítá binární logaritmus z cˇ ísla x a pˇresností n – poˇcet desetinných míst. 3 Ale

je možné totožný algoritmus najít i na stránkách projektu http://wikiperia.org

8


3.2.1


Výpoˇcet binárního logaritmu lb( x )

Výpoˇcet binárního logaritmu je nutné provádˇet ve dvou krocích: 1. Spoˇcíst celou cˇ ást logaritmu – subroutina izplgxbin() 2. Spoˇcíst desetinnou cˇ ást logaritmu – subroutina izplgxfrac() Funkce izplgx() prvnˇe spoˇcte celou cˇ ást logaritmu a poté i desetinnou voláním dvou ruzných ˚ funkcí. V pˇrípadˇe, že je x v intervalu x ∈ (0; 1), volá se -izplgx() ovšem s argumentem nikoli x, ale pˇrevrácené hodnoty 1/x: log2 x = −1 · log2 x −1 = −1 · log2 1/x x ∈ (0; 1) ⇒ 1/x ∈ (1, R+ ) Výpoˇcet celé cˇ ásti binárního logaritmu Pˇri výpoˇctu celé cˇ ásti binárního logaritmu je využito faktu, že známe-li cˇ íslo x a základ a, tak logaritmus loga ( x ) bude vˇetší jako jedna, pokud x > a a menší jako jedna, pokud bude x < a. Pokud je x > a, tak se k výsledné hodnotˇe pˇriˇcte 1 a cˇ íslo x se základem a podˇelí. Tato smyˇcka konˇcí ve chvíli, kdy x < a. Tuto myšlenku je možné zefektivnit použitím podmínek. Je-li cˇ íslo x rovno nule, tak je návratová hodnota -1. V pˇrípadˇe, že x je vˇetší 2n , (kde n je postupnˇe n = {16, 8, 4, 2, 1}), tak bude zvˇetšena hodnota celé cˇ ásti lb( x ) o n a x vydˇeleno 2n . Algoritmus pˇredpokládá, že nejvˇetší zpracovávané cˇ íslo je 232 – tedy že bude pˇreklad a bˇeh programu probíhat na 32bitovém operaˇcním systému. Výpoˇcet desetinné cˇ ásti logaritmu Máme-li spoˇctenu celou cˇ ást logaritmu, je nutné dopoˇcítat cˇ ást desetinnou. Tu vypoˇcte subroutina izplgxfrac() pracující s rekurentním algoritmem na schématu C.7. Mˇejme na zaˇcátku cˇ íslo x, které spadá do intervalu x ∈ (1; 2). Je-li x rovno jedné, poté je algoritmus u konce a navrací nulu. Stejnˇe navrací nulu v pˇrípadˇe, že pˇresnost je rovna nule – v tomto pˇrípadˇe algoritmus dosáhl požadovaného poˇctu iterací. Pokud je presnost vˇetší než 0, je dekrementována. Jak již bylo napsáno, tak hodnota x náleží do intervalu (1, 2). Budeme jej tak dlouho umocnovat, ˇ dokud nebude x v intervalu x ∈ (2; 4). Pˇri každém umocnˇení naopak vydˇelíme hodnotu zlomek dvˇema. Návratová hodnota je promˇenná zlomek+izplgxfrac(x/2,zlomek,presnost) – tedy volání dalšího kroku pro zvýšení pˇresnosti.

9


3.3


Statistické funkce

V rámci subroutiny izpstatistics() budou rˇ ešeny úlohy pro naˇctení dvou hodnot (w a váhy h), ovˇerˇ ení, že h ∈ R+ a w i h jsou ruzné ˚ od EOF. Po ovˇerˇ ení správnosti naˇctených veliˇcin budou data w a h pˇredána požadované subroutinˇe – izpwam pro vážený aritmetický prumˇ ˚ er a nebo izpwqm v pˇrípadˇe váženého kvadratického prumˇ ˚ eru. Funkce poˇcítající pru˚ mˇer (at’ již se jedná o izpwam tak i izpwqm) musí respektovat, že po každém zpracování hodnot je tˇreba uložit cˇ itatele a jmenovatele funkce, aby bylo možné zpracovávat další hodnoty. Zvláštˇe v pˇrípadˇe poˇcítání kvadratického prumˇ ˚ eru – zopakuji rovnici (2.15) v u n u w2 · h u∑ i i u w = u i =1 n , t ∑ hi i =1

kde je vidˇet, že v pˇrípadˇe, že by funkce vrátila pouze hodnotu w nebylo by možné poˇcítat dále. Proto je nutné, aby každá funkce vracela nejen výsledek, který se na konci cyklu vytiskne, ale i hodnotu cˇ itatele a jmenovatele, které jí budou pˇri dalším cyklu opˇet pˇredány jako parametry. Koncept práce statistické subroutiny izpstatistics je na obrázku C.8 na stranˇe XI. Volané subroutiny pouze poˇcítají cˇ itatele, jmenovatele a nakonec výsledek. Funkce izpwam dostane na vstupu hodnoty w a váhu h, dˇríve spoˇctený citatel a jmenovatel. Data zpracuje a poté vrátí citatel, jmenovatel a koneˇcnˇe i vysledek. Jednotlivé prvky jsou poˇcítány ze vztahu: ˚ citatel = citatel + w · h , jmenovatel = jmenovatel + h , citatel vysledek = . jmenovatel

(3.1) (3.2) (3.3)

Podobnˇe funkce izpwqm dostane na vstupu hodnoty w a váhu h, dˇríve spoˇctený citatel a jmenovatel a po zpracování vrátí aktualizované hodnoty citatel a jmenovatel a spoˇctený vysledek. Obdobou rovnic (3.1), (3.2) a (3.3) pro vážený kvadratický prumˇ ˚ er jsou citatel = citatel + w · w · h , jmenovatel = jmenovatel + h , s citatel vysledek = . jmenovatel

(3.4) (3.5) (3.6)

10



Kapitola 4

Specifikace testu˚ V této kapitole jsou popsány testy pro odhalení chybných a/nebo nesmyslných vstupních dat. Test 1 Chybná syntaxe −→ kontrola chyby ./proj2 ./proj2 ./proj2 ./proj2 ./proj2 ./proj2

#nedostatek parametrů -wam #správně --wam --tanh -6 #špatný rozsah přesnosti --tanh 15 #špatný rozsah přesnosti --logax 3 0 #špatný základ logaritmu --logax 3 1 #špatný základ logaritmu

Test 2 Správnost výsledku −→ Porovnání s pˇredpokládanou správnou hodnotou Statistické funkce – wam Testy váženého aritmetického prumˇ ˚ eru 1 1 1 1 1 1

3 3 1 1 1 1

1 1 9 9 5 5

8 8 1 150 1 1 80 1 0 0 9 1

-> -> -> -> -> ->

1 1 5 30 1 5

#různé váhy stejné hodnoty #různé váhy stejné hodnoty #stejné váhy různé hodnoty #stejné váhy různé hodnoty #váha 0 nezmění průměr #váha 0 nezmění průměr

dají dají dají dají

stejnou hodnotu stejnou hodnotu průměrnou hodnotu průměrnou hodnotu

Statistické funkce – wqm Testy váženého kvadratického prumˇ ˚ eru 1 3 1 8 -> 1 #různé váhy stejné hodnoty dají stejnou hodnotu 1 3 1 8 1 150 -> 1 #různé váhy stejné hodnoty dají stejnou hodnotu Tangens hyperbolický – tanh Testy hyperbolického tangentu +0 -> 0 # Test limity 0/x=0 +5 -> 1 # Test návratu hodnoty x>5 -5 -> -1 # Test návratu hodnoty x<-5

11



Logaritmus – logax Testy logarimu 0 -> -inf #při základě 3 0 -> +inf #při základě 0.5 1 -> 0 +inf -> -inf #řešení v nekonečnu pro a=3 -inf -> +inf #řešení v nekonečnu pro a=0.5

12



Kapitola 5

Popis vlastního rˇešení ˇ Rešení zadaných problému˚ vychází z rozboru˚ v kapitolách 2 a 3. Byly zvoleny algoritmy s nejlepším pomˇerem pˇresnosti a efektivity. Vše je rˇ ešeno sadou vzájemnˇe volaných funkcí, proto je doporuˇceno použít pro kompilaci pˇriložený Makefile. Poznámka: Makefile má naprogramovány také cíle pro instalaci (cíl install) a nebo odebrání ze systému (cíl uninstall). V pˇrípadˇe úpravy kódu mužete ˚ použít cíl clean pro odstranˇení všech binárních souboru˚ (objekty a nebo spustitelné soubory) a poté i distrib pro vytvoˇrení tar.gz archivu vhodného k redistribuci (výsledný archiv má tvar xsafar14-fit.tar.gz; tvar bez koncovky mužete ˚ upravit v cílu TARNAME v souboru Makefile). Tyto cíle jsou ovšem funkˇcní jen v UNIX-like operaˇcních systémech. Pro použití cíle install a uninstall musíte mít práva superuživatele!

5.1

Ovládání programu

Jedná se o cˇ istˇe konzolovou (CLI-pure) aplikaci bez grafického rozhranní (GUI). Vzhledem k nˇekolika vzájemnˇe nezávislým funkcím, jsou všechny možnosti popsány v nápovˇedˇe programu – staˇcí jej spustit s parametrem -h. V rámci implementace jsou zavedeny nˇekterá omezení na požadovanou pˇresnost, která je souˇcástí vstupních parametru˚ pro výpoˇcet logaritmu a hyperbolický tangens. Ty se spouští parametry: --tanh presnost pro výpoˇcet hyperbolického tangentu s pˇresností na presnost desetinných míst a --logax presnost zaklad pro výpoˇcet logaritmu o základˇe zaklad s pˇresností pˇresností na presnost desetinných míst. Pro výpoˇcet statistických informací se program spustí s parametry --wam a --wqm – vážený aritmetický/kvadratický prumˇ ˚ er. Po spuštˇení program oˇcekává na standardním vstupu data ke zpracování. V pˇrípadˇe funkcí tangentu a nebo logaritmu je to jediná hodnota – funkˇcní hodnota dané funkce se poté vypíše na standardní výstup. V pˇrípadˇe statistických funkcí se jedná o dvojici dat – hodnota a její váha. Funkce poˇcítající statistické informace pracuje s nezápornou hodnotou váhy, pˇriˇcemž krom první dvojice hodnota-váha je akceptovatelná i nulová váha.

13


5.2


Implementace

Parametry z pˇríkazové rˇ ádky zpracuje subroutina getParams() pˇrevzatá ze "vzorového projektu Ing. Davida Martinka". V pˇrípadˇe, že byla zvolena nápovˇeda (parametr -h), program rovnou vypíše nápovˇedu a skonˇcí. Funkcí loga ( x ) a tanh( x ), je spuštˇena smyˇcka, kdy se funkcí scanf() naˇcte jedna hodnota na vstupu, která se pošle funkci izplogax, pˇrípadnˇe izptanh. Na standardní výstup je pak funkcí printf() vypsána návratová hodnota volané funkce. Pˇri volání statistických funkcí je spuštˇena subroutina izpstatistics(UseWQM). Parametrem této funkce je použití kvadratického prumˇ ˚ eru a nebo ne. Funkce izpstatistics naˇcítá funkcí scanf() hodnoty x a váha, které poté dle parametru UseWQM volá bud’to subroutinu pro poˇcítání aritmetického nebo kvadratického váženého prumˇ ˚ eru dle vztahu˚ (2.13) a (2.15). Hodnoty jsou ukládány do struktury STATISTICS. Na konci smyˇcky se vypíše aktuální prumˇ ˚ er ze všech dˇríve získaných dat.

14



Kapitola 6

Závˇer Program poˇcítá tˇri úlohy, pˇriˇcemž volba úlohy k poˇcítání je provedena pomocí parametru pˇri startu programu. Program umí spoˇcíst loga ( x ), tanh( x ) se zadanou pˇresností a statistické funkce váženého aritmetického a váženého kvadratického prumˇ ˚ eru. Funkce poˇcítající tanh( x ) výsledek rˇ eší pouze v intervalu (−5; 5) – mimo tento interval navrací pouze asymptotickou hodnotu ±1. Funkce poˇcítající loga ( x ) byla zvolena na základˇe analýzy (vizte cˇ ást 2.2 na stranˇe 3) tak, aby byla pokud možno co nejpˇresnˇejší a nejrychlejší. Funkce izptanh a izplogax jsou naprogramovány tak, aby je bylo možné použít i v jiných subroutinách. Stejnˇe tak jsou ošetˇreny i funkce pro výpoˇcet statistické funkce váženého aritmetického a váženého kvadratického prumˇ ˚ eru.

15



Literatura H. Bartsch. Matematické vzorce. Mladá fronta, a. s., 1996. I. Bíbr and P. Šafaˇrík. 333 Tipu˚ a Triku˚ pro Mandriva Linux. Computer Press, a. s., 2010. A. Cuyt, V. Petersen, B. Verdonk, and H. Waadeland. Handbook of Continued Fractions for Special Functions. Springer, 2008. D. Knuth. Umˇení programování; 1. díl – Základní algoritmy. Computer Press, a. s., 2008. H. Kopka and P. Daly. LATEX – Kompletní pruvodce. ˚ Computer Press, 2004.

Tato práce byla vysázena v sázecím systému LATEX 2ε (Kopka and Daly, 2004). 16



Dodatek A

Metriky kódu Poˇcet souboru: ˚

19 souboru˚ vˇc. souboru˚ LICENSE a Makefile

Poˇcet rˇádku˚ zdrojového textu (vˇc. komentáˇru): ˚ Velikost statických dat:

1 303 rˇádku˚

7 209 B

Velikost spustitelného souboru: lizací pˇri pˇrekladu)

13 117 B (Linux, 32bit, bez ladících informací s optima-

Neoddˇelitelnou souˇcástí programu je soubor s licencí LICENSE – program je licencován pod GPLv3+.

I



Dodatek B

Grafy

Funkce ln (x) "data" u 1:4 0*x

0.4

log_a(x)

0.2

0

-0.2

-0.4

0

500

1000

1500

2000

2500 Osa x

3000

3500

4000

4500

5000

Obrázek B.1: Logaritmus x rˇ ešený algorimty binárního logarimu (ˇcervená kˇrivka) a rˇ etˇezovým zlomkem (zelená kˇrivka). Správná hodnota dosazená z knihovny math.h splývá ˇ s cˇ ervenou kˇrivkou. Rešení taylorovým rozvojem není v zobrazených hodnotách osy x – je definován jen pro x ∈ (0; 2)

II



2 (tanh(x)) 1.5

1

0.5

0

-0.5

-1

-1.5

-2 -10

-5

0

5

10

Obrázek B.2: Graf funkce tanh()

4 Funkce log_a (x) log0.5 (x) log2 (x) log10 (x)

3

2

log_a(x)

1

0

-1

-2

-3

-4 0

2

4

6

8

10

12

14

x

Obrázek B.3: Graf funkcí log0.5 ( x ), log2 ( x ) a log10 ( x ) III



Dodatek C

Schémata main(akce[,presnost[,a]])

nacti_x

NE

ANO

akce = statistika

akce=wqm return 0

ANO

x = EOF ANO

NE

UseWQM =1

UseWQM = 0 NE y=izplogax(presnost, x, a)

ANO

akce = log

izpstatistics(UseWQM)

y=izptanh(presnost,x)

ANO

akce = tanh

x = EOF

return 0

vytiskni(y)

Obrázek C.1: Schéma volání jednotlivých subroutin z nejvyšší úrovnˇe programu – funkce main(). Funkce poˇcítající loga ( x ) a tanh( x ) pracují s již naˇctenou hodnotou, pˇresností (a pˇríp. i základem a)

IV



iteracni_algoritmus(presnost,x)

rad = 10^(presnost+1) n=0

y_old=urci_krok_0(x,n)

n = n+1

y_new = dalsi_krok(x,n,y_old)

y_old = y_new

delta = abs( rad * (y_new - y_old))

delta > 1. NE

ANO

return y_new

Obrázek C.2: Schéma práce iteraˇcních funkcí, které bylo použity pro rˇ ešení algoritmu˚ funkcí tanh( x ) a loga ( x )

V



izptanh(presnost,x)

abs(x) > 5

ANO

return 1.0

exp2x = izpexp(2*x,1) n=2

yold = (exp2x-1)/(exp2x+1)

rad = izppow(10, presnost+1)

exp2x = izpexp(2*x,n)

ynew = (exp2x-1)/(exp2x+1)

delta = abs( rad * (ynew-yold)) n++

yold = ynew

return ynew

NE

delta > 1.0

ANO

Obrázek C.3: Schéma výpoˇctu tanh( x ) se zadanou pˇresností presnost

VI



izpexp(x,presnost)

return izpexplim(x,presnost)

NE

(x < 1) && (x > -1)

return izpexplim(x,presnost)

ANO

ANO

status = izpexpfakt(x,presnost)

status == -1

NE

return status

(a) Schéma volání dvou ruzných ˚ funkcí pro výpoˇcet ex izpexplim(x,presnost)

izpexplim(x,presnost)

rad = izppow(10,presnost+1)

rad = izppow(10,presnost+1)

yold = 1

yold = 1. + x n=1

ynew = izppow((1 + x/n), n ) ynew=yold+((izppow(x,n)/izpfactorial(n))

n = n+10

n = n+1

delta = abs( rad * ( ynew - yold)

n > 15

ANO

delta = abs( rad * (ynew-yold))

return -1

yold = ynew

yold = ynew

delta > 1. ANO

ANO

delta > 1

return ynew

(b) Schéma volání funkce izpexpfact

return ynew

(c) Schéma volání funkce izpexplim

ˇ Obrázek C.4: Rešení výpoˇctu ex pomocí funkcí izpexpfact a izpexplim

VII



izplogax(presnost,a,x)

x<0

ANO

ANO

x == 0 && a>1

ANO

x == 0 && a<1

x == 1

return NAN

ANO

return -INFINITY

return +INFINITY

return 0

rad = pow(10.,presnost+1) n=2

lgx=izplgx(x,1)

NE

yold = lgx

a != 2

ANO

lga=izplgx(a,1)

yold = lgx / lga

lgx = izplgx(x,n)

NE

ynew = lgx

a != 2

ANO

lga=izplgx(a,n)

ynew = lgx / lga

lgx = izplgx(x,n)

n++ delta = fabs( rad*(yold-ynew)) yold = ynew

ANO

delta > 1

NE

return ynew

Obrázek C.5: Schéma výpoˇctu logaritmu VIII



izplgx(x,presnost)

rad=pow(10,presnost+1) n=3 ANO

return (-1.0)*izplgx(1/x,presnot)

NE

cele=izplogbin(x)

x>1

zlomek=x*(1/pow(2,cele))

yold = cele+izplgxfrac(zlomek,1,2)

ynew =cele + izplgxfrac(zlomek,1,n)

n++ delta = fabs(rad*(ynew-yold)) yold=ynew

return ynew

NE

delta>1

ANO

Obrázek C.6: Schéma výpoˇctu binárního logaritmu lb( x )

IX



izplgxfrac(x,zlomek,presnost)

presnost == 0

return 0

x ==1

return 0

presnost--

x<2

i += 1

return zlomek + izplgxfrac(x/2,zlomek,presnost)

zlomek /= 2

x *= x

Obrázek C.7: Schéma výpoˇctu desetinné cˇ ásti binárního logaritmu lb( x )

X



izpstatistics(UseWQM)

stav = nacti(w)

ANO

stav == EOF

return 0

ANO

stav != 1

print(NAN)

stav = nacti(h)

ANO

stav == EOF

[vysledek,citatel,jmenovatel] = izpwam(w,h,citatel,jmenovatel)

NE

stav != 1

ANO

h<0

ANO

ANO

(UseWQM == 1)

print(NAN) return 0

print(NAN)

printerr("záporná váha!") return 1

[vysledek,citatel,jmenovatel] = izpwqm(w,h,citatel,jmenovatel)

print(vysledek)

return 0

NE

stav == 1

ANO

Obrázek C.8: Schéma volání statistických funkcí

XI

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ

Recommend Documents