Opened 8 years ago

Last modified 6 weeks ago

#18299 new enhancement

upgrade prime_powers

Reported by: vdelecroix Owned by:
Priority: major Milestone:
Component: number theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #16880 Stopgaps:

Status badges

Description

We make prime_powers an iterator (as it is for primes). We also provide an alternative way of generating prime powers using the method next_prime_power from #16880. It is indeed much faster for a range like [2^200, 2^200 + 256].

See also: #18298

Change History (8)

comment:1 Changed 8 years ago by kcrisman

Deprecation... again, iterators are good in general, but harder for absolute newbies.

comment:2 Changed 8 years ago by vdelecroix

I do not see how one can make it an iterator! Possibly the ugly

def prime_powers(m, n=None, output_type=None):
    if output_type is None:
        deprecation("this is switching from list to iterator")
        output_type = "list"

    if output_type == "list":
        return list(future_prime_powers(m, n))
    elif output_type == "iterator":
        return future_prime_powers(m, n)
    else:
        raise ValueError("output_type must be either 'list' or 'iterator'")

This is what you would prefer? Do you have something better to suggest?

comment:3 Changed 8 years ago by kcrisman

I don't really want it to be an iterator, but that seemed to be the point of this ticket. I just want to make sure there is a way to return a list easily, though this is less important than for primes per se.

comment:4 Changed 8 years ago by leif

I like future_prime_powers(); sounds like it would return numbers which aren't yet prime powers (but will in a few years, say)...

comment:5 Changed 8 years ago by leif

W.r.t. generators:

I guess Karl-Dieter refers to displaying generator object at ... instead of a list of numbers in interactive mode, which might be annoying to (Python) newbies.

In general (or most cases), generators are "better", so we'd IMHO just have to educate new users somehow, telling them they can simply use list(foo(...)). ;-)

Or we could let the "default" functions wrap generator versions, but then we'd have to revert the behaviour of primes() etc. again, which is a bit odd as well.

IIRC Cython meanwhile supports generators, so e.g. primes() could be sped up, at least for "small" numbers (exceeding PARI's stored primes), but that's a bit off-topic.

Last edited 8 years ago by leif (previous) (diff)

comment:6 Changed 8 years ago by leif

P.S.: For convenience, we could also add generators like n.next_primes(), n.next_prime_powers() etc.


Another way to avoid the generator object at ... would be to wrap the generators in classes, similar to n.factor() (although the latter doesn't do lazy factoring). (We do have a Primes class, but e.g. not PrimeRange or the like.)

comment:7 in reply to:  5 Changed 8 years ago by vdelecroix

Replying to leif:

W.r.t. generators:

I guess Karl-Dieter refers to displaying generator object at ... instead of a list of numbers in interactive mode, which might be annoying to (Python) newbies.

In general (or most cases), generators are "better", so we'd IMHO just have to educate new users somehow, telling them they can simply use list(foo(...)). ;-)

And in Python 3 almost everything becomes an iterator (map, range, etc).

Or we could let the "default" functions wrap generator versions, but then we'd have to revert the behaviour of primes() etc. again, which is a bit odd as well.

Changing primes is not an option, see this thread.

IIRC Cython meanwhile supports generators, so e.g. primes() could be sped up, at least for "small" numbers (exceeding PARI's stored primes), but that's a bit off-topic.

Yes, that would be good.

Replying to leif:

P.S.: For convenience, we could also add generators like n.next_primes(), n.next_prime_powers() etc.


Another way to avoid the generator object at ... would be to wrap the generators in classes, similar to n.factor() (although the latter doesn't do lazy factoring). (We do have a Primes class, but e.g. not PrimeRange or the like.)

Wrapping might be a reasonable option, but then what should we do when sombedy does len(l)? Expand the list? Just run the iterator? Use prime_pi? And with l[4]? Should we use next_prime? Use nth_prime? The best solution depends on the usage and this is why I do prefer avoiding wrappers. But this is what has been proposed in the above thread... I would be happy if there is enough documentation mentioning the other ways of accessing the information. So let me do that.

Concrete proposition:

  • make Primes and PrimePowers behave like IntegerRange
    sage: Primes(100, 1000)
    Set of prime numbers in the range 101 <= p < 998: 101, 103, 107, 109, ...
    sage: Primes(2**30)
    Set of prime numbers in the range 2 <= p < 1073741790: 2, 3, 5, 7, ...
    
    (note that the bounds are computed accurately to have a simple equality test)
  • make primes a deprecated alias of Primes (but keep it in sage.rings.arith as it is)
  • change sage.rings.arith.prime_powers to an iterator
  • in the global namespace make prime_powers a deprecated alias of PrimePowers

Vincent

comment:8 Changed 6 weeks ago by mkoeppe

Milestone: sage-6.7
Note: See TracTickets for help on using tickets.