#16880: prime_powers and prime_power_range
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: number theory | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/16880 | a3195f7bb4e16cc4eb3f3ae4ef58a4b5d0341ad2
Dependencies: #16878 | Stopgaps:
-------------------------------------+-------------------------------------
Description changed by vdelecroix:
Old description:
> The cythonization of `prime_powers` is much faster (around x4 in the
> timings). We introduce in a new function `prime_power_range` in
> `fast_arith.pyx` that is similar to `prime_range`.
>
> Since #16878, 1 is not a prime power anymore! So we fix `prime_powers` to
> never return 1 in its output.
New description:
This ticket introduces several changes:
- introduce a method `next_prime_power` for integers
- make `prime_powers` an iterator (using `next_prime_power`) so that it
can be used for large integers as well
- create a much faster cythonized `prime_power_range`
We get a little speed down for the iteration over `prime_powers` but we
can now do
{{{
sage: for p in prime_powers(2**100, 2**100+500):
....: print p
1267650600228229401496703205376
1267650600228229401496703205653
1267650600228229401496703205707
1267650600228229401496703205823
}}}
The cython function `prime_power_range` is much faster than the previous
`prime_powers` (around x4 in the timings).
Since #16878, 1 is not a prime power anymore! So we fix `prime_powers` to
never return 1 in its output.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/16880#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
