Opened 8 years ago
Closed 8 years ago
#15193 closed enhancement (fixed)
Add _pari_() method to Factorization
Reported by: | pbruin | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.12 |
Component: | factorization | Keywords: | pari |
Cc: | Merged in: | sage-5.12.rc1 | |
Authors: | Peter Bruin | Reviewers: | Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Various PARI functions, such as Zn_issquare
(cf. #13596), accept an integer argument in factored form. To profit from this, it is convenient to add a method Factorization._pari_()
to convert a Sage Factorization
to a PARI matrix.
Apply: 15193-Factorization-pari-chain.patch (requires >= 5.12.beta5 or #15124)
Attachments (2)
Change History (12)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 8 years ago by
comment:3 in reply to: ↑ 2 Changed 8 years ago by
Replying to mathzeta2:
instead of
reduce
we can use something faster:from itertools import chain ... #line 914: entries = init + tuple(chain.from_iterable(self))
It sounds plausible that this is indeed faster; have you got some timings?
comment:4 Changed 8 years ago by
Yes, for me it is faster for factorizations with at least (about) 10 factors. Some non-scientific timings:
sage: import itertools sage: A = factor(prod(primes(2))) sage: %timeit reduce(lambda f, g: f+g, A, ()) 1000000 loops, best of 3: 830 ns per loop sage: %timeit tuple(itertools.chain(*A)) 100000 loops, best of 3: 2.26 us per loop sage: %timeit tuple(itertools.chain.from_iterable(A)) 100000 loops, best of 3: 1.86 us per loop sage: B = factor(prod(primes(200))) sage: %timeit reduce(lambda f, g: f+g, B, ()) 10000 loops, best of 3: 33.2 us per loop sage: %timeit tuple(itertools.chain(*B)) 10000 loops, best of 3: 20.8 us per loop sage: %timeit tuple(itertools.chain.from_iterable(B)) 10000 loops, best of 3: 20.1 us per loop sage: C = factor(prod(primes(2000))) sage: %timeit reduce(lambda f, g: f+g, C, ()) 1000 loops, best of 3: 418 us per loop sage: %timeit tuple(itertools.chain(*C)) 10000 loops, best of 3: 119 us per loop sage: %timeit tuple(itertools.chain.from_iterable(C)) 10000 loops, best of 3: 117 us per loop sage: len(A), len(B), len(C) (0, 46, 303)
comment:5 Changed 8 years ago by
Your solution is clearly asymptotically faster in theory and practice, and I find it more elegant. There is a non-negligible overhead for small cases, unfortunately, but adding a case distinction for this seems overkill. A new patch is underway.
comment:6 Changed 8 years ago by
- Description modified (diff)
comment:7 Changed 8 years ago by
- Reviewers set to Jeroen Demeyer
- Status changed from needs_review to positive_review
Looks good and useful.
comment:8 Changed 8 years ago by
- Milestone changed from sage-5.12 to sage-5.13
comment:9 Changed 8 years ago by
- Milestone changed from sage-5.13 to sage-5.12
comment:10 Changed 8 years ago by
- Merged in set to sage-5.12.rc1
- Resolution set to fixed
- Status changed from positive_review to closed
instead of
reduce
we can use something faster: