Výpočet vzroců pro algoritmus Toom - k

k=3;

(* polynomy *)
f=Sum[(Subscript[a, i])*x^i,{i,0,k-1}]
g=Sum[(Subscript[b, i])*x^i,{i,0,k-1}]

(* modularni reprezentace v bodech -(k-1),...,k-1 *)
frep=Table[f/.x->u,{u,-(k-1),k-1}]
grep=Table[g/.x->u,{u,-(k-1),k-1}]

(* soucin v modularni reprezentaci *)
hrep=frep*grep

(* rekonstrukce soucinu fg *)
t=Table[{i-k,hrep[[i]]},{i,1,2*k-1}];
InterpolatingPolynomial[t,x] 
Collect[%,x]
(* vsimnete si, ze ve vyjadreni koeficientu se skutecne vyskytuje jen pet soucinu; i kdyz to tak nevypada, ty zlomky se pozerou *)

(* kontrola ze to je opravdu soucin *)
Expand[%]