Move PRs from Base about primes.jl HOT 14 CLOSED

This can imho be closed, issue #55 keeps track of the prime iterator.

from primes.jl.

Makes totally sense, actually I had this on my todo, this is similar in functionality to the forprime construct in pari/gp.

from primes.jl.

Moved over here #9

from primes.jl.

Should we drop nextprime(::BigInt)? @pabloferz also wrote "Given that it seems hard to do much better than this, what we really should focus on is in improving isprime istead, as discussed here #11594."

from primes.jl.

"Sizehint for primes" now #11

from primes.jl.

@mschauer I did some tests with your nextprime PR (using GMP's implementation) and your nextprime2 simple loop (modified to add 2 instead of 1 (to test only odd numbers) and in place to minimize allocations), and although in the example you gave, nextprime performs comparatively poorly, on average it seems to be a bit better. Would you mind porting your PR over here, we can always change the implementation when we have something better?

from primes.jl.

A nextprime function sounds like a good idea.

from primes.jl.

Ok, I'll bring over my PR then

from primes.jl.

I did some more experiments last week, and I'm not sure now which implementation should be chosen for nextprime, the from gmp or the trivial solution. I think I favor the latter now, for simplicity while there is no winner.

from primes.jl.

+1 for the "naïve" approach. It also allows us to write a generic function for all types. The only optimization that needs testing to see if it helps a little, is to check every other integer for numbers > 2 or to use a small wheel, for example (not thoroughly tested)

function nextprime(x)
    x < 2 && return 2
    x < 3 && return 3
    d, r = divrem(x + 1, 6)
    x = 6d + ifelse(r > 1, 5, 1)
    Δ = ifelse(r > 1, 2, 4)
    while(!isprime(x))
        x += Δ 
        Δ = ifelse(Δ == 2, 4, 2)
    end
    return x
end

but I'm not sure this would be of much benefit.

from primes.jl.

And for BigInts

function nextprime(x::BigInt)
    x < 2 && return BigInt(2)
    x < 3 && return BigInt(3)
    a, b = BigInt(2), BigInt(4)
    d, r = divrem(x + 1, 6)
    x = 6d + ifelse(r > 1, 5, 1)
    Δ = ifelse(r > 1, a, b)
    while(!isprime(x))
        ccall((:__gmpz_add,:libgmp), Void, (Ptr{BigInt}, Ptr{BigInt}, Ptr{BigInt}), &x, &x, &Δ)
        Δ = ifelse(Δ == 2, b, a)
    end
    return x
end

from primes.jl.

I have done experiments last week with something like this, but using directly your wheel implementation! (so using 30 = 2*3*5 instead of 6). But there was unfortunately no improvement against the naive test on odd numbers (a wheel with 2), as far as I could observe. The reason was that all the MR tests which are skipped correspond exactly to those which are extremly cheap; in other words, the wheel doesn't eliminate the expensive tests. Can be worth comparing with your implementation though.

from primes.jl.

Yeah, I would have thought it won't help to use a wheel given that the cost of the wheel will be similar to the cost of discarding via isprime directly. But I wanted to propose a 6 wheel (or the 30 wheel already implemented that you tested) just in case.

from primes.jl.

Just kind of thinking aloud here, but something that may be kind of interesting would be to define a PrimeIterator type, which allows lazily iterating through primes. Then Base.next(::PrimeIterator, n) is just the n+1th prime, and calling nextprime on the iterator could potentially be made efficient if we do some clever caching or something.

Dunno, maybe this makes no sense, just a thought.

from primes.jl.