Slug #230
More curiously slow code -- squaring a polynomial
Start date:
21 Sep 2012
Due date:
% Done:
0%
Estimated time:
Description
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;
History
#1 Updated by Anna Maria Bigatti over 10 years ago
- Target version set to CoCoA-5.1.0 Easter14
#2 Updated by John Abbott about 10 years ago
- Target version changed from CoCoA-5.1.0 Easter14 to CoCoA-5.?.?