program test;
uses
Math;
type
TPolynomial = class
private
FCoeff: array of Double;
procedure SetCoeff(Index: Integer; Value: Double);
function GetCoeff(Index: Integer): Double;
function GetDegree: Integer;
public
constructor Create(Degree: Integer);
constructor CreateFromArray(const CoeffArray: array of Double);
function Add(const B: TPolynomial): TPolynomial;
function Subtract(const B: TPolynomial): TPolynomial;
function Multiply(const B: TPolynomial): TPolynomial;
function Equals(const B: TPolynomial): Boolean; reintroduce;
function Evaluate(X: Double): Double;
function LowerPart(D: Integer): TPolynomial;
function UpperPart(D: Integer): TPolynomial;
function Shift(D: Integer): TPolynomial;
procedure WritePoly(VarChar: Char = 'x');
property Coeff[Index: Integer]: Double read GetCoeff write SetCoeff;
property Degree: Integer read GetDegree;
end;
constructor TPolynomial.Create(Degree: Integer);
begin
if Degree < 0 then
Degree := 0;
SetLength(FCoeff, Degree + 1);
end;
constructor TPolynomial.CreateFromArray(const CoeffArray: array of Double);
var
I: Integer;
begin
SetLength(FCoeff, Length(CoeffArray));
for I := 0 to High(CoeffArray) do
FCoeff[I] := CoeffArray[I];
end;
function TPolynomial.GetCoeff(Index: Integer): Double;
begin
Result := FCoeff[Index];
end;
procedure TPolynomial.SetCoeff(Index: Integer; Value: Double);
begin
FCoeff[Index] := Value;
end;
function TPolynomial.GetDegree: Integer;
begin
Result := High(FCoeff);
end;
function TPolynomial.Add(const B: TPolynomial): TPolynomial;
var
MaxDegree, I: Integer;
begin
MaxDegree := Max(Self.Degree, B.Degree);
Result := TPolynomial.Create(MaxDegree);
for I := 0 to MaxDegree do
Result.Coeff[I] := Self.Coeff[I] + B.Coeff[I];
end;
function TPolynomial.Subtract(const B: TPolynomial): TPolynomial;
var
MaxDegree, I: Integer;
begin
MaxDegree := Max(Self.Degree, B.Degree);
Result := TPolynomial.Create(MaxDegree);
for I := 0 to MaxDegree do
Result.Coeff[I] := Self.Coeff[I] - B.Coeff[I];
end;
function TPolynomial.Multiply(const B: TPolynomial): TPolynomial;
var
ResultDegree, I, J: Integer;
begin
ResultDegree := Self.Degree + B.Degree;
Result := TPolynomial.Create(ResultDegree);
for I := 0 to Self.Degree do
for J := 0 to B.Degree do
Result.Coeff[I + J] := Result.Coeff[I + J] + (Self.Coeff[I] * B.Coeff[J]);
end;
function TPolynomial.Equals(const B: TPolynomial): Boolean;
var
I: Integer;
begin
if Self.Degree <> B.Degree then
Exit(False);
for I := 0 to Self.Degree do
begin
if Self.Coeff[I] <> B.Coeff[I] then
Exit(False);
end;
Result := True;
end;
function TPolynomial.Evaluate(X: Double): Double;
var
I: Integer;
begin
Result := 0;
for I := Self.Degree downto 0 do
Result := Result * X + Self.Coeff[I];
end;
function TPolynomial.LowerPart(D: Integer): TPolynomial;
var
I: Integer;
begin
Result := TPolynomial.Create(D - 1);
for I := 0 to D - 1 do
Result.Coeff[I] := Self.Coeff[I];
end;
function TPolynomial.UpperPart(D: Integer): TPolynomial;
var
I: Integer;
begin
Result := TPolynomial.Create(Self.Degree - D);
for I := 0 to Self.Degree - D do
Result.Coeff[I] := Self.Coeff[I + D];
end;
function TPolynomial.Shift(D: Integer): TPolynomial;
var
I: Integer;
begin
Result := TPolynomial.Create(Self.Degree + D);
for I := 0 to Self.Degree do
Result.Coeff[I + D] := Self.Coeff[I];
end;
procedure TPolynomial.WritePoly(VarChar: Char = 'x');
var
I: Integer;
begin
for I := 0 to Degree do
Write(FCoeff[I]:0:2, VarChar, '^', I, ' ');
WriteLn;
end;
function Karatsuba(const f, g: TPolynomial): TPolynomial;
var
temp1, temp2, h1, h2, h3, h: TPolynomial;
d: Integer;
begin
// Базовый случай: если один из многочленов равен нулю
if (f.Degree = 0) and (f.Coeff[0] = 0) or
(g.Degree = 0) and (g.Coeff[0] = 0) then
begin
Result := TPolynomial.Create(0);
Result.Coeff[0] := 0;
Exit;
end;
// Базовый случай: оба многочлена - константы
if (f.Degree = 0) and (g.Degree = 0) then
begin
Result := TPolynomial.Create(0);
Result.Coeff[0] := f.Coeff[0] * g.Coeff[0];
Exit;
end;
// Получаем максимальную степень и вычисляем d
d := Ceil(Max(f.Degree, g.Degree) / 2);
// Разделяем многочлены на нижнюю и верхнюю части
temp1 := f.LowerPart(d);
temp2 := g.LowerPart(d);
h1 := Karatsuba(temp1, temp2); // flow * glow
temp1 := f.UpperPart(d);
temp2 := g.UpperPart(d);
h2 := Karatsuba(temp1, temp2); // fup * gup
// Вычисляем (flow + fup) * (glow + gup)
temp1 := f.LowerPart(d).Add(f.UpperPart(d)); // flow + fup
temp2 := g.LowerPart(d).Add(g.UpperPart(d)); // glow + gup
h3 := Karatsuba(temp1, temp2);
// Объединяем результаты
temp1 := h3.Subtract(h1).Subtract(h2);
temp2 := temp1.Shift(d);
h := h1.Add(temp2);
temp2 := h2.Shift(2 * d);
Result := h.Add(temp2);
end;
procedure TestKaratsuba;
var
a, b, c: TPolynomial;
begin
a := TPolynomial.CreateFromArray([9, 7, 4, 8, 9]);
b := TPolynomial.CreateFromArray([8, 4, 2, 1, 6, 5, 9, 4]);
WriteLn('Polynomial a:');
a.WritePoly('x');
WriteLn('Polynomial b:');
b.WritePoly('x');
c := Karatsuba(a, b);
WriteLn('Result of Karatsuba multiplication (c):');
c.WritePoly('x');
end;
procedure RunTests;
var
a, b, c: TPolynomial;
begin
a := TPolynomial.CreateFromArray([1]);
b := TPolynomial.CreateFromArray([1]);
c := Karatsuba(a, b);
Assert(c.Equals(TPolynomial.CreateFromArray([1])), 'Test 1 Failed');
a := TPolynomial.CreateFromArray([2]);
b := TPolynomial.CreateFromArray([3]);
c := Karatsuba(a, b);
Assert(c.Equals(TPolynomial.CreateFromArray([6])), 'Test 2 Failed');
a := TPolynomial.CreateFromArray([1, 1]); // x + 1
b := TPolynomial.CreateFromArray([2, 1]); // x + 2
c := Karatsuba(a, b);
Assert(c.Equals(TPolynomial.CreateFromArray([2, 3, 1])), 'Test 3 Failed'); // 2 + 3x + 1x^2
a := TPolynomial.CreateFromArray([1, 2, 3]); // 1 + 2x + 3x^2
b := TPolynomial.CreateFromArray([4, 5]); // 4 + 5x
c := Karatsuba(a, b);
Assert(c.Equals(TPolynomial.CreateFromArray([4, 13, 22, 15, 0])), 'Test 4 Failed'); // 4 + 13x + 22x^2 + 15x^3 + 0x^4
{
The result of multiplying two polynomials is calculated as follows:
a(x) = 1 + 2x + 3x^2
b(x) = 4 + 5x
The multiplication is done using the distributive property:
1. Multiply 1 by (4 + 5x):
1 * (4 + 5x) = 4 + 5x
2. Multiply 2x by (4 + 5x):
2x * (4 + 5x) = 8x + 10x^2
3. Multiply 3x^2 by (4 + 5x):
3x^2 * (4 + 5x) = 12x^2 + 15x^3
Combining these results gives us:
c(x) = (4 + 5x) + (8x + 10x^2) + (12x^2 + 15x^3)
Now, summing the like terms:
- Constant: 4
- x terms: 5x + 8x = 13x
- x^2 terms: 10x^2 + 12x^2 = 22x^2
- x^3 terms: 15x^3
Thus, the final result is:
c(x) = 4 + 13x + 22x^2 + 15x^3
Note that the degree of the resulting polynomial can be equal to the sum of the degrees of the original polynomials:
Maximum degree of a(x) = 2
Maximum degree of b(x) = 1
Therefore, the maximum degree of c(x) can be 2 + 1 = 3.
We include 0x^4 for completeness, so the final result can be represented as:
c = TPolynomial.CreateFromArray([4, 13, 22, 15, 0])
}
a := TPolynomial.CreateFromArray([0]); // 0
b := TPolynomial.CreateFromArray([2, 1]); // 2 + x
c := Karatsuba(a, b);
Assert(c.Equals(TPolynomial.CreateFromArray([0])), 'Test 5 Failed'); // 0
WriteLn('All tests passed!');
end;
begin
RunTests;
TestKaratsuba;
end.
Recent
