Opened 4 years ago

# Accelerate expansion for padics in mixed extensions

Reported by: Owned by: Xavier Caruso major sage-8.4 padics padicBordeaux David Roe, Julian Rüth N/A #23218

### Description

Currently the method `expansion` is very slow for mixed extensions with a large absolute index of ramification.

```sage: K.<a> = Qq(3^3,10)
sage: S.<x> = K[]
sage: Z = (1+x)^27
sage: L.<pi> = K.extension(Z^2 + Z + 1)
sage: elt = L.random_element()
sage: %time _ = list(elt.expansion())
CPU times: user 2.86 s, sys: 4 ms, total: 2.87 s
Wall time: 2.87 s
```

I had a look at the code and it turns out that the current implementation performs `prec` (the relative precision) shifts by `-1`. I think that it would be possible to shift only `prec/e` times by `-e` (where `e` is the absolute index of ramification) and then roughly save a factor `e` in the complexity.

### comment:1 Changed 4 years ago by Xavier Caruso

In order to illustrate my point, I post a code (written in pure python) which is a little bit faster than the current implementation:

```def my_expansion(elt):
if elt.valuation() != 0:
raise NotImplementedError
parent = elt.parent()
e = parent.absolute_e()
prec = elt.precision_absolute()
curprec = 0
pie = parent.uniformizer_pow(e)
expansion = [ ]
while curprec < prec:
poly = elt._poly_rep()
expansion += [ poly[i].residue() for i in range(min(e,prec-curprec)) ]
elt //= pie
curprec += e
return expansion
```