ALG)8

298 Rozdział 13. Kodowanie i kompresja danych

W konsekwencji, jeśli będziemy interpretować duże liczby jako wielomiany, to wszelkie operacje na tych liczbach mogą zostać zastąpione algorytmami działającymi na wielomianach.

Aby dodawać i mnożyć duże liczby całkowite, musimy zatem nauczyć się dodawać i mnożyć... wielomiany!

Reprezentacja wielomianu w' C++ jest najprostsza przy użyciu tablic, służących do zapamiętywania współczynników. Wielomian stopnia n i zmiennej x jest ogólnie definiowany następująco:

W(x) - a_nx" + a_n_|X"~' +...+a,x + a₀.

Obliczanie wartości W(b) dla pewnego b, wydaje się dość kosztowne z uwagi na konieczność wielokrotnego mnożenia i dodawania:

int oblicz_wielomianl(int b, int wfl, int rozm)

(

int res=0,pot=l;

for(int j=rozm-l;j>=0;j—)

(

res+=pot*w[j];    // sumy cząstkowe

pot*=b;    // następna potęga b

ł

return rea;

I

(W przypadku wielomianów o współczynnikach niecałkowitych, należy wszędzie zamienić typ int na double).

Istnieje jednak tzw. schemat Horneraó pozwalający na znacznie prostsze obliczenie W(b)\

\V{h) -    . ((a„b +    )h + a„_₂ )h+.. .+a, jb + a₀.

Realizacja schematu I lornera może być następująca:

horner.cpp

int oblicz_wielomianż(int a, int w[],int rozm)

int res=w[0);

for(int j=l;j<rozm;res=res*a+w[j++]); return res;

)

const n=5;    II stopień wielomianu

void main()

⁶ Wynalazcą tej procedury był tak naprawdę isaac Newton, ale historia przypisała ją Homerowi.