4
\$\begingroup\$

I'm trying to teach myself some Cython. To do so, I use Project Euler #10:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. 2 Find the sum of all the primes below two million.

My Cython code is:

from libcpp.vector cimport vector
from libcpp cimport bool

SOLL = 142913828922

def run(unsigned long top = 2000000):

    cpdef unsigned long ist = 2
    cdef vector[bool] pos
    pos.resize(top, True)
    top //= 2

    # reduced_prime is (prime - 1)/2, since all primes (except 2) are uneven
    cpdef unsigned long reduced_prime, ind, prime

    for reduced_prime in range(1, top):
        if pos[reduced_prime]:
            prime = reduced_prime*2 + 1

            for ind in range(prime + reduced_prime, top, prime):
                pos[ind] = False

            ist += prime

    return ist

which needs about .19s to run. The following C++ code only needs .01s:

#include <vector>
#include <iostream>

int main() {
    unsigned long top = 2000000;
    unsigned long ist = 2;

    std::vector<bool> pos(top, 1);
    top /= 2;

    for (unsigned long reduced_prime = 1; reduced_prime < top; reduced_prime++) {
        if (pos[reduced_prime]) {
            unsigned long prime = reduced_prime*2 + 1;

            for (unsigned long ind = prime + reduced_prime; ind < top; ind += prime) {
                pos[ind] = 0;
            }

            ist += prime;
        }
    }

   std::cout << ist << std::endl;
}

Therefore I'm under the impression my Cython code is suboptimal.

For the off-chance it matters, Cython code was compiled with:

cython src/e010.pyx -3 --cplus -o src/e010.cpp
g++ -shared -pthread -fPIC -fwrapv -O2 -Wall -fno-strict-aliasing -I/usr/include/python3.2mu src/e010.cpp -o src/e010.so

C++ code was compiled by:

g++ e10.cpp -O2 -o e10

Timings are taken with time on Ubuntu 12.04.

\$\endgroup\$
2
\$\begingroup\$

Change the inner loop to use old Pyrex syntax:

        for ind from prime + reduced_prime <= ind < top by prime:
            pos[ind] = False

Apparently Cython still does not optimize range loops to pure C when step size is a variable: ticket #546.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.