Opened 8 years ago

Closed 8 years ago

# Add _pari_() method to Factorization

Reported by: Owned by: pbruin minor sage-5.12 factorization pari sage-5.12.rc1 Peter Bruin Jeroen Demeyer N/A

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)

### comment:1 Changed 8 years ago by pbruin

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

### comment:2 follow-up: ↓ 3 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

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.