program untitled;
uses crt,math,polynomial;
function Karatsuba(f,g:TPolynomial):TPolynomial;
var temp1,temp2:TPolynomial;
h,h1,h2,h3:TPolynomial;
k,m,n,d:integer;
begin
if f.deg < g.deg then
begin
temp1 := f;
f := g;
g := temp1;
end;
//Base case f = 0 or g = 0
if ((f.deg = 0)and(f.coeff[0] = 0)) or ((g.deg = 0)and(g.coeff[0] = 0)) then
begin
h := makePolynomial(0);
h.coeff[0] := 0;
Karatsuba := h;
Exit
end;
//Base case both polynomials are constant
if g.deg = 0 then
begin
h := makePolynomial(f.deg);
for k := 0 to h.deg do
h.coeff[k] := g.coeff[0] * f.coeff[k];
Karatsuba := h;
Exit
end;
begin
//Checking which polynomial has maximum degree
d := max(f.deg,g.deg);
//Calculating ceiling of half of max degree
d := (d + 1) div 2;
//Creating temporary polynomial which stores lower part of polynomial f
m := min(d ,f.deg + 1);
temp1 := makePolynomial(m-1);
for k := 0 to m - 1 do
temp1.coeff[k] := f.coeff[k];
//Creating temporary polynomial which stores lower part of polynomial g
n := min(d,g.deg + 1);
temp2 := makePolynomial(n-1);
for k := 0 to n - 1 do
temp2.coeff[k] := g.coeff[k];
//Recursive call of function Karatsuba to calculate product flow * glow
h1 := Karatsuba(temp1,temp2);
//Creating temporary polynomial which stores upper part of polynomial f
temp1 := makePolynomial(ord(f.deg - m >= 0)*(f.deg - m));
temp1.coeff[0] := 0;
for k := 0 to f.deg - m do
temp1.coeff[k] := f.coeff[k + m];
//Creating temporary polynomial which stores upper part of polynomial g
temp2 := makePolynomial(ord(g.deg - n >= 0)*(g.deg - n));
temp2.coeff[0] := 0;
for k := 0 to g.deg - n do
temp2.coeff[k] := g.coeff[k+n];
//Recursive call of function Karatsuba to calculate product fup * gup
h2 := Karatsuba(temp1,temp2);
//Creating temporary polynomial to store lower part of polynomial g
temp1 := makePolynomial(n-1);
for k:= 0 to n - 1 do
temp1.coeff[k] := g.coeff[k];
//Creating temporary polynomial to store upper part of polynomial g
temp2 := makePolynomial(ord(g.deg - n >= 0)*(g.deg - n));
for k := 0 to n - 1 do
temp1.coeff[k] := g.coeff[k];
temp2.coeff[0] := 0;
for k := 0 to g.deg - n do
temp2.coeff[k] := g.coeff[k+n];
//Creating polynomial glow + gup
h3 := AddPolynomials(temp1,temp2);
//Set coefficients of temporary polynomial to coefficients of lower part of polynomial f
for k := 0 to m - 1 do
temp1.coeff[k] := f.coeff[k];
//Creating temporary polynomial which stores upper part of polynomial f
temp2 := makePolynomial(ord(f.deg - m >= 0)*(f.deg - m));
temp2.coeff[0] := 0;
for k := 0 to f.deg - m do
temp2.coeff[k] := f.coeff[k+m];
//Creating polynomial flow + fup
temp1 := AddPolynomials(temp1,temp2);
//Recursive call of function Karatsuba to calculate product (flow + fup)*(glow + gup)
h3 := Karatsuba(temp1,h3);
//Merging results , calculation middle terms
d := min(m,n);
temp1 := SubtractPolynomials(h3,h1);
temp1 := SubtractPolynomials(temp1,h2);
temp2 := makePolynomial(temp1.deg+d);
for k := 0 to temp1.deg do
temp2.coeff[k + d] := temp1.coeff[k];
for k := 0 to d - 1 do
temp2.coeff[k] := 0;
//Adding lower part and middle part
h := AddPolynomials(h1,temp2);
//Creating upper part
temp2 := makePolynomial(h2.deg + 2*d);
for k := 0 to h2.deg do
temp2.coeff[k + 2*d] := h2.coeff[k];
for k := 0 to 2*d - 1 do
temp2.coeff[k] := 0;
//Adding upper part to current result
h := AddPolynomials(h,temp2);
Karatsuba := h;
end;
end;
var f:text;
k,n,m:integer;
a,b,c:TPolynomial;
BEGIN
Assign(f,'input.txt');
Reset(f);
ReadLn(f,n);
a := makePolynomial(n);
k := n;
while not Eoln(f) do
begin
Read(f,a.coeff[k]);
k:=k-1;
end;
ReadLn(f,m);
b := makePolynomial(m);
k := m;
while not Eoln(f) do
begin
Read(f,b.coeff[k]);
k:=k-1;
end;
WriteLn('Polynomial a');
WriteLn(a.deg);
writePolynomial(a,'x');
WriteLn('Polynomial b');
WriteLn(b.deg);
writePolynomial(b,'x');
c := Karatsuba(a,b);
WriteLn('Polynomial c');
WriteLn(c.deg);
writePolynomial(c,'x');
Close(f);
END.