Opened 11 years ago

Closed 11 years ago

# Obtaining coefficients of polynomials over finite fields is extremely slow

Reported by: Owned by: johanbosman tbd major sage-4.7.2 performance polynomials, finite fields sage-4.7.2.alpha3 Johan Bosman, Simon King Simon King, Johan Bosman N/A #11685

If we have a polynomial over a finite field and we want to obtain its coefficients, then there seems to be a lot of conversion overhead. It is a lot slower than multiplying such polynomials:

```sage: K.<a> = GF(5^3)
sage: P = PolynomialRing(K, 'x')
sage: f = P.random_element(100)
sage: timeit('f.list()')
5 loops, best of 3: 115 ms per loop
sage: timeit('f * f')
625 loops, best of 3: 794 µs per loop
```

If, on the other hand, we do not use NTL, then we can obtain the coefficient list without any delays, though in that case multiplication is a lot slower:

```sage: P = PolynomialRing(K, 'x', implementation='not NTL')
sage: f = P(f)
sage: timeit('f.list()')
625 loops, best of 3: 968 ns per loop
sage: timeit('f * f')
25 loops, best of 3: 12.3 ms per loop
```

This performance issue occurs in both 4.7 and 4.7.1.rc1.

Apply

to the Sage library.

### Changed 11 years ago by johanbosman

To be used after applying the fix of #11685

### comment:1 Changed 11 years ago by johanbosman

• Authors set to Johan Bosman
• Dependencies set to #11685
• Status changed from new to needs_review

The uploaded patch improves the speed slightly:

```sage: K.<a> = GF(5^3)
sage: P = PolynomialRing(K, 'x')
sage: f = P.random_element(100)
sage: timeit('f.list()')
125 loops, best of 3: 2.92 ms per loop
```

A real fix would of course be an NTL wrapper for finite fields, which is a huge project that may not get finished soon.

### comment:2 Changed 11 years ago by SimonKing

The code of `list()` currently does `[self[i] for i in range(celement_len(&self.x, _parent))]`. You improved the `__getitem__` method.

But still, calling the `__getitem__` method over and over again seems to create a lot of overhead. I am sure that NTL provides a method that returns the list of coefficients. So, why not use that instead?

And if that is impossible, note that most lines of `__getitem__` are concerned with preparatory steps, namely:

```        cdef ZZ_pE_c c_pE
cdef cparent _parent

_parent = get_cparent(self._parent)
_parent[0].restore()
c_pE = ZZ_pEX_coeff(self.x, i)

K = self._parent.base_ring()
```

I am pretty sure that it is possible to do these preparatory steps only once. Hence, I suggest to be a bit more "explicit" in the `list()` method, rather than calling `self[i]`.

Of course, in addition to that, one should also keep your improvement of `__getitem__`.

### comment:3 Changed 11 years ago by johanbosman

The problem is that Sage uses NTL for polynomials over finite fields, but not for elements of finite fields. So simply using NTL's list method wouldn't work (unfortunately). I'll try to see whether a direct list() method will improve speed further. Though I suspect that 99% of the running time goes into

```K(ZZ_pE_c_to_list(c_pE))
```

so that the gain will be negligible.

### comment:4 Changed 11 years ago by johanbosman

• Status changed from needs_review to needs_info

### comment:5 Changed 11 years ago by SimonKing

I already created a patch for the more direct approach. I am now running doc tests. The additional speed gain in your example is something like 20%.

### comment:6 Changed 11 years ago by SimonKing

• Authors changed from Johan Bosman to Johan Bosman, Simon King
• Status changed from needs_info to needs_review

At least the tests in devel/sage/doc pass. Hence, I have already posted my patch. Here are the timings:

```sage: K.<a> = GF(5^3)
sage: P = PolynomialRing(K, 'x')
sage: f = P.random_element(100)
```

#11685 only:

```sage: timeit('f.list()')
5 loops, best of 3: 79.9 ms per loop
```

```sage: timeit('f.list()')
125 loops, best of 3: 2.36 ms per loop
```

All patches:

```sage: timeit('f.list()')
125 loops, best of 3: 2.03 ms per loop
```

OK, that's only a gain of 14%. But I had one run where it took 2.42 ms with one patch and 1.98 ms with both patches (that's why I stated 20% in my previous post).

Anyway, does the second patch make sense? I am currently running doc tests, so that probably I can review both #11685 and your patch from here.

### comment:7 Changed 11 years ago by SimonKing

• Reviewers set to Simon King

I already stated that your patch improves the `__getitem__` method considerably, and I can confirm the resulting speedup in `list()`.

The long doctests of both devel/sage-main/doc and devel/sage-main/sage pass. Hence, I give your patch a positive review.

Of course I can not review my own patch. So, I'd appreciate if you could have a look on it.

### comment:8 Changed 11 years ago by johanbosman

I've been travelling all day; I'll start reviewing right now. ;)

### comment:9 follow-up: ↓ 10 Changed 11 years ago by johanbosman

• Status changed from needs_review to needs_work

There's a declaration

```cdef ZZ_pE_c c_pE
```

in your code but it isn't used. So you might as well leave it out. ;).

### comment:10 in reply to: ↑ 9 Changed 11 years ago by SimonKing

There's a declaration

```cdef ZZ_pE_c c_pE
```

in your code but it isn't used. So you might as well leave it out. ;).

Right. That is a copy-and-paste error.

### Changed 11 years ago by SimonKing

More direct coefficient list creation for NTL polys over finite fields. Apply after Johan's patch

### comment:11 Changed 11 years ago by SimonKing

• Status changed from needs_work to needs_review

I just updated my patch. So, "needs review" again.

### comment:12 Changed 11 years ago by johanbosman

• Reviewers changed from Simon King to Simon King, Johan Bosman
• Status changed from needs_review to positive_review

The code looks okay now, all doctests pass, and the documentation builds fine.

### comment:13 follow-up: ↓ 14 Changed 11 years ago by leif

• Description modified (diff)

Make someone review #11685... ;-)