Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#16869 closed defect (fixed)

faster prime_powers

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.4
Component: number theory Keywords:
Cc: ncohen Merged in:
Authors: Vincent Delecroix Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 8259a7d (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by vdelecroix)

The function prime_powers in sage.rings.arith was using the symbolic ring... it would be faster to use a sleep(10) and avoid it.

follow up: #16880

Change History (12)

comment:1 Changed 6 years ago by vdelecroix

  • Branch set to u/vdelecroix/16869
  • Commit set to 0799048ccc0da82a59b5cdc733127c997dfd11fa
  • Status changed from new to needs_review

New commits:

​0799048trac #16869: fast prime_powers

comment:2 Changed 6 years ago by vdelecroix

Old timings 

sage: timeit("prime_powers(1000)")
125 loops, best of 3: 6.13 ms per loop
sage: timeit("prime_powers(5000)")
25 loops, best of 3: 9.43 ms per loop
sage: timeit("prime_powers(10000)")   # oh yeah! 10000 is a square!
625 loops, best of 3: 282 µs per loop
sage: timeit("prime_powers(10001)")
25 loops, best of 3: 12.7 ms per loop

new timings 

sage: timeit("prime_powers(1000)")
625 loops, best of 3: 91.4 µs per loop
sage: timeit("prime_powers(5000)")
625 loops, best of 3: 282 µs per loop
sage: timeit("prime_powers(10000)")
625 loops, best of 3: 518 µs per loop
sage: timeit("prime_powers(10001)")
625 loops, best of 3: 500 µs per loop

It seems that using twice prime_range is not a so good idea.

Vincent

comment:3 Changed 6 years ago by git

  • Commit changed from 0799048ccc0da82a59b5cdc733127c997dfd11fa to f73bd87b6850f626ae9d6da896fb730f3ae759c1

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​f73bd87trac #16869: fast prime_powers

comment:4 Changed 6 years ago by git

  • Commit changed from f73bd87b6850f626ae9d6da896fb730f3ae759c1 to 8259a7d2951366c5c715e8080ce96106e1e7e14a

Branch pushed to git repo; I updated commit sha1. New commits:

​8259a7dtrac #16869: fix prime_powers(0,1)

comment:5 Changed 6 years ago by ncohen

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

Gooooooooooooooood to go !

Nathann

comment:6 Changed 6 years ago by vdelecroix

Cool! Thanks!

Vincent

comment:7 follow-up: Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

author name can't be reviewer name ;-)

comment:8 Changed 6 years ago by vdelecroix

  • Reviewers changed from Vincent Delecroix to Nathann Cohen
  • Status changed from needs_work to positive_review

comment:9 in reply to: ↑ 7 Changed 6 years ago by vdelecroix

Replying to vbraun:

author name can't be reviewer name ;-)

Never happy ;-)

comment:10 Changed 6 years ago by ncohen

Soorrryyyyyyyyyyyyyyyyyyyyyyyyyyy

Nathann

comment:11 Changed 6 years ago by vbraun

  • Branch changed from u/vdelecroix/16869 to 8259a7d2951366c5c715e8080ce96106e1e7e14a
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:12 Changed 6 years ago by vdelecroix

  • Commit 8259a7d2951366c5c715e8080ce96106e1e7e14a deleted
  • Description modified (diff)
Note: See TracTickets for help on using tickets.