Python large integer performance

user_1030287 0
Viewed 301

I wanted to code a prime number generator in python - I've only done this in C and Java. I did the following. I used an integer bitmap as an array. Performance of the algorithm should increase nlog(log(n)) but I am seeing exponential increase in cost/time as the problem size n increases. Is this something obvious I am not seeing or don't know about python as integers grow larger than practical? I am using python-3.8.3.

def countPrimes(n):
    if n < 3:
        return []

    arr = (1 << (n-1)) - 2

    for i in range(2, n):
        selector = 1 << (i - 1)
        if (selector & arr) == 0:
            continue

        # We have a prime
        composite = selector
        while (composite := composite << i) < arr:
            arr = arr & (~composite)

    primes = []
    for i in range(n):
        if (arr >> i) & 1 == 1:
            primes.append(i+1)

    return primes

Some analysis of my runtime:

enter image description here

A plot of y = nlog(log(n)) (red line which is steeper) and y = x (blue line which is less steep):

enter image description here

I'd normally not use integers with sizes exceeding uint64, because python allows unlimited size integers and I'm just testing, I used the above approach. As I said, I am trying to understand why the algorithm time increases exponentially with problem size n.

primes time-complexity python-3.x algorithm python
1 Answers

I used an integer bitmap as an array

That's extremely expensive. Python ints are immutable. Every time you want to toggle a bit, you're building a whole new gigantic int.

You also need to build other giant ints just to access single bits you're interested in - for example, composite and ~composite are huge in arr = arr & (~composite), even though you're only interested in 1 bit.

Use an actual mutable sequence type. Maybe a list, maybe a NumPy array, maybe some bitvector type off of PyPI, but don't use an int.

user_23571120
Related