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:

Status badges

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 jdemeyer

  • Cc jdemeyer added
  • Component changed from basic arithmetic to factorization
  • Owner changed from AlexGhitza to tbd

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

comment:2 Changed 11 years ago by jdemeyer

  • Report Upstream changed from N/A to Reported upstream. Developers deny it's a bug.

comment:3 Changed 5 years ago by jmantysalo

  • 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:4 Changed 5 years ago by bruno

  • Status changed from needs_review to positive_review

I agree!

comment:5 Changed 5 years ago by embray

  • 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.