Jordi Burgos's avatar

Python bitarray and Sieve of Eratosthenes

Read in 5 min.

Some time ago, I was thinking about prime numbers and I found that it is possible to find prime numbers just with sums instead of divisions or remainders. As it was very simple approach, I thought that for sure, someone else found this solution already. And I was right, this algorithm is called Sieve of Eratosthenes.

This method exchanges the CPU intense calculations by storage. Instead of calculating if a number is prime with divisions, it stores which numbers are not primes until a maximum, then the prime numbers are the ones that are not on the list. Very simple.

Here is the first version of my solution made in Python.

The bitarray started as a solution for a programming contest where the problem was to find the n-th number missing on a 8 GB file full of integers.

BitArray

The easy option to keep all the numbers that are not primes is to use a list. It is a valid solution but not the best, as each number would use 64 bits (Assumption for big numbers, as Python takes the best type for each number representation). The first 1.000.000 numbers would be stored on 7.62 MB of memory.

The minimum size of memory is the bit, so we can mark each number with just a bit. With this approach, a 1.000.000 would use 122 Kb of memory. Here is the implementation of a BitArray in Python.

The program uses an array of 64 bit numbers (or 32 bits, depending on your processor) and each bit says if the number is marked or not. For example, the number 1, goes on the element 0 of the array and the bit 1. The number 63, goes on the element 1 of the array, position bit 32.

Array 32 bits
element 0 00000000000000000000000000000010
element 1 10000000000000000000000000000000

The position of each number on the array and the position of the bit set or reset inside is calculated with bit arithmetic. Here is the code for the address calculations:

    [...]
    # Depends on architecture
    if bitsstr == '64bit':
        self.bits = 64
        self.bit_mask = 0x0000003F
        self.bit_offset = 6
    [...]

def __get_address(self, n):
    # position on the array
    bucket = n >> self.bit_offset
    # bit position on the element
    bit = n & self.bit_mask
    return bucket, bit

How many numbers can hold ?

For calculating all the primes until a certain number, we need to mark all those numbers in any way into memory. The bitarray just uses one bit per number. The architecture, you know 32 or 64 bits, does not affect to the amount of memory as the numbers use just 1 bit.

With 1 GB of memory, it is possible to hold the numbers from 0 to 8,589,934,592, this is 1 * 1024 * 1024 * 1024 * 8.

GB MemoryNumbersPower of 2
18,589,934,5922^33
217,179,869,1842^34
434,359,738,3682^35
868,719,476,7362^36
16137,438,953,4722^37
32274,877,906,9442^38
64549,755,813,8882^39
1281,099,511,627,7762^40
10248,796,093,022,2082^43

This calculations are aproximations, the execution of the program would take a little more memory.

How many memory would need the maximum prime number found ?

The [http://en.wikipedia.org/wiki/Largest_known_prime_number] (http://en.wikipedia.org/wiki/Largest_known_prime_number) is 2^57,885,161 - 1, a number with 17,425,170 digits.

Using the previous table with the comparison between numbers and memory used, calculate the memory needed for the maximum prime number found is easy. 1 Gigabyte holds from 0 to 2^33, 1 Terabyte holds from 0 to 2^43. So 2^57,885,161 - 1 can fit on (57,885,161 - 33) = 57,885,129 Gibabytes = 56,528.45 Terabytes = 55.20 Petabytes.

This sizes are unmanageable usin RAM memory, but it could be possible usin hard drives to store all the information. What would cost to store all that information on hard drives? A 4 TB SATA hard disk costs about 150 EUR (~205 USD). That would be 14,133 drives. About 2,119,800 EUR (2,898,025 USD).

Just for the hard drives. Anyone interested on funding the project ?

Not bad

Optimization

The storage admits some optimizations. The very easy is to skip all even numbers and change the kind of addressing of bits. All the even numbers are not primes. That would take the cost of the project to the half. Those 2,119,800 EUR (2,898,025 USD), would turn on 1,059,900 EUR (1,449,201 USD).

Conclusions

This method to calculate primes is more CPU efficient than the usual with divisions if all the information fits on RAM memory. Its drawback is that trades CPU by storage.

The cost for using this algorithm in the real would be huge, but we just need to let the time pass and wait for the terabyte or petabyte RAM memory or hard drives.


Probably, you want to share this article: