Prime sieve in JavaScript

Update : After running the C version through Emscripten, the result is about the same speed as the C version when run through Firefox. Wow!

Update : Switching from a Javascript Array to Int8Array halved the time in Firefox, making it comparable to C and Emscripten. (Until moving C to 8 bits, then things got faster there as well …).

Ok, time for some more prime sieving. This time, we are going to try JavaScript, Python, and C.

First, the Python code

import numpy as np

def sieve1(n):
    values = np.arange(n)
    values[1] = 0
    # values[4::2] = 0
    for i in xrange(n):
        i2 = i*i
        if i2 >= n:
            break
        if values[i]:
            values[i2::i] = 0
    result = values[values > 0]
    return result

This is the normal sieve. The inner loop is in NumPy, and running

%timeit ps = primes_np.sieve1(15485864)

Gives me a list of first million primes in about 425 ms on my laptop.

Next, C.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
  const int n = 15485864;
  clock_t start = clock();
  int *arr = malloc(n * sizeof(int));

  for(int i = 0; i < n; ++i) { arr[i] = i; }
  arr[1] = 0;

  for(int i = 0; i < n; ++i) {
    int d = i * i;
    if(d >= n) { break; }
    if(arr[i]) {
      for(int j = d; j < n; j += i) {
        arr[j] = 0;
      }
    }
  }
  int count = 0;
  for(int i = 0; i < n; ++i) {
    if(arr[i]) { ++count; }
  }
  clock_t end = clock();
  printf("found %d primes less than %d\n", count, n);
  double duration = (end - start) / (double)CLOCKS_PER_SEC;
  printf("took %f seconds\n", duration);
}

This code took about 280 ms. (clang -O3)

Finally, the JavaScript version.

const create_array = (() => {
    // Create an array of values as the result of calling fcn[i] for 0
    // <= i < n
    if(typeof Int8Array === 'function') {
        return (n) => {
            return new Int8Array(n);
        };
    } else {
        return () => {
            return new Array();
        };
    }
})();

const array_init = function(fcn, n) {
    const result = create_array(n);
    for(let i = 0; i < n; i++) {
        result[i] = fcn(i);
    }
    return result;
};

// Simple sieve.
const sieve1 = function(n) {
    // alert("version 2");
    const values = array_init(() => 1, n);

    values[1] = 0;
    values[0] = 0;

    for(let i = 0; i < n; i++) {
        if(values[i] > 0) {
            if(i*i > n) { break; }
            for(let j = i*i; j < n; j += i) {
                values[j] = 0;
            }
        }
    }

    const result = [];
    for(let j = 0; j < values.length; j += 1) {
        if(values[j] > 0) {
            result.push(j);
        }
    }
    return result;
};


export {sieve1};

This takes around 650 ms on the same computer.

None of these examples were tweaked or tested rigorously …

Just for fun, you can run the JavaScript on this page. The millionth prime should be 15,485,863.