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:

Status badges

Description (last modified by pbruin)

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)

15193-Factorization-pari.patch (1.5 KB) - added by pbruin 8 years ago.
15193-Factorization-pari-chain.patch (1.6 KB) - added by pbruin 8 years ago.
same but using itertools.chain

Download all attachments as: .zip

Change History (12)

Changed 8 years ago by pbruin

comment:1 Changed 8 years ago by pbruin

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 follow-up: Changed 8 years ago by mathzeta2

instead of reduce we can use something faster:

from itertools import chain
... #line 914:
        entries = init + tuple(chain.from_iterable(self))

comment:3 in reply to: ↑ 2 Changed 8 years ago by pbruin

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 mathzeta2

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 pbruin

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.

Changed 8 years ago by pbruin

same but using itertools.chain

comment:6 Changed 8 years ago by pbruin

  • Description modified (diff)

comment:7 Changed 8 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to positive_review

Looks good and useful.

comment:8 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.12 to sage-5.13

comment:9 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.13 to sage-5.12

comment:10 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.12.rc1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.