Opened 7 years ago

# Performance of casting polynomials to polynomials over finite fields

Reported by: Owned by: afiori minor sage-6.4 performance FiniteField Polynomial Casting roed, jpflori Andrew Fiori N/A

### Description

One would expect the performance of casting the usual way (as in test 1 below) to be at least not much worse than test 2:

```sage: QQX=QQ['x']
sage: QP=Qp(3,30);
sage: R=QP.residue_field();
sage: RX=R['x'];
sage: prim=primes_first_n(1000)
sage: polysQQ = [ QQX(prim[i:i+30]) for i in range(1,900)]
sage: def test1(PR,l):
return [PR(P) for P in l];
....:
sage: def test2(PR,l):
return [PR([PR.base_ring()(coef) for coef in P.list()]) for P in l];
....:
sage: %timeit test1(RX,polysQQ)
1 loops, best of 3: 478 ms per loop
sage: %timeit test2(RX,polysQQ)
1 loops, best of 3: 230 ms per loop
```

Especially since the actual implementation of casting that is performed essentially reduces to converting to a list and casting as we do in test 2.

The problem is that the implementation of list->polynomial casting provided by Polynomial_template is very much not optimal, sufficiently so that two of the three implementing classes handle lists in their own init rather than passing through to polynomial template.

The polynomial->polynomial casting is then also inefficient as it converts the poly to a list and recalls init. In the original code this bypassed the optimized list implementations in the implementing class, this is what the current patch changes. The effect on performance is as follows:

```sage: %timeit test1(RX,polysQQ)
1 loops, best of 3: 219 ms per loop
```

There is still room for improvement, the current (and with patch) implementation will in most cases end up calling Polynomial_template.init twice, and likely also Polynomial.init twice, this is wasteful (even though the calls are largely no-ops). It would probably be better to, in addition to the currently proposed patch, special case casts from polynomials in the implementing classes the same way lists are done to avoid this.

### comment:1 Changed 7 years ago by afiori

• Authors set to Andrew Fiori

### comment:2 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

### comment:3 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3