- OT: A better sieve (was Re: Sieve of Erastosthenes optimized to the max) - 2 Updates
- MSVC-bug - 1 Update
| Tim Rentsch <tr.17687@z991.linuxsc.com>: Feb 16 08:06AM -0800 > I was implementing a version of that when something else occurred to > me. You can sacrifice speed for store size if you're prepared to do an > integer divide for every prime lookup. I explained before how numbers can be considered mod 30, of which only the residues { 1, 7, 11, 13, 17, 19, 23, 29 } are candidates, because all other residues are divisible by 2, 3, or 5. And very conveniently, there are exactly 8 of these residues, so one byte can be used to represent each block of 30 numbers (only 8 of which might be prime). That cuts down on the space needed. I also explained how the divides and remainders can be avoided, by taking advantage of the structure of how the numbers being considered are represented, and arranging that the difficult parts be done at compile time. I have an implementation (written in C) based on this approach that determines all primes less than roughly 51.75 billion, taking just under 56 seconds to complete. (No threading is used - code is all single threaded.) > operator[]. (certainly not the at function). And also I found myself > using emplace_back a lot. It's a PITA because you can only emplace > back a single item, and it is slow. My program is written in C and uses ordinary C arrays. I expect it could be converted to C++ without too much difficulty. |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 16 06:30PM +0100 Am 16.02.2024 um 17:06 schrieb Tim Rentsch: > determines all primes less than roughly 51.75 billion, taking just > under 56 seconds to complete. (No threading is used - code is all > single threaded.) On my 16 core PC this takes 1.73 seconds and 43 seconds overall CPU time without printing the numbers to a file. C:\Users\Boni\Documents\Source\bitmapSieve>timep "x64\Release-clang++\bitmapSieve.exe" 51750000000 "" real 1.729s user 43.094s sys 0.094s cylces 194.738.953.589 |
| Bonita Montero <Bonita.Montero@gmail.com>: Feb 16 09:17AM +0100 Am 15.02.2024 um 23:11 schrieb Paavo Helde: > Constructing and copying std::strings is allowed to allocate dynamic > memory. Make your string a bit longer and you will see allocations > also in Release builds. The small string optimization is nothing which is guaranteed. Initializing a function object with a reference_wrapper is guaranteed to be without memory allocation. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment