Opened 13 months ago

Last modified 13 months ago

## #26015 new task

# Accelerate expansion for padics in mixed extensions

Reported by: | caruso | Owned by: | |
---|---|---|---|

Priority: | major | Milestone: | sage-8.4 |

Component: | padics | Keywords: | |

Cc: | roed, saraedum | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | #23218 | Stopgaps: |

### 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.

**Note:**See TracTickets for help on using tickets.

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