Looking for something similar to Python's bisect_right

[qznc]

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. ;)