Since int32 is large enough for the biggest number I'll be checking, and 32-bit integer division is usually faster than 64-bit, even on 64-bit platforms, I wrote my prime checking function to take a uint32. A basic prime checking function will usually test odd divisors up to the square root of N, skipping all even numbers (multiples of two). My prime checker is slightly more optimized by skipping all multiples of 3. Here's the code:
func i32Prime(n uint32) bool {
// if (n==2)||(n==3) {return true;}
if n%2 == 0 { return false }
if n%3 == 0 { return false }
sqrt := uint32(math.Sqrt(float64(n)))
for i := uint32(5); i <= sqrt; i += 6 {
if n%i == 0 { return false }
if n%(i+2) == 0 { return false }
}
return true
}
My code will never call isPrime with small numbers, so I have the first line that checks for two or three commented out. In order to test and benchmark the function, I wrote prime_test.go. Run the tests with "go test prime_test.go -bench=. test". For numbers up to 22 bits, i32Prime is one to two orders of magnitude faster than ProbablyPrime(0). In absolute terms, on a Celeron G1840 using a single core, BenchmarkPrime reports 998 ns/op. I considered further optimizing the code to skip multiples of 5, but I don't think the ~20% speed improvement is worth the extra code complexity.
Awesome. It's a small but elegant function! I'd probably combine the adjacent conditionals with an OR operator though.
ReplyDelete