Рачунање са полиномима¶

Када се операције сабирања, одузимања, множења и дељења полинома имплементирају онако како их и ми сами рачунамо, задатак није алгоритамски нарочито интересантан, али може да буде поучан у контексту дизајна софтвера.

Алгоритамски интересантан део ове лекције је ефикасан рекурзиван алгоритам за множење полинома, који омогућава да за велике степене полинома до резултата дођемо уз мање операција над бројевима, него уобичајеним приступом. Тај алгоритам је познат као Карацубин алгоритам, по математичару Анатолију Карацуби који га је смислио 1960. године.

Карацубин алгоритам је један од првих из групе алгоритама, који су касније постали познати као алгоритми типа подели и савладај (енгл. divide and conquer). Вероватно су вам од раније познати неки алгоритми овог типа, нпр. Quick Sort или Merge Sort. Алгоритам брзе Фуријеове трансформације (енгл. Fast Fourier Transform, скр. FFT), који је изузетно значајан у решавању разних инжењерских проблема, сродан је Карацубином и такође спада у алгоритме типа подели и савладај. Имајући ово на уму, идеја Карацубиног алгоритма је свакако вредна упознавања, јер су сличне идеје примењене у решавању многих других проблема.

У овој лекцији ћемо се прво задржати на уредној имплементацији метода потребних за рад са полиномима, водећи рачуна о детаљима. На крају ћемо објаснити идеју Карацубиног алгоритма и проанализирати број операција.

Полоними и рачунске операције над њима¶

Као што знамо, полином је задат својим степеном и низом коефицијената. Овде ћемо подразумевати да је једина променљива у свим полиномима \(x\), да су коефицијенти реални бројеви и да се задају редом, почевши од најстаријег, тј. оног уз највиши степен променљиве. На пример, полином \(P(x) = 2x^3 - 5x^2 + 7\) задат је степеном 3 и коефицијентима 2, -5, 0, 7. За степен полинома ћемо користити ознаку \(deg\), тако да за овај полином можемо да пишемо \(deg(P) = 3\). Када кажемо да је степен неког полинома \(n\), подразумевамо да је коефицијент уз степен \(n\) различит од нуле, а да су сви остали чланови полинома нижег степена од \(n\). Специјално, за нула-полином код кога су сви коефицијенти нуле, кажемо да је степена -1. Коефицијент уз највиши степен полинома називамо водећи коефицијент, а коефицијент уз \(x^0\) зовемо слободан коефицијент.

Од операција над полиномима, разматраћемо сабирање, одузимање, множење, дељење без остатка и рачунање остатка при дељењу. При извођењу ових операција користе се следећа правила рачунања са полиномима:

\(a \cdot x^k + b \cdot x^k = (a+b) \cdot x^k\). На пример, \(14 x^3 + 4 x^3 = 18 x^3\)
\(a \cdot x^k - b \cdot x^k = (a-b) \cdot x^k\). На пример, \(14 x^5 - 4 x^5 = 10 x^5\)
\((a \cdot x^k) \cdot (b \cdot x^j) = (a \cdot b) \cdot x^{k+j}\). На пример, \(2 x^3 \cdot 3 x^5 = 6 x^8\)
\(\frac{a \cdot x^k}{b \cdot x^j} = \frac{a}{b} \cdot x^{k-j}\). На пример, \(\frac{6 x^7}{2 x^5} = 3 x^2\)

Операције сабирања и одузимања полинома

Приликом сабирања и одузимања полинома, међусобно се сабирају и одузимају чланови са једнаким експонентима

пример сабирања полинома: \((2x^3-x^2+5x-3) + (7x^2 + 4) = 2x^3 + 6x^2 +5x + 1\)
пример одузимања полинома: \((2x^3-x^2+5x-3) - (7x^2 + 4) = 2x^3 - 8x^2 +5x - 7\)

Множење полинома

Приликом множења полинома користи се дистрибутивни закон, тј. сваки члан једног полинома се множи сваким чланом другог. На пример:

\[\begin{split}\begin{aligned} (3x^2 - 2x + 5) \cdot (4x^3 + 3x + 2) &= (3x^2 - 2x + 5) \cdot 4x^3 + (3x^2 - 2x + 5) \cdot 3x + (3x^2 - 2x + 5) \cdot 2 \\ &= (12x^5 - 8x^4 + 20x^3) + (9x^3 - 6x^2 + 15x) + (6x^2 - 4x + 10)\\ &= 12x^5 - 8x^4 + (20+9)x^3 + (6-6)x^2 + (15-4)x + 10\\ &= 12x^5 - 8x^4 + 29x^3 + 11x + 10\\ \end{aligned}\end{split}\]

Дељење полинома

Поступак дељења полинома је сличан поступку целобројног дељења вишецифрених бројева, при коме се поред количника добија и остатак. Нека су

\[\begin{split}P_n = a_n x^n + a_{n-1}x^{n-1} + \cdots + a_1x^1 + a_0\\ Q_m = b_m x^m + b_{m-1}x^{m-1} + \cdots + b_1x^1 + b_0\\\end{split}\]

два дата полинома. Желимо да израчунамо полиноме

\[\begin{split}R_r = c_r x^r + c_{r-1}x^{r-1} + \cdots + c_1x^1 + c_0\\ U_u = d_u x^u + d_{u-1}x^{u-1} + \cdots + d_1x^1 + d_0\\\end{split}\]

такве да је \(P = Q \cdot R + U\) и при томе \(deg(U) < deg(Q)\).

Као прво, можемо да уочимо да у случају када је степен полинома \(P_n\) мањи од степена полинома \(Q_m\), тада је количник нула-полином, тј. \(R(x) = 0\), а остатак је читав полином \(P_n\). У противном, на основу особина производа полинома и уведеног ограничења \(deg(U) < deg(Q)\) закључујемо да је водећи члан количника \(c_r x^r = \frac{a_n}{b_m}x^{n-m}\). Када ово уврстимо у једнакост \(P = Q \cdot R + U\) добијамо

\[\begin{split}\begin{aligned} P &= Q \cdot R + U\\ P &= Q \cdot (c_r x^r + R') + U\\ P &= Q \cdot c_r x^r + Q \cdot R' + U\\ P - Q \cdot c_r x^r &= Q \cdot R' + U\\ P' &= Q \cdot R' + U\\ \end{aligned}\end{split}\]

где смо са \(P'\) означили полином \(P - Q \cdot c_r x^r\), а са \(R'\) полином \(R - c_r x^r\). Да бисмо довршили поступак дељења, сада је потребно да поделимо полином \(P'\) полиномом \(Q\), добијемо количник \(R'\) и израчунамо \(R\) као \(R' + c_r x^r\). Ово је једноставнији задатак од полазног јер је степен полинома \(P'\) мањи од степена полинома \(P\), тако да овим поступком можемо да довршимо рачунање количника.

Погледајмо описани поступак на примеру. Поделићемо полиноме \(x^5+2x^4-2x^3+9x^2−4x+3\) и \(x^2−3x+4\)

први члан количника је \(x^5 / x^2 = x^3\), даље треба делити полином \(P' = P - Q x^3 = x^5+2x^4-2x^3+9x^2−4x+3 - (x^2−3x+4) \cdot x^3 = 5x^4-6x^3+9x^2-4x+3\)
други члан количника је \(5x^4 / x^2 = 5x^2\), даље треба делити полином \(P'' = P' - Q \cdot 5x^2 = 5x^4-6x^3+9x^2-4x+3 - (x^2−3x+4) \cdot 5x^2 = 9x^3-11x^2-4x+3\)
трећи члан количника је \(9x^3 / x^2 = 9x\), даље треба делити полином \(P''' = P'' - Q \cdot 9x = 9x^3-11x^2-4x+3 - (x^2−3x+4) \cdot 9x = 16x^2 - 40x + 3\)
четврти члан количника је :math:` 16x^2 / x^2 = 16`, преостали полином је \(P'''' = P''' - Q \cdot 16 = 16x^2 - 40x + 3 - (x^2−3x+4) \cdot 16 = 8 x - 61\). Пошто је овај полином степена мањег од степена полинома \(Q\), он представља остатак.

Закључујемо да је количник \(R = x^3 + 5 x^2 + 9 x + 16\) и остатак \(U = 8 x - 61\). Исправност рачунања можемо да потврдимо провером да важи \(P = Q \cdot R + U\).

Имплементација полонима и операција над њима¶

Природно је да полиноме у програму представимо објектима класе Polynomial (полином). Према ономе што је речено на почетку, класа треба да садржи низ реалних коефицијената a и својство Deg:

Мада ћемо у кôду за коефицијенте полинома да користимо листу реалих бројева, у даљој анализи користимо реч низ, као и до сада. При томе не мислимо на низ у смислу синтаксе језика, него на низ као математички појам.

Резултат сваке од пет помињаних операција над полиномима (сабирање, одузимање, множење, дељење и рачунање остатка) је такође полином, за који треба предвидети довољно дугачке низове за коефицијенте. Због тога је потребно да пре израчунавања коефицијената резултата знамо степен резултата, односно горње ограничење степена резултата.

Нека су дата два полинома, \(P(x)\) степена \(n\) и \(Q(x)\) степена \(m\), дакле \(deg(P) = n, deg(Q) = m\). Да бисмо имали на уму степене полинома, уобичајено је да их пишемо у индексу уз ознаку полинома, овако: \(P_n, Q_m\).

Користећи уведене ознаке, констатујмо да за полиноме \(P_n, Q_m\) важи:

\(deg(P_n + Q_m) \leq \max(n, m)\)
\(deg(P_n - Q_m) \leq \max(n, m)\)
\(deg(P_n \cdot Q_m) = n + m\)
\(deg(\frac{P_n}{Q_m}) = n - m\).

У случају збира или разлике, степен резултата може да буде мањи од \(\max(m, n)\) ако су полиноми \(P_n, Q_m\) истог степена и коефицијенти уз највиши степен се поништавају.

Нормализација записа полинома¶

Резултат сабирања и одузимања може да буде и било којег нижег степена, па и нула-полином. У случајевима када добијемо да је водећи коефицијент неког полинома нула, пожељно је да извршимо нормализацију записа тог полинома. На тај начин поједностављујемо имплементацију операција над полиномима и штедимо меморију. Нормализација се врши тако што се (на ефикасан начин) уклоне нуле у низу коефицијената, нпр. овако:

Имплементација операција над полиномима¶

Оператори +, -, *¶

Операције сабирања, одузимања и множења полинома можемо да имплементирамо као следеће методе:

public static Polynomial operator +(Polynomial P, Polynomial Q)
{
    if (P.Deg < Q.Deg)
    {
        Polynomial tmp = P; P = Q; Q = tmp;
    }
    Polynomial R = new Polynomial(P);
    for (int i = 0; i <= Q.Deg; i++)
        R.a[i] += Q.a[i];

R.Normalize();
    return R;
}

public static Polynomial operator -(Polynomial P, Polynomial Q)
{
    Polynomial R;
    if (P.Deg >= Q.Deg)
    {
        R = new Polynomial(P);
        for (int i = 0; i <= Q.Deg; i++)
            R.a[i] -= Q.a[i];
    }
    else
    {
        R = new Polynomial(Q.Deg);
        for (int i = 0; i <= P.Deg; i++)
            R.a[i] = P.a[i] - Q.a[i];
        for (int i = P.Deg+1; i <= Q.Deg; i++)
            R.a[i] = -Q.a[i];
    }
    R.Normalize();
    return R;
}

public static Polynomial operator *(Polynomial P, Polynomial Q)
{
    Polynomial R = new Polynomial(P.Deg + Q.Deg);
    for (int i = 0; i <= P.Deg; i++)
        for (int j = 0; j <= Q.Deg; j++)
            R.a[i + j] += P.a[i] * Q.a[j];

return R;
}

Захваљујући дефиницијама ових оператора, када будемо комплетирали класу Polynomial, у програмима који је користе моћи ћемо да пишемо наредбе попут:

и сличне, где су P, Q полиноми раније дефинисани у програму.

Оператори /, % (дељење и остатак)¶

Када ручно делимо два полинома, ми истовремено израчунавамо количник и остатак. Зато ћемо и у програму, да не бисмо понављали кôд, да напишемо метод DivMod, у коме се израчунавају оба резултујућа полинома. Метод DivMod може да буде и јаван, да би корисник коме су потребни и количник и остатак при дељењу нека два полинома добио резултате ефикасније. За кориснике којима је потребан само један од ова два резултујућа полинома, дефинишемо и операторе / и %, који се ослањају на метод DivMod.

Ови методи нам омогућавају да након комплетирања класе Polynomial пишемо:

или

и слично.

Операције између бројева и полинома¶

У математици је уобичајено да се користе записи \(P+c, c \cdot P\) и слични, где је \(P\) полином. а \(c\) реалан број. Да бисмо омогућили исту функционалност у програмима, не морамо да дефинишемо све могуће операторе као што су

и слични. Довољно је да напишемо оператор који омогућава компајлеру да реалне бројеве по потреби схвати као одговарајуће полиноме степена нула. Реч је о оператору имплицитне конверзије реалног броја у полином. Пошто се ради о имплицитној конверзији, неће бити потребе ни да у изразима у којима користимо класу Polynomial назначавамо када број треба да се заменимо полиномом (експлицитна конверзија, односно каст). Компајлер ће то сам да учини у ситуацијама у којима то разрешава конфликт неслагања типова, као што то чини када сабирамо целе и реалне бројеве.

Оператор имплицитне конверзије може, на пример, да се напише овако:

Када будемо комплетирали класу, овај оператор ће нам омогућити да у корисничком програму пишемо овакве и сличне наредбе:

Исписивање полинома¶

Да бисмо могли да исписујемо саме полиноме (а не само њихове вредности или коефицијенте) на исти начин као што исписујемо бројеве и податке других основних типова, можемо да редефинишемо метод ToString за полиноме. Дефиниција тог метода изгледа овако:

У овом методу можемо да израчунамо стринг, који ће да представља наш полином. Грубо говорећи, за дати полином треба у стринг нанизати записе облика +a_i*x^i за све степене i и коефицијенте a_i. Ипак, програмско исписивање полинома на начин који је уобичајен у математици је задатак који захтева нешто више пажње и труда, јер постоје разни изузеци од овог општег правила. На пример, ако је \(P(x)= 3x^5 +x^4 -7x^2 + 2x - 6\), не желимо да програм испише +3x^5+1x^4+0x^3+-7x^2+2x^1+-6x^0, него 3x^5+x^4-7x^2+2x-6. Из овог примера можемо да уочимо неколико додатних правила:

Знак плус треба изоставити испред водећег коефицијента
Када је коефицијент уз неки степен нула, цео члан треба изоставити, осим што код полинома једнаког нули треба исписати укупно једну нулу
Када је коефицијент уз неки степен један, треба изоставити коефицијент, осим ако је реч о слободном коефицијенту
Када је коефицијент уз неки степен минус један, треба писати само минус, осим ако је реч о слободном коефицијенту
Уз линеаран коефицијент не треба писати x^1, него x
Уз слободан коефицијент не треба писати x^0
Када је коефицијент уз неки степен негативан, треба изоставити знак плус испред члана

Да бисмо избегли понављање делова кôда, користимо помоћну функцију Monomial, која враћа текстуалну репрезентацију једног члана полинома, водећи рачуна о разним специјалним случајевима. У методу ToString само позивамо метод Monomial, и то једном за водећи члан, и једном у петљи за остале чланове.

Имплементација метода ToString за полиноме, омогућава нам да у корисничком програму за дати полином P пишемо нпр. Console.WriteLine("P = {0}", P); и добијемо исправно исписан израз полинома.

Комплетан кôд овог (као и свих других) примера може да се преузме са уводне странице овог курса.

Карацубин алгоритам¶

Из уобичајеног алгоритма за множење

лако можемо да израчунамо број операција које се изврше у овом алгоритму. Наредба у двострукој петљи се извршава \((deg(P) + 1) \cdot (deg(Q) + 1)\) пута, а у њој имамо по једно сабирање и множење. Означимо степене полинома \(P, Q\) редом са \(n, m\). Сада имамо да је број операција једнак \(f(n, m) = (n + 1) \cdot (m + 1)\), одакле за довољно велике \(n, m\) следи \(mn \leq f(n, m) \leq 2mn\). Користећи стандардну нотацију за сложеност алгоритма, овај закључак можемо да запишемо као \(Т(n, m) = \theta(mn)\). Једноставније речено, број операција (а тиме и време рада алгоритма) расте асимптотски истом брзином као и производ \(mn\).

Анатолиј Карацуба је 1960. године као студент Колмогорова дошао до идеје како да рекурзивним поступком смањи број операција при множењу полинома, када су степени \(m, n\) довољно велики. Да бисмо суштину идеје изразили што једноставније, претпоставимо да је

\[\begin{split}\begin{aligned} P(x) = p_{2n-1}x^{2n-1}+...+p_{2}x^2+ + p_1x+p_0\\ Q(x) = q_{2n-1}x^{2n-1}+...+q_{2}x^2+ + q_1x+q_0\\ \end{aligned}\end{split}\]

Тада полиноме \(P, Q\) можемо да запишемо и овако:

\[\begin{split}\begin{aligned} P(x) &= p_{2n-1}x^{2n-1}+...+p_{n}x^{n} + p_{n-1}x^{n-1}+...+p_{0}x^{0}\\ &= (p_{2n-1}x^{n-1}+...+p_{n})x^{n} + (p_{n-1}x^{n-1}+...+p_{0}x^{0})\\ &= P_1 x^{n} + P_2\\ \\ Q(x) &= q_{2n-1}x^{2n-1}+...+q_{n}x^{n} + q_{n-1}x^{n-1}+...+q_{0}x^{0}\\ &= (q_{2n-1}x^{n-1}+...+q_{n})x^{n} + (q_{n-1}x^{n-1}+...+q_{0}x^{0})\\ &= Q_1 x^{n} + Q_2\\ \end{aligned}\end{split}\]

Приметимо да су полиноми \(P_1, P_2, Q_1, Q_2\) степена \(n-1\), тј. имају по \(n\) коефицијената, дакле двоструко мање коефицијената него полиноми \(P\) и \(Q\). Даље имамо:

\[\begin{split}\begin{aligned} P \cdot Q &= (P_1 x^{n} + P_2) (Q_1 x^{n} + Q_2)\\ &= (P_1 \cdot Q_1)x^{2n} + (P_1 \cdot Q_2)x^n + (P_2 \cdot Q_1)x^n + P_2 \cdot Q_2\\ &= (P_1 \cdot Q_1)x^{2n} + (P_1 \cdot Q_2 + P_2 \cdot Q_1)x^n + P_2 \cdot Q_2\\ &= (P_1 \cdot Q_1)x^{2n} + ((P_1+P_2)\cdot(Q_1+Q_2) - P_1 \cdot Q_1 - P_2 \cdot Q_2)x^n + P_2 \cdot Q_2\\ &= R_1 x^{2n} + ((P_1+P_2)\cdot(Q_1+Q_2) - R_1 - R_2)x^n + R_2\\ \end{aligned}\end{split}\]

где је \(R_1 = P_1 \cdot Q_1, R_2 = P_2 \cdot Q_2\). На основу овога, производ \(P \cdot Q\), можемо да добијемо тако што израчунамо производе

\[\begin{split}\begin{aligned} R_1 &= P_1 \cdot Q_1\\ R_2 &= P_2 \cdot Q_2\\ R_3 &= (P_1+P_2)\cdot(Q_1+Q_2)\\ \end{aligned}\end{split}\]

уз додатни број операција, који је сразмеран са \(n\). Другим речима, проблем множења два полинома са низовима коефицијената дужине \(2n\) сведен је на три проблема истог типа, са низовима дужине \(n\). Због тога, за време извршавања алгоритма важи \(T(2n,2n)=3T(n,n)+\theta(n)\). Може се доказати (за доказ видети мастер теорему) да из ове рекурентне релације следи

\[T(n,m) = \Theta (max(n,m)^{\log_{2}3})\]

Ово значи да је за полиноме \(P\) и \(Q\), степена редом \(n\) и \(m\), потребно приближно \(N^{\log_2 3} \approx N^{1.58}\) операција за њихово множење Карацубиним алгоритмом, где је са \(N\) означен \(max(n, m)\).

На крају, ево и наше имплементације Карацубиног множења полинома:

Задатак¶

Упоредите Карацубин алгоритам за множење полинома са класичним множењем, тако што ћете у оба алгоритма да додате мерење времена. Испорбајте оба начина за полиноме различитих степена и покушајте да одредите за колико велик степен полинома Карацубин алгоритам почиње да буде бржи од класичног множења.

Садржај

1. Основни алгебарски алгоритми

2. Основни геометријски алгоритми

3. Основни алгоритми текста

4. Основни графовски алгоритми

5. Одабрани алгоритми и структуре података