search

JuliaMath / Primes.jl

Prime numbers in Julia
Other
99 stars 32 forks source link

use BPSW for primality testing #129

Closed oscardssmith closed 1 year ago

oscardssmith commented 1 year ago

Use BPSW for prime testing numbers with more than 32 bits. The lucas test costs about 2 MR tests, but by the time a number has passed 1 MR round, it's probably prime, so this saves between (roughly) 2 and 4 MR tests of time.

function bench()
    ts = Float64[]
    for i in 16:61
        push!(ts, @belapsed isprime(p) setup=(p=nextprime(rand(2^$i:2^($i+1)))))
    end
    ts
end

image

oscardssmith commented 1 year ago

This appears to be failing on Julia <1.6 (due to the @ccalls I added in IntegerMathUtils). Would anyone be upset by me raising the compat of this to Julia 1.6? I don't think it makes sense to keep supporting Julia versions pre 1.6 since 1.6 has been the LTS version for 2 years by now.

StefanKarpinski commented 1 year ago

Seems fine to me.

StefanKarpinski commented 1 year ago

To clarify, bumping the requirement to Julia 1.6 seems fine. I don't feel qualified to review the PR.