/** 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