Add _pari_() method to Factorization

[pjbruin]

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: attachment: 15193-Factorization-pari-chain.patch (requires >= 5.12.beta5 or #15124)

Component: factorization

Keywords: pari

Author: Peter Bruin

Reviewer: Jeroen Demeyer

Merged: sage-5.12.rc1

Issue created by migration from https://trac.sagemath.org/ticket/15193

[pjbruin]

Attachment: 15193-Factorization-pari.patch.gz

[pjbruin]

Description changed:

--- 
+++ 
@@ -1,2 +1,5 @@
 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: [attachment: 15193-Factorization-pari.patch](https://github.com/sagemath/sage-prod/files/10658435/15193-Factorization-pari.patch.gz)
+(requires >= 5.12.beta5 or #15124)
+

[mathzeta]

comment:2

instead of reduce we can use something faster:

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

[pjbruin]

comment:3

Replying to @mathzeta:

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?

[mathzeta]

comment:4

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)

[pjbruin]

comment:5

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.

[pjbruin]

same but using itertools.chain

[pjbruin]

comment:6

Attachment: 15193-Factorization-pari-chain.patch.gz

[pjbruin]

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
 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: [attachment: 15193-Factorization-pari.patch](https://github.com/sagemath/sage-prod/files/10658435/15193-Factorization-pari.patch.gz)
+Apply: [attachment: 15193-Factorization-pari-chain.patch](https://github.com/sagemath/sage-prod/files/10658436/15193-Factorization-pari-chain.patch.gz)
 (requires >= 5.12.beta5 or #15124)

[jdemeyer]

comment:7

Looks good and useful.

[jdemeyer]

Reviewer: Jeroen Demeyer

[jdemeyer]

Merged: sage-5.12.rc1