## Slug #230

### More curiously slow code -- squaring a polynomial

Status:
New
Priority:
Normal
Assignee:
-
Category:
-
Target version:
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 Bigattiover 4 years ago

• Target version set to CoCoA-5.1.0 Easter14

#### #2 Updated by John Abbottover 4 years ago

• Target version changed from CoCoA-5.1.0 Easter14 to CoCoA-5.?.?

Also available in: Atom PDF