CoCoA » CoCoA-5

The function SquaredPoly should be of quadratic complexity, so doubling the degree should increase computation by about a factor of 4. Instead the time increases by a rather larger factor. Here is some sample code:

Define SquaredPoly(V)
  L := Len(V);
  If Len(V) = 0 Then Return V; EndIf;
  N := 0;
  For I := L To 1 Step -1 Do If V[I] <> 0 Then N := I; Break; EndIf; EndFor;
  If N = 0 Then Return [0]; EndIf;
  N := N-1;
  Q := NewList(2*N+1, 0);
  For I := 0 To N-1
    Do For J := I+1 To N
      Do Q[I+J+1] := Q[I+J+1] + V[I+1]*V[J+1];
    EndFor;
  EndFor;
  For I := 1 To 2*N+1 Do Q[I] := 2*Q[I]; EndFor;
  For I := 0 To N Do Q[2*I+1] := Q[2*I+1] + V[I+1]^2; EndFor;
  Return Q;
EndDefine;

Define L2F(L)
  TopLevel x;
  Return Sum([L[I]*x^(I-1) | I In 1..Len(L)]);
EndDefine; -- L2F

Define RndPoly(D)
  TopLevel CurrentRing;

  Return [Rand(-99,99)*one(CurrentRing) | I In 0..D];
EndDefine; -- RndPoly

Use ZZ/(29641)[x];
PolyDeg := 500;
NumberOfTests := 3;
PolyList := [RndPoly(PolyDeg*2^I) | I In 0..NumberOfTests-1];

For I := 1 To NumberOfTests Do
  t0 := CpuTime();
  S := SquaredPoly(PolyList[I]);
  delta_t := DecimalStr(CpuTime()-t0);
  PrintLn "SquaredPoly, polinomio ", I, ": ", delta_t;
  F := L2F(PolyList[I]);
  t0 := CpuTime();
  S := F^2;
  delta_t := DecimalStr(CpuTime()-t0);
  PrintLn "Quadrato CoCoA, polinomio ", I, ": ", delta_t;
EndFor;