Sunday, July 6, 2014

Sieve Timing Continued - A simpler method

After writing up all my sieve timing stuff yesterday, I was thinking of things I could do to add more information to my set of sieve times, and in an attempt to implement some additional optimizations, I realized a method that I probably should have realized a long time ago: instead of computing sub-list of primes based on square roots and such, why not just generate a list of primes in place? Somehow this never came to mind before, but this time it did, and lo and behold, it is about as fast or maybe faster than the recursive method (In the data I have it is much faster at 10^8, but I only ran one trial, so that information is sketchy). Most importantly though, the code is much simpler. The code is below:

/** For some reason this didn't occur to me for a really long time */
void smartestSieve(int bound, int* primes, int* primeslength) {
    primes[0] = 2; primes[1] = 3; primes[2] = 5; int mLength = 3;
    int n;
    for (n = 7; n < bound; n += 2 * ((2*n) % 3)) {
        int isprime = 1;
        int i;
        for (i = 2; i < mLength; ++i) {
            int p = primes[i];
            if (p*p > n) {
                break;
            } else if (n % p == 0) {
                isprime = 0;
                break;
            }
        }
        if (isprime) {
            primes[mLength++] = n;
        }
    }
    *primeslength = mLength;
}

Timing information is below, first, I slotted it into the original graph, removing the two slowest methods:

 And, to emphasize the "part that matters", its comparison with the recursive method:

The information used to generate these graphs is now on the second page of the sheet linked to in the previous post, https://docs.google.com/spreadsheets/d/18-avzFTZDDOPMh7p_FRPOVc9SVfEhxPEoVFGQPTyNWk/edit?usp=sharing

I am now considering looking at the advantages of hand tooled assembly and/or comparing the same methods in Python.

No comments:

Post a Comment