[Octave-bug-tracker] [bug #61300] primes() is 4 times slower for integer types than for double, patch attached

[Arun Giridhar]

Follow-up Comment #3, bug #61300 (project octave):

I know now exactly why this slowdown happens. It's because for some reason the
integer range is violated, causing the upper bound to exceed lenp, then the
array is resized and rewritten with all that overhead. For i = 1, the range
inside sievep becomes 8:7:lenp. Look at this experiment for that range:


>> n = double(1.5e9), lenp = floor((n+1)/6), (8:7:lenp)(end-4:end)
n =       1500000000
lenp =        250000000
ans =
               249999968               249999975               249999982      
        249999989               249999996

>> n = uint64(1.5e9), lenp = floor((n+1)/6), (8:7:lenp)(end-4:end)
n = 1500000000
lenp = 250000000
ans =
  249999975  249999982  249999989  249999996  250000003


That last value 250000003 should not be there. Somehow the mixed range with
doubles and integers is causing inappropriate rounding, therefore the whole
array is being resized and rewritten. And this can happen for both sievem and
sievep, therefore twice the overhead.

One more experiment. Stick one or both these statements inside the sieve
calculation, just before sievem and sievep are created:

lenp = double(lenp);
lenm = double(lenm);


You will see that using only one causes 50% of the slowdown, using both causes
no slowdown at all, and using neither causes the full slowdown.

So this is an integer range bug, not necessarily a bug in primes.

Copying jwe for his input.

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?61300>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/