Timeline for Sieve of Eratosthenes for small limits
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2018 at 18:24 | comment | added | P_P | It's a little slower than popcnt, but because counting the bits is done in a few ms. or so, it's fast enough: graphics.stanford.edu/~seander/… v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; | |
| Mar 11, 2018 at 17:44 | history | edited | Jamal | CC BY-SA 3.0 |
deleted 26 characters in body; edited title
|
| Mar 11, 2018 at 16:45 | comment | added | Will Ness | relative, of course not. I tried to run your code in ideone to compare the timings, but I don't know how to access POPCNT on gcc. | |
| Mar 11, 2018 at 16:27 | answer | added | P_P | timeline score: 0 | |
| Mar 11, 2018 at 16:17 | comment | added | P_P | @Will Ness: I should have said "one sieve makes an array of primes". It seems my i7 is that slow. I would be amazed if the relative times significantly changed on another system. | |
| Mar 11, 2018 at 13:14 | comment | added | Will Ness | @P_P I don't understand your times. if 4254 means 4.254 seconds, then it is way slower than what Ideone reports (3.75s). You have 3.6GHz i7, it can't be that slow. (?) | |
| Mar 11, 2018 at 13:10 | comment | added | Will Ness | @P_P Only one sieve returns primes? Which of the three? ;) Mine producing a correct count and value, I thought it must mean it's OK. | |
| Mar 10, 2018 at 14:26 | comment | added | P_P | @Will Ness: Times (ms) for 3 sieves. Limits: 1e9, 2e9, 4e9. WN: 4254, 9531, 19905. PP: 3135, 6801, 14555. KW: 2047, 4352, 9094. KW (primesieve.org/segmented_sieve.html). One sieve returns primes ;) | |
| Mar 10, 2018 at 0:11 | comment | added | Will Ness |
@P_P I used vector<bool> once, for nice and easy code, with comparable performance (to yours) on ideone (supposed to be slower than top boxes). And it's not even segmented. Runs at N^1.10 to your N^1.094, at the top range. (so, the same). See for yourself how simple it is. (N means upper limit; ~N^1.10 corresponds to ~n^1.16, in n the number of primes). vector<bool> got the bad rap for not being proper vector. Who cares, if it's doing the job.
|
|
| Mar 9, 2018 at 23:26 | comment | added | Will Ness |
@Quuxplusone log(2, 15.8/7.4) = 1.094. not 2.0. 15.8s up to 2^32 is respectable speed.
|
|
| Mar 9, 2018 at 23:13 | comment | added | Will Ness | @Quuxplusone one needn't suspect, just measure. :) Personally, I found that article's wording extremely confusing. The math there clarified things, though. | |
| Mar 9, 2018 at 16:46 | comment | added | P_P | My apologies, I didn't know, of course it will never happen again. My intention was to treat the remarks in your excellent answer. Unfortunately, I know now, it is not allowed. | |
| Mar 9, 2018 at 1:41 | comment | added | 1201ProgramAlarm | You should not be changing or improving the code in your question in response to any answers you get. This is specifically stated in the What should I do when someone answers my question in the help. | |
| Mar 8, 2018 at 22:42 | history | edited | P_P | CC BY-SA 3.0 |
Tried to handle the 1st answer.
|
| Mar 8, 2018 at 13:30 | answer | added | 1201ProgramAlarm | timeline score: 3 | |
| Mar 8, 2018 at 12:58 | history | edited | P_P | CC BY-SA 3.0 |
After reading the comments, improved the formatting.
|
| Mar 8, 2018 at 0:13 | comment | added | Loki Astari | @Edward The fastest runtime is obtained by copying and pasting the first 75 primes from primes.utm.edu/lists/small/10000.txt | |
| Mar 7, 2018 at 22:10 | comment | added | Edward | The fastest runtime is obtained if the sieve is constructed at compile time. See codereview.stackexchange.com/questions/93775/… | |
| Mar 7, 2018 at 21:17 | history | edited | P_P | CC BY-SA 3.0 |
Added time for primes < 2^31
|
| Mar 7, 2018 at 21:03 | comment | added | Quuxplusone | I recommend reading Melissa O'Neill's cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf and seeing whether what you've got really has the appropriate big-O performance. I haven't checked but I suspect you've got quadratic performance in there right now. | |
| Mar 7, 2018 at 21:01 | comment | added | Quuxplusone |
You're doing waaay too much on a single line, on many places in this code. Protip: any time you find yourself needing to write ;;, that's a sign you're doing something wrong, stylistically.
|
|
| Mar 7, 2018 at 20:45 | history | edited | P_P | CC BY-SA 3.0 |
improved formatting
|
| Mar 7, 2018 at 20:37 | review | First posts | |||
| Mar 7, 2018 at 21:13 | |||||
| Mar 7, 2018 at 20:35 | history | asked | P_P | CC BY-SA 3.0 |