Move PRs from Base
simonbyrne opened this issue · 14 comments
The following PRs were never merged into Base, and so weren't copied over.
cc: @mschauer, @pabloferz
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 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?
A nextprime function sounds like a good idea.
Ok, I'll bring over my PR then
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.
+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
endbut I'm not sure this would be of much benefit.
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
endI 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.
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.
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.
Makes totally sense, actually I had this on my todo, this is similar in functionality to the forprime construct in pari/gp.