Opened 11 years ago
Closed 5 years ago
#9463 closed defect (wontfix)
Integer factorization should handle perfect powers efficiently
Reported by: | fredrik.johansson | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | factorization | Keywords: | |
Cc: | jdemeyer | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Reported upstream. Developers deny it's a bug. | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
factor() is extremely slow at factoring large perfect powers (with a nontrivial base).
sage: %time factor(next_prime(10^20)^150) CPU times: user 0.75 s, sys: 0.00 s, total: 0.75 s Wall time: 0.75 s 100000000000000000039^150 sage: %time factor(next_prime(10^20)^250) CPU times: user 2.68 s, sys: 0.00 s, total: 2.68 s Wall time: 2.69 s 100000000000000000039^250 sage: %time factor(next_prime(10^20)^500) CPU times: user 13.19 s, sys: 0.00 s, total: 13.19 s Wall time: 13.20 s 100000000000000000039^500
For comparison, SymPy handles such numbers in an instant:
sage: from sympy import factorint sage: %time factorint(next_prime(10^20)^150) CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s {100000000000000000039L: 150} sage: %time factorint(next_prime(10^20)^250) CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s {100000000000000000039L: 250} sage: %time factorint(next_prime(10^20)^500) CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s Wall time: 0.02 s {100000000000000000039L: 500}
Perfect power testing is very cheap, so it should be attempted early on for large numbers.
Change History (5)
comment:1 Changed 11 years ago by
- Cc jdemeyer added
- Component changed from basic arithmetic to factorization
- Owner changed from AlexGhitza to tbd
comment:2 Changed 11 years ago by
- Report Upstream changed from N/A to Reported upstream. Developers deny it's a bug.
comment:3 Changed 5 years ago by
- Milestone set to sage-duplicate/invalid/wontfix
- Status changed from new to needs_review
Examples take milliseconds now even on old computer, so I guess this has been fixed and can be closed.
comment:5 Changed 5 years ago by
- Resolution set to wontfix
- Status changed from positive_review to closed
Determined to be invalid/duplicate/wontfix (closing as "wontfix" as a catch-all resolution).
Note: See
TracTickets for help on using
tickets.
This is because of the way PARI factors number (first trial division, then perfect power checking). See http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1074