Opened 12 years ago

Closed 12 years ago

#9537 closed enhancement (fixed)

trial_division in Sage is really slow

Reported by: was Owned by: AlexGhitza
Priority: minor Milestone: sage-4.5.2
Component: basic arithmetic Keywords:
Cc: Merged in: sage-4.5.2.alpha0
Authors: William Stein Reviewers: Sebastian Pancratz
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges


See my talk:

Basically, this sucks:

sage: n = 20110000038209
sage: timeit('trial_division(n)')
125 loops, best of 3: 2.75 ms per loop

Even in pure python one can easily implement this so it runs in about 650microseconds. In C, it takes only 6 microseconds!

Attachments (1)

trac_9537-fast_trial_division.patch (6.4 KB) - added by was 12 years ago.

Download all attachments as: .zip

Change History (4)

comment:1 Changed 12 years ago by was

  • Status changed from new to needs_review

Changed 12 years ago by was


comment:2 Changed 12 years ago by spancratz

  • Status changed from needs_review to positive_review

comment:3 Changed 12 years ago by mpatel

  • Authors set to William Stein
  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Reviewers set to Sebastian Pancratz
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.