Timeline for Parallel sieve of Eratosthenes
Current License: CC BY-SA 3.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:40 | history | edited | CommunityBot |
replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
|
|
| Sep 3, 2016 at 22:50 | comment | added | Will Ness |
@NiklasB. a. not 1..maxp; sqrt(maxp)..maxp, as we already have primes below sqrt(maxp). b. dividing into equal-sized chunks will create skewed workload distribution because lower chunks need fewer primes (only up to sqrt(toplimit(chunk)) ).
|
|
| May 20, 2014 at 8:50 | history | edited | Vogel612 |
edited tags
|
|
| Apr 13, 2014 at 21:37 | comment | added | Niklas B. | @LokiAstari Obviously it seems impossible to understand the algorithm as I expressed it, so there must be a particular part about my explanation that is not easy to follow | |
| Apr 13, 2014 at 21:36 | comment | added | Loki Astari | @NiklasB.: How can I know what assumptions you have made. I can't read your mind. | |
| Apr 13, 2014 at 21:35 | comment | added | Niklas B. | @LokiAstari Please enlighten me what assumption is left unsaid here, I'm willing to clarify but unwilling to write code (because that's a lot more work than describing an idea in an abstract way) | |
| Apr 13, 2014 at 21:33 | comment | added | Loki Astari | You are not. Because there are so many assumptions being left unsaid. The only way to express them is to write the code. After that we can comment on its validity as a solution. | |
| Apr 13, 2014 at 21:32 | comment | added | Loki Astari | @NiklasB.: English is a very imprecise language. Which is why we have programming languages and mathematics which can express the same meaning much more accurately and in a more compact form. So if you can't express the program in the comment section you definately can not express the same meaning in English in the same space. (unless what you are trying to express is exceedingly trivial and parallel programs are not trivial and have many issues that are not apparent in English because it lacks the context and a lot of definition). So even though you think you are explaining something .... | |
| Apr 13, 2014 at 21:14 | comment | added | Niklas B. | @LokiAstari The algorithm there contains way more than is necessary for the implementation I have in mind. You just need a list of primes in the range 1..sqrt(maxp). That list can be computed using SoE (recursively with parallelization threshold or just sequentially using OPs algorithm). Then you divide the range [1..maxp] into evenly sized chunks of size maxp/p where p is the number of processors. You can process the chunks independently. | |
| Apr 13, 2014 at 21:08 | comment | added | Loki Astari | @NiklasB.: Its interesting that you think that one sentence written by you is the same as a whole page of detailed algorithms by somebody else? :-) | |
| Apr 13, 2014 at 20:53 | comment | added | Niklas B. | @Loki I feel that my comment is already detailled enough that one could implement the algorithm using only the information in it. The idea is that each composite in the range [X, Y] has at least one prime factor <= sqrt(Y). More information can be found in the internet, for example here | |
| Apr 13, 2014 at 19:46 | comment | added | Loki Astari | @NiklasB.: I am sure you can effectively paralyze the finding of primes. I think your comment is lacking any details and thus not worth commenting on. If you actually supplied the code then we can discuss further. | |
| Apr 13, 2014 at 15:24 | history | edited | Morwenn | CC BY-SA 3.0 |
Added a link to the follow-up question.
|
| Apr 13, 2014 at 10:36 | vote | accept | Morwenn | ||
| Apr 13, 2014 at 10:30 | answer | added | Morwenn | timeline score: 8 | |
| Apr 13, 2014 at 8:46 | answer | added | gnasher729 | timeline score: 12 | |
| Apr 13, 2014 at 5:12 | comment | added | Niklas B. | @LokiAstari Actually if you precompute the primes up to sqrt(maxp), you can then partition the sieving space evenly between the processors and get no contention at all. The same trick works to make the sequential sieve algorithm much more cache-efficient. | |
| Apr 13, 2014 at 0:41 | comment | added | vzn | +1; parallelism in prime searching is a very interesting advanced idea & wonder if there is more scientific analysis of this somewhere...refs anyone? anyway note that the science of prime detection in general is highly advanced and theoretical and sieve of eratosthenes while respectable as a programming exercise is regarded by experts as basically a "toy" algorithm for the problem... my understanding GNFS is the leading/typical algorithm, wonder if it has been parallelized by anyone? | |
| Apr 12, 2014 at 23:10 | history | tweeted | twitter.com/#!/StackCodeReview/status/455120848140394496 | ||
| Apr 12, 2014 at 20:44 | answer | added | Loki Astari | timeline score: 16 | |
| Apr 12, 2014 at 20:25 | answer | added | Edward | timeline score: 22 | |
| Apr 12, 2014 at 20:12 | comment | added | Morwenn | My computer isn't even a multicore to start with. It would probably have troubles beating the cache-friendly sequential approach with threads. | |
| Apr 12, 2014 at 20:06 | comment | added | Morwenn | @LokiAstari No I didn't time it. Actually, I didn't care at all about speed, I just wanted to write a multithread program and get it reviewed for the sole purpose of learning. | |
| Apr 12, 2014 at 20:03 | comment | added | Loki Astari | Have you timed this? It would surprise me if a parallel sieve is faster because of the memory contention. The speed up you receive from cached memory over real memory seem more likely to give you a speed up (as you can't do as much local caching with threads as different threads may be on different cores and you need to keep pushing things backwards and forwards across caches and memory). | |
| Apr 12, 2014 at 19:49 | answer | added | Nobody moving away from SE | timeline score: 23 | |
| Apr 12, 2014 at 19:33 | history | asked | Morwenn | CC BY-SA 3.0 |