Javascript Increase Max Array Size

I am trying to create an array of size 2^32 = 4294967296, because I am trying to get all the prime numbers till 2^32 by running the sieve algorithm. However any operation in that a

Solution 1:

Arrays can't be that big, the maximum length is 2-1. According to ECMAScript spec,

Every Array object has a length property whose value is always a nonnegative integer less than 2.

A String property name P is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 2−1.

Solution 2:

An array of 2^32 elements is basically 4 GB * size of an element, so there are high chances it will not fit into memory.

The error you are getting is exactly that: the allocator cannot allocate enough space. You might want to consider another solution than allocating a several gigabytes array. Having a little more detail about what you are trying to achieve could help putting you on the right track! :)

Solution 3:

For node.js just install big-array.

A resizable array using non-sequential block memory allocation. Growing or shrinking the array does not require reallocation of the entire array. Useful when you need to track a few trillion data points.

Solution 4:

For a sieve algorithm, you need just one bit for each number to test...

Look for a bitset implementation (https://github.com/tdegrunt/bitset for instance). This one will grow dynamically as you set bits in it. You can set and get bits, and each bit will tell you if n is a prime.

However, I recommend you test with max 100, not 2^32... because it will be slow...

Actually, bitset breaks between 10M and 100M on my Mac. I guess they don't use a byte array.

In coffee-script because it's less verbose...

Bitset = require 'bitset'

sieve = (maxSize)=>

    mark = (bitset)->
        markMultiplesOf = (n)->
            bitset.set(n*each) foreachin [2..(maxSize / n)]

        markMultiplesOf eachforeachin [2..(maxSize / 2)] when bitset.get(each) isfalse

    showPrimes = (bitset)->
        console.log eachforeachin [0..(bitset.length())] when bitset.get(each) isfalse

    timestamp = Date.now()

    bitset = new Bitset(maxSize)
    mark bitset, maxSize

    console.log "took #{Date.now() - timestamp} ms"
    showPrimes(bitset)

sieve(10000000) # takes < 4s