Move PRs from Base

[simonbyrne]

The following PRs were never merged into Base, and so weren't copied over.

• RFC: nextprime(::BigInt) JuliaLang/julia#16314
• Better sizehint for primes JuliaLang/julia#16333
• Improve isprime performance for 32-bit integers JuliaLang/julia#16349

cc: @mschauer, @pabloferz

[pabloferz]

Moved over here #9

[mschauer]

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."

[mschauer]

"Sizehint for primes" now #11

[rfourquet]

@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?

[simonbyrne]

A nextprime function sounds like a good idea.

[mschauer]

Ok, I'll bring over my PR then

[rfourquet]

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.

[pabloferz]

+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.

[pabloferz]

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

[rfourquet]

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.

[pabloferz]

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.

[ararslan]

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.

[rfourquet]

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

[mschauer]

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