A programozás oktatása során elsődleges célom, hogy a diákok elsajátítsák azt az analitikus gondolkodást, amely lehetővé teszi a feladat megoldásához szükséges algoritmus kidolgozását. Pont a programozás az a művészet, ahol nagyon sok jó megoldás létezik és szinte divat kérdése a választás. Egy egyszerű példán szeretném bemutatni, hogy miért érdemes gondolkodni az algoritmusok fejlesztésén. A minta kódokat GNU Octave programban teszteltem.
Szinusz függvény
Aki dolgozott már trigonometrikus függvényekkel, tapasztalhatta, hogy a nagy mennyiségű trigonometrikus számítás hihetetlen mértékben lassíthatja a programokat. A legtöbb esetben matematikai trükköket vezetnek be az ilyen számítások elkerülésére, mint:
1 = sin 2 (x) + cos 2 (x)
A szinusz függvényt jól közelíthetjük Taylor sorba fejtéssel. Minél több elemet használunk, annál pontosabb becslést tudunk elvégezni, de közben megnöveljük a számítási időt is. A Taylor polinom már 5 taggal nagyon jól közelíti a szinusz függvényt, azonban csak [-π : +π] tartományban. Az alábbi függvény kiszámítja a paraméterként kapott szög (radiánban) szinusz értékét.
%% Szinusz függvény becslése Taylor sorral - 1 function RV = tsin(x,TS=5) a = x; while (max(a) > pi) a(a>pi) -= 2*pi; endwhile while (min(a) < -pi) a(a<-pi) += 2*pi; endwhile V = a; VX = a; VD = 1; Sgn = -1; N = 1; for i = 1:TS N += 2; VX = VX.*a.*a; VD *= N*(N-1); V += Sgn*VX/VD; Sgn *= -1; endfor RV = V; endfunction
A fenti tsin()
függvény alapértelmezett viselkedéssel 5 elemig számolja ki a Taylor polinomot. Első lépésként a paraméter szögeket – vektort feltételezve – a megfelelő tartományba igazítja. Ezt követően for
ciklusban kiszámítja a szükséges számú elemeket. Próbáljuk ki. Az alábbi kódban [-π : +π] tartományban hoztam létre szögeket, majd a beépített sin()
függvényt és a saját tsin()
függvényt is felhasználtam. Az utolsó sorban kiszámítottam a két adatsor eltérését (RMSE = root mean squared error).
%% Taylor sor tesztelése x = -pi:0.0001:pi; y0 = zeros(1,length(x)); y1 = y0; %% Beépített függvény használata id = tic(); y0 = sin(x); toc(id); %% Taylor sorba fejtés, 5 elemmel id = tic(); y1 = tsin(x); toc(id); printf("RMSE = %g\n",sqrt(mean( (y0-y1).^2 )));
Az általam használt asztali gépen 62832 érték kiszámítása a beépített szinusz függvénnyel 0.000734091 sec, míg a Taylor sor segítségével 0.00205708 sec. Mindkét érték igen alacsony, de azért látszik, hogy a beépített függvény 2,8-szoros sebességgel működik. A becslési hiba RMSE = 8.5946e-05 lett. Nyilvánvalóan kevesebb elemmel gyorsabban, de nagyobb hibával, míg több elemmel lassabban, de pontosabban lehet kiszámítani a függvény értékét. Amennyiben a fenti pontosság nekünk elegendő, a for
ciklus kiváltható beágyazott szorzásokkal. Ekkor nem tudjuk módosítani a Taylor sor elemeinek számát, de a számítás gyorsabb.
%% Szinusz függvény becslése Taylor sorral - 2 function RV = tsin2(x) a = x; while (max(a) > pi) a(a>pi) -= 2*pi; endwhile while (min(a) < -pi) a(a<-pi) += 2*pi; endwhile RV = a - a.*a.*a.*(1/6 - a.*a.*(1/120 - a.*a.*(1/5040 - a.*a.*(1/362880 - a.*a/39916800)))); endfunction
A fenti kódban a faktoriális értékek konstansok és fix elemszámmal dolgozik. Az előző példában létrehozott x
értékeken lefuttatva 0.000934124 sec idő alatt elvégezte a számítást. Ez megközelíti a beépített függvény sebességét, csak 27,25%-kal lassabb. A becslési hiba azonos, RMSE = 8.5946e-05 értékű lett.
Amennyiben nem lenne beépített függvény a számításhoz és nekünk kellene elkészíteni az algoritmust, nem mindegy melyik megoldást választjuk. Csupán a két Taylor sor függvényt összehasonlítva a második 2,2-szeres sebességgel hajtható végre az 5 taggal. A beágyazott szorzások alkalmazása népszerű technika polinomok kiszámításához. Érdemes elővenni a matematikai ismereteket és egyszerűsíteni a számításokat, ahol lehetséges.