Sieve of Eratosthenes in Javascript vs Haskell

user_470772 0
Viewed 179

I've been playing around with Haskell and find it fascinating, especially the Lazy Evaluation feature which allows us to work with (potencially) infinite lists.

From this, derives the beautiful implementation of the Sieve of Eratosthenes to get an infinite list of primes:

primes = sieve [2..]
  where sieve (x:xs) = x : sieve [i | i <- xs, i `mod` x /= 0]

Still using haskell i can have either:

takeWhile (<1000) primes

which gives me the primes until 1000 (n), or

take 1000 primes

which gives me the first 1000 primes

I tried to implement this in Javascript, forgetting the 'infinite' possibility and this is what i came up with:

const sieve = list => {
  if (list.length === 0) return []
  const first = list.shift()
  const filtered = list.filter(x => x % first !== 0)
  return [first, ...sieve(filtered)]
}

const getPrimes = n => {
  const list = new Array(n - 1).fill(null).map((x, i) => i + 2)
  return sieve(list)
}

It works perfectly (if i don't reach maximum call stack size), but i can only get the prime numbers "up until" n.

How could i use this to implement a function that would instead return "the first n" primes?

I've tried many approaches and couldn't get it to work

Bonus

is there any way i can use tail call optimization or something else to avoid StackOverflows for large Ns?

primes javascript
2 Answers

As @VLAZ suggested, we can do this using generators:

function* removeMultiplesOf(x, iterator) {
  for (const i of iterator)
    if (i % x != 0)
      yield i;
}
function* eratosthenes(iterator) {
  const x = iterator.next().value;
  yield x;
  yield* eratosthenes(removeMultiplesOf(x, iterator));
}
function* from(i) {
  while (true)
    yield i++;
}
function* take(n, iterator) {
  if (n <= 0) return;
  for (const x of iterator) {
    yield x;
    if (--n == 0) break;
  }
}

const primes = eratosthenes(from(2));
console.log(Array.from(take(1000, primes)));

Btw, I thought one might be able to optimise this by not doing division repeatedly:

function* removeMultiplesOf(x, iterator) {
  let n = x;
  for (const i of iterator) {
    while (n < i)
      n += x;
    if (n != i)
      yield i;
  }
}

but a quick benchmark showed it actually is about as fast as the simple function.

user_10485720

Alright, after working all weekend on this, i think i found my best implementation.

My solution uses proper caching (using the power of closures) of previous results so, the performance keeps getting better the more you use it

To get the first N primes, I iterate through the getPrimesTill until i reach a sufficient length... there is a compromise here, which will find more primes than intended on the first time but i don't think it can be any other way. Maybe getPrimesTill(n + ++count * n * 5) can be further optimized but i think this is more than good enough.

To be able to handle very large numbers while avoiding stack overflows, i implemented the sieve algorithm using a for loop, instead of recursion.

Here's the code:

function Primes() {
  let thePrimes = []

  const shortCircuitPrimes = until => {
    const primesUntil = []
    for (let i = 0; ; i++) {
      if (thePrimes[i] > until) {
        return primesUntil
      }
      primesUntil.push(thePrimes[i])
    }
  }

  const sieveLoop = n => {
    const list = buildListFromLastPrime(n)
    const result = []
    let copy = [...thePrimes, ...list]
    for (let i = 0; i < result.length; i++) {
      copy = copy.filter(x => x % result[i] !== 0)
    }
    for (let i = 0; ; i++) {
      const first = copy.shift()
      if (!first) return result
      result.push(first)
      copy = copy.filter(x => x % first !== 0)
    }
  }

  const buildListFromLastPrime = n => {
    const tpl = thePrimes.length
    const lastPrime = thePrimes[tpl - 1]
    const len = n - (lastPrime ? tpl + 1 : 1)
    return new Array(len).fill(null).map((x, i) => i + 2 + tpl)
  }

  const getPrimesTill = n => {
    const tpl = thePrimes.length
    const lastPrime = thePrimes[tpl - 1]
    if (lastPrime > n) {
      return shortCircuitPrimes(n)
    }

    const primes = sieveLoop(n)
    if (primes.length - thePrimes.length) {
      thePrimes = primes
    }
    return primes
  }

  const getFirstPrimes = n => {
    let count = 0
    do {
      if (thePrimes.length >= n) {
        return thePrimes.slice(0, n)
      }
      getPrimesTill(n + ++count * n * 5)
    } while (true)
  }

  return { getPrimesTill, getFirstPrimes, thePrimes }
}

const { getPrimesTill, getFirstPrimes, thePrimes } = Primes()

I created a repo for it, with exhaustive testing anyone wants to give it a go.

https://github.com/andrepadez/prime-numbers-sieve-eratosthenes-javascript

The entire test suite takes about 85s to run, as i'm testing with many possible combinations and very large numbers.
Also, all the expected results were obtained from the Haskell implementation, so to not to pollute the tests.

Also, I found this awesome video, where the guy implements Lazy Evaluation and Infinite Lists using TypeScript... In the end, he builds the Sieve Algorithm in Javascript, working exactly like intended in Haskell

https://www.youtube.com/watch?v=E5yAoMaVCp0

user_4707720
Related