Množenje polinoma

Nije rijetkost da se natjecateljski zadatak može svesti na problem množenja polinoma.
Školski algoritam je vrlo jednostavan ali i spor - složenost mu je .

Postoje i mnogo bolji pristupi i cilj ovog članka je upoznati čitatelja s njima.
Nakon formalizacije problema opisat ćemo Karatsubin algoritam složenosti .
Zatim ćemo vidjeti kako pomnožiti dva polinoma uporabom interpolacije što će biti osnovna ideja za dva algoritma složenosti sa sličnim temeljima: množenje koristeći FFT, odnosno NTT.

Svi ovi algoritmi su "podijeli-pa-vladaj" algoritmi (Divide and conquer algorithms) pa ovaj članak može poslužiti i za upoznavanje (kroz primjere) s takvim pristupom rješavanju problema.

U nastavku ćemo za polinome koristiti neku od sljedećih notacija (sve ih smatramo jednakima):

Problem

Na ulazu imamo dva polinoma i istog stupnja , a izlaz je polinom stupnja :

Školski algoritam u C-u je jednostavan i jasno ilustrira problem:

void mnozi(int* a, int* b, int* c, int n) {
  for (int i = 0; i <= 2*n; ++i) {
    c[i] = 0;
  }
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= n; ++j) {
      c[i+j] += a[i] * b[j];
    }
}

Karatsubin algoritam

Problem rješavamo rekurzivno:

Jedno množenje smo kompenzirali zbrajanjima (koja su "jeftina") te sada imamo tri množenja upola manjih polinoma koja rješavamo rekurzivno, a rezultate kombiniramo prema posljednjem izrazu za .
Pažljivom analizom dolazimo do složenosti ovog algoritma, što je približno .
Ako vas zanima kako elegantno izračunati složenost ovog i sličnih algoritama pručite Master theorem.

Množenje polinoma uporabom interpolacije polinoma

Poznato je da parova takvih da za jednoznačno određuju polinom stupnja takav da . Kažemo da iz evaluacija polinoma u točaka možemo rekonstruirati polinom.

Nama je u problemu množenja polinoma nepoznat polinom stupnja . Ako pronađemo vrijednosti tog polinoma u točaka možemo iz njih rekonstruirati cijeli polinom!
Kako pronaći vrijednost polinoma u nekoj točki ? Budući da se radi o umnošku polinoma i dovoljno je evaluirati oba polinoma u točki i pomnožiti dobivene vrijednosti.

Algoritam se dakle sastoji od 3 koraka:

Sve je to lijepo i krasno, no već prvi korak ne znamo napraviti u složenosti boljoj od .
Netko je skužio da se evaluacija polinoma u hrpi točaka može napraviti brže ako su točke odabrane prema određenim pravilima. I to nije sve, treći korak se u tom slučaju isto može svesti na evaluaciju polinoma sličnog skupa točaka. Drugi korak je očito linearan, pa ovo zvuči obećavajuće.
Upoznajmo se najprije s brzim postupkom evaluacije polinoma u takvim točkama.

Evaluacija polinoma u hrpi točaka (transformacija)

Algoritam koji ćemo u ovom dijelu proučiti uzima polinom , prirodan broj i .
Algoritam vraća vrijednosti polinoma u točaka: , , .. , .
Zgodno je vrijednosti dobivene evaluacijom zapisati u obliku polinoma stupnja , tako da vrijednost evaluacije u točki stoji uz . U tom slučaju možemo reći da algoritam vraća novi polinom, i tada govorimo o transformaciji polinoma. U ostatku ovog članka kad kažemo transformacija mislimo na ovaj algoritam.

Matematički, transformacija koju radimo je:

Dodat ćemo još jedan uvjet koji mora zadovoljavati (ne pitajte zašto, barem ne zasad): . Ako ste upravo pomislili da uvjet nema previše smisla ne zaboravite da se nismo ograničili na realne brojeve kod odabira .

Kako brzo izračunati ovu transformaciju?
Upoznat ćemo se s varijantom Cooley-Tukey algoritma koja brzo izračunava ovu transformaciju kada je potencija broja .

Na ulazu su dakle , i polinom , a na izlazu je transformirani polinom .

Algoritam je rekurzivan:

Složenost algoritma je .

Množenje koristeći brzu Fourieovu transformaciju (FFT)

Ovaj algoritam nam kaže da umnožak polinoma i možemo zapisati kao:

gdje je :

Primjetite sličnosti s već spomenutim množenjem polinoma uporabom interpolacije.

Primjetite i da su vrijednosti ovdje kompleksni brojevi te da vrijedi .
Možemo primjeniti algoritam iz prethodnog poglavlja za brzo izračunavanje transformacije.
Činjenica da transformaciju znamo brzo izračunati samo za slučajeve kad je potencija broja 2 ne predstavlja veliki problem, dovoljno je za uzeti prvu sljedeću potenciju broja 2 koja nije manja od .
Sve ovakve i slične brze implementacije DFT-a nazivaju se zajedničkim imenom brze Fourieove transformacije (FFT).

Valja napomenuti da pri implementaciji ovog algoritma i transformacije treba biti svjestan oblika broja i ne računati direktno njegove potencije (kako bi se očuvala preciznost) već koristiti Eulerov identitet koji kaže da za bilo koji realan vrijedi:
.

Složenost ovog algoritma množenja polinoma je .

Množenje polinoma nad prostim poljima koristeći NTT (Number theoretic transform)

Nedostatak DFT-a je (barem za nas) to što koristi realne odnosno kompleksne brojeve.
Ako radimo s polinomima nad konačnim poljima to ponekad možemo izbjeći. Pretpostavimo da radimo s konačnim poljem tj. sve operacije nad brojevima provodimo modulo gdje je prost broj.

Analogno DFT-u, umnožak polinoma i stupnja možemo pisati kao:

gdje je :

Za izračunavanje transformacije možemo iskoristiti već opisani algoritam, s tim da sve operacije provodimo modulo . Primjetite da smo sada dobili dodatan uvjet za , on mora biti djelitelj od . Uz stare zahtjeve da nije manji od te da mora biti potencija broja 2, pronalaženje pravog može postati nemoguće. To je upravo i glavna mana NTT-a, jer je sada jedini slučaj gdje ga možemo iskoristiti slučaj kada je prost broj oblika .
Zapravo, moguće je i češće, ali to zahtjeva modificiranje opisanog algoritma za izračunavanje transformacije, glavna ideja ostaje ista ali ulazni niz ne rastavljamo konstantno na dva jednaka dijela. Oni koje to više zanima neka slobodno eksperimentiraju.

Zaključak

Pošli smo od problema množenja polinoma, no treba napomenuti da se FFT koristi ponajviše u računalnom procesiranju raznih signala (slike, zvuka..).
Kad govorimo o množenju polinoma, klasična primjena je množenje velikih brojeva (zapisujemo ih kao polinome u bazi 10 ili nekoj većoj/manjoj bazi).

FFT je svakako bolji izbor od Karatsubinog algoritma kad govorimo o brzini, no nedostatak mu je preciznost jer smo primorani koristiti realni tip podatka pri implementaciji.
Uz preciznost, prednost Karatsubinog algoritma je i mogućnost množenja polinoma čak i kad dijeljenje nije definirano (npr. modulo 24).

Trebamo napomenuti da se NTT može iskoristiti čak i kad ne želimo eksplicitno rezultat modulo prost . Dovoljno je uzeti veći od najveće vrijednosti članova rezultantnog polinoma i pokrenuti algoritam. Nekad to nije praktično jer smo obično ograničeni 32-bitnim ili 64-bitnim cjelobrojnim tipom podatka. Tada možemo nekoliko puta izvršiti množenje, svaki puta modulo različit prost broj . Odabrani prosti brojevi mogu biti proizvoljno mali ali njihov umnožak mora biti veći od najveće vrijednosti članova rezultatntnog polinoma. Vrijednost člana rezultata modulo (tj. pravu vrijednost rezultata) možemo zatim izračunati koristeći Kineski teorem o ostacima (CRT).

Zadaci za vježbu

http://www.spoj.com/problems/VFMUL/
http://www.spoj.com/problems/LPRIME/
http://www.spoj.com/problems/MAXMATCH/
http://codeforces.com/gym/100524 (Zadatak D)
http://icpc.baylor.edu/download/worldfinals/problems/icpc2015.pdf (Zadatak J)

© 2016. Ivan Katanić Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License