On Wednesday, 30 October 2013 at 18:56:42 UTC, Zeke wrote:
On Wednesday, 30 October 2013 at 14:17:22 UTC, qznc wrote:
Why do you want to find the exact prime first? Just check
against sqrt(num) in the loop.
auto upper = cast(ulong)sqrt(cast(double)num)) + 1;
foreach(ulong prime; primes) {
if (prime > upper) return true;
if (num % prime == 0) return false;
}
assert (false); // should be unreachable?
Because having a branch inside the foreach causes a branch
prediction error when you've found a prime number. Simply
iterating up to the sqrt and then terminating the loop has no
branch prediction error. Try it for yourself.
Interesting thought.
In your code, there are two conditional branches in each
iteration: The check for the end of foreach range and the prime
check. Why is one more condition for the upper check so bad?
I admit, my code includes the superfluous foreach range check.
Hence this improved version:
ulong prime;
int i = 0;
assert (primes[$] > upper);
do {
prime = primes[i];
if (num % prime == 0) return false;
i+=1;
} while (prime < upper);
return true;
In this version there is still an implicit bounds check for the
array access. For dmd "-noboundscheck" disables that branching.
Optimizing for branch prediction sounds premature, since you are
using a slow algorithm anyways. ;)
