Opened 14 years ago
Closed 14 years ago
#467 closed enhancement (fixed)
[with patch] asymptotically slow pari integer conversions
Reported by: | dmharvey | Owned by: | craigcitro |
---|---|---|---|
Priority: | minor | Milestone: | sage-2.8.7 |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The conversion function from PARI integers to python longs is asymptotically slow (apparantly quadratic time). This shows up when doing something like int(some_pari_object)
. Similarly from SAGE integers to PARI integers.
There are also inconsistencies like (on my machine at home):
sage: x = 10^100000 sage: time y = pari(x) CPU times: user 1.18 s, sys: 0.01 s, total: 1.19 s Wall time: 1.26 sage: time z = Integer(y) CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s Wall time: 0.02 sage: time u = int(y) CPU times: user 1.94 s, sys: 1.33 s, total: 3.27 s Wall time: 3.58 sage: time u = int(Integer(y)) CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s Wall time: 0.03
now see the quadratic time:
sage: x = 10^1000000 sage: time y = pari(x) CPU times: user 105.12 s, sys: 1.26 s, total: 106.38 s Wall time: 121.86 sage: time z = Integer(y) CPU times: user 0.03 s, sys: 0.02 s, total: 0.05 s Wall time: 0.09 sage: time u = int(y) CPU times: user 188.17 s, sys: 145.12 s, total: 333.28 s Wall time: 364.80 sage: time u = int(Integer(y)) CPU times: user 0.04 s, sys: 0.02 s, total: 0.06 s Wall time: 0.07
Attachments (1)
Change History (9)
comment:1 Changed 14 years ago by
- Milestone set to sage-feature
comment:2 Changed 14 years ago by
- Type changed from defect to enhancement
comment:3 Changed 14 years ago by
- Owner changed from somebody to craigcitro
comment:4 Changed 14 years ago by
- Status changed from new to assigned
comment:5 Changed 14 years ago by
- Milestone changed from sage-feature to sage-2.8.7
- Summary changed from asymptotically slow pari integer conversions to [with-patch] asymptotically slow pari integer conversions
Changed 14 years ago by
comment:6 Changed 14 years ago by
- Summary changed from [with-patch] asymptotically slow pari integer conversions to [with patch] asymptotically slow pari integer conversions
comment:7 Changed 14 years ago by
This has a serious problem:
22:42 < cwitty_> I was looking at #467, and I just crashed SAGE with a PARI stack overflow. 22:43 < cwitty_> I thought the stack was supposed to resize automatically, or something? (Or at least not crash SAGE.) 22:44 < cwitty_> sage: n = 10^10000000 22:44 < cwitty_> sage: %time _ = pari(n) 22:44 < cwitty_> *** the PARI stack overflows ! 22:44 < cwitty_> current stack size: 8000000 (7.629 Mbytes) 22:44 < cwitty_> [hint] you can increase GP stack with allocatemem() 22:44 < cwitty_> /home/cwitty/sage/local/bin/sage-sage: line 205: 25703 Aborted sage-ipython -c "$SAGE_STARTUP_COMMAND;" "$@" 22:44 < cwitty_> (This is after I applied the patch from #467.) 22:45 < williamstein> weird. 22:45 < williamstein> it should automatically double *if* the author correctly uses _sig_on/_sig_off 22:47 < cwitty_> This is the ZZ->Pari fast coercion patch, and I'm pretty sure (from skimming the patch) that he never touches _sig_on/_sig_off. So that's probably it.
See trac #
comment:8 Changed 14 years ago by
- Resolution set to fixed
- Status changed from assigned to closed
Note: See
TracTickets for help on using
tickets.
So I've fixed half of the above problems, namely the Pari <--> SAGE issues. I'm going to make a patch for the Pari <--> int issues, but since 2.8.7 is imminent, I thought it would be worth getting this posted first. Here's the state of affairs after the first patch:
There is a small (20%) improvement on pari --> sage with this patch, and a much larger (at least 5X, up to 7-8X depending on the length of the number) improvement on sage --> pari with this patch. Running y._pari_() with y an element of ZZ is the fastest way to get the corresponding pari element, as pari(y) has just a bit more overhead (it ultimately calls y._pari_() after a few typechecks and whatnot).
The other ticket (with the pari <--> python long issue) is #864.