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 ² (x) + cos ² (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.