Opened 2 years ago

Last modified 17 months ago

#23470 new defect

Creation of polynomials over finite fields is quite slow

Reported by: caruso Owned by:
Priority: major Milestone: sage-8.1
Component: finite rings Keywords: sd87, padicIMA
Cc: jpflori Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:


On my laptop, it takes almost 1 second to create a polynomial of degree 10000 over F_125:

    sage: k = GF(5^3)
    sage: S.<x> = k[]
    sage: L = [ k.random_element() for _ in range(10000) ]
    sage: %time f = S(L)
    CPU times: user 764 ms, sys: 4 ms, total: 768 ms
    Wall time: 767 ms

while computing its square takes only 40ms:

    sage: %time g = f*f
    CPU times: user 32 ms, sys: 8 ms, total: 40 ms
    Wall time: 39.6 ms

Change History (3)

comment:1 Changed 2 years ago by jpflori

This is already way too slow:

sage: K = GF(125)
sage: R = K['t']
sage: L = [K.random_element() for _ in range(10**5)]
sage: %timeit [c.polynomial() for c in L]
1 loop, best of 3: 7.32 s per loop
sage: KK = GF(125, impl="pari_ffelt")
sage: RR = KK['t']
sage: LL = [KK.random_element() for _ in range(10**5)]
sage: %timeit [c.polynomial() for c in LL]
1 loop, best of 3: 13.7 s per loop

comment:2 Changed 2 years ago by jpflori

There is a lot of python overhead to do magic conversion btw different C implementations. So unless we implement special methods to go back and forth specific implementations it looks hard to tackle that one in a generic way.

comment:3 Changed 17 months ago by roed

  • Keywords padicIMA added
Note: See TracTickets for help on using tickets.