Why are these sieve optimizations breaking my code?

Question

And how can I correct them to work? I am trying to optimize my sieve per previous suggestions, but in both instances the code breaks:

Incrementing j = j + ( i * 2) will break the code.

Obviously I'm missing some concept on optimizations as well as other people are. But in general you just go through and mark all multiples of a prime as not prime. Optimizing is the next step.

// prime-3
// sieve implementation
function prime3(n) {
  const sieve = (new Array(n)).fill(true);
  // Only iterate up to the square root n for marking
  for (let i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      // recommended optimization breaks the code
      // j = j + ( i * 2 )
      for (let j = i * i; j <= n; j = j + i) {
        sieve[j] = false;
      }
    }
  }
  return makePrimes(sieve, n);
};

function makePrimes(sieve, n) {
  let primes = [];
  for (let i = 2; i < n; i++) {
    if (sieve[i]) {
      primes.push(i);
    }
  }
  return primes;
}
console.log(prime3(100));

the [recommendation was](https://stackoverflow.com/a/60419115/849891) "to special-case 2, start from 3 ***and*** increment the candidates by 2 and use the inner loop increment of `2*i` instead of just `i`" -- *provided* you start from 3 and increment the candidates by 2, that is. :) i.e. the optimizations come in particular order, you can't skip one and use the other which really is contingent on the first one! — Will Ness, Mar 11 '20 at 21:27
thanks, noted. also I needed to step through the code to see what it is doing, and than it is more obvious. Creating a sieve with the evens marked out is `O(n)` time complexity can you explain the over all Big O ? — jennifer, Mar 15 '20 at 14:02
re the big O time complexity, see the last sentence in [my answer](https://stackoverflow.com/a/60419115/849891) to your other question. It gives links. the `π(n)* π(√n)` there means: each prime under `n` is tested for divisibility by all the primes under `sqrt(n)`. `π(n)` =~ `n/log n` (see the link there for details). as for the composites, see the other link. the overall complexity is the maximum of the two. If you will have some specific questions after working through those links, ask them there please. :) — Will Ness, Mar 15 '20 at 15:17
or did you mean the complexity of the proper sieve of Eratosthenes? for that, see e.g. https://stackoverflow.com/a/2582776/849891. (the above comment refers to the optimal trial division sieve). — Will Ness, Mar 15 '20 at 15:32

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

Your optimization needs to be applied after getting rid of even number first (except 2). because when i==2, you effectively skipped all even numbers by incrementing by i*2.

Here is a working code:

// prime-3
// sieve implementation
function prime3(n) {
  let sieve = (new Array(n)).fill(true);
  for (let i = 4; i < n; i+=2) {
    sieve[i] = false;
  }
  
  // Only iterate up to the square root n for marking
  for (let i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      // now it works
      // j = j + ( i * 2 )
      for (let j = i * i; j <= n; j = j + i*2) {
        sieve[j] = false;
      }
    }
  }
  return makePrimes(sieve, n);
};

function makePrimes(sieve, n) {
  let primes = [];
  for (let i = 2; i < n; i++) {
    if (sieve[i]) {
      primes.push(i);
    }
  }
  return primes;
}
console.log(prime3(100));

Edit

Scratch this. Further testing does show prime3 is 3 times faster then simple sieve.

The code although works, seems put too much tricks to do and introduced both extra calculations and confusion. A simple sieve code like the following in my comparison out performs the one in the answer. Again, KISS is the principle.

It took the script in the origin answer 317ms to sieve 1M numbers, while the simple sieve took only 241ms.

function simpleSieve(n) {
  let a = new Array(n)
  let answer = []
  let p
  for (let i = 2; i < n; i ++) {
    a[i] = i
  }
  for (let i = 2; i < n; i++) {
    if (a[i]) {
      answer.push(a[i])
      p = a[i]
      for(let j = p; j < n;  j += p) {
        a[j] = 0
      }
    }
  }
  return answer
}

Edit 2

Retested with cpp and prime3 does improve about 3 times faster than simple sieve:

p3:
n = 100000000, t = 866717 microseconds.
n = 200000000, t = 2354425 microseconds.
n = 300000000, t = 3689165 microseconds.
n = 400000000, t = 4950224 microseconds.
n = 500000000, t = 6119779 microseconds.
n = 600000000, t = 7375925 microseconds.
n = 700000000, t = 8647293 microseconds.
n = 800000000, t = 10477116 microseconds.
n = 900000000, t = 11589894 microseconds.
n = 1000000000, t = 12806997 microseconds.
simple:
n = 100000000, t = 2316019 microseconds.
n = 200000000, t = 6063749 microseconds.
n = 300000000, t = 9783295 microseconds.
n = 400000000, t = 13315450 microseconds.
n = 500000000, t = 16640474 microseconds.
n = 600000000, t = 20282461 microseconds.
n = 700000000, t = 24219469 microseconds.
n = 800000000, t = 29203786 microseconds.
n = 900000000, t = 32965856 microseconds.
n = 1000000000, t = 37694084 microseconds.

Codes here for completeness:

void simpleSieve(int n) {
  bool *a = (bool *)calloc(n, sizeof(bool));
  int p;
  memset(a, true, sizeof(bool) * n);
  for (int i = 2; i < n; i++) {
    if (a[i]) {
      p = i;
      for (int j = p; j < n; j += p) {
        a[j] = 0;
      }
    }
  }
  free(a);
}

void prime3(int n) {
  bool *sieve = (bool*)calloc(n, sizeof(bool));
  sieve[2] = true;
  for (int i = 3; i < n; i+=2) {
    sieve[i] = true;
  }
  int step;
  for (int i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      step = i*2;
      for (int j = i * i; j <= n; j = j + step) {
        sieve[j] = false;
      }
    }
  }
  free(sieve);
}

Seems inefficient to create an array with all true values and then mark all the evens. Wish there was a way to init the array with all the evens marked out. — jennifer, Mar 11 '20 at 14:48
the loop is just O(n). magnitude smaller than the overall complexity, which is O(nlog(log(N))) — Jingshao Chen, Mar 11 '20 at 15:28
why are you marking the multiples of 4,6,8,10,... as composite? aren't they already marked as composite multiples of 2? --- why are you checking whether even numbers above 2 are prime? don't you already know they are not? --- why are you marking 2 as composite, then as prime, and then check whether it is prime or not? don't you already know 2 is prime? — Will Ness, Mar 11 '20 at 21:06
They were not marked as composite in the question because the increment by `i*2`, and the smallest `i` is `2`. The last why is valid. I updated my answer. — Jingshao Chen, Mar 12 '20 at 16:33

score 1 · Accepted Answer · answered Mar 15 '20 at 13:54

You made a simple mistake of not preparing your sieve. You should eliminate all multiples of 2 to start with:

function makeSieve(n){
  const sieve = new Array(n).fill(true);
  for(let i = 2; i < sieve.length; i += 2){
    sieve[i] = false;
  }
}

Now when you go to mark non-primes you can increment i * 2

For example

3, 6, 9, 12, 15, 18, 21

will become

3, 9, 15, 21

Max K · Answer 3 · 2020-03-11T14:20:15.917

Actually the optimization is working for me:

 // prime-3
    // sieve implementation
    function prime3 (n) {
      const sieve = (new Array(n)).fill(true);
    
      // Only iterate up to the square root n for marking
      for (let i = 2; i * i <= n; i += 1) {
        if (sieve[i]) {
    
          // recomended optimizations break the code
          // j = i * i 
          // j = j + ( i * 2 )
          for (let j = i * i; j <= n; j = j+i) {
            sieve[j] = false;
          }
        }
      }
      return makePrimes(sieve, n);
    };
    
    function makePrimes(sieve, n){
      let primes = [];
      for (let i = 2; i < n; i++) {
        if(sieve[i]) {
          primes.push(i);
        }
      }
      return primes;
    }
    
    console.log(prime3(100));

But your j = j + ( i * 2 ) 'optimization' actually breaks the algorithm. The results will contain non prime numbers. Here a snippet to check:

function prime3 (n) {
      const sieve = (new Array(n)).fill(true);
    
      // Only iterate up to the square root n for marking
      for (let i = 2; i * i <= n; i += 1) {
        if (sieve[i]) {
    
          // recomended optimizations break the code
          // j = i * i 
          // j = j + ( i * 2 )
          for (let j = i * i; j <= n; j = j+(i*2)) {
            sieve[j] = false;
          }
        }
      }
      return makePrimes(sieve, n);
    };
    
    function makePrimes(sieve, n){
      let primes = [];
      for (let i = 2; i < n; i++) {
        if(sieve[i]) {
          primes.push(i);
        }
      }
      return primes;
    }
    
    console.log(prime3(100));

Why are these sieve optimizations breaking my code?

3 Answers3

Edit

Edit 2