did you check that link? (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf)
The Total Count of the Primes in all of the blocks is 16,028,906,205.
The current time is: 11:23:40.00
The current time is: 9:17:42.04
-----------
02:05:57.96
Marco,
There are several things you can do.
1. Use an odd bit sieve - bits represent only the odd numbers like 1, 3, 5, 7 ... This gives you twice the numbers for the same memory block.
2. Set all bits, then reset all multiples of the prime numbers. Since 2 is not present, you save the time of resetting half of all of the bits.
3. Scan for a set bit, double and add 1 for the prime number, Square that prime for the first bit to reset, divide by 2 (shift right 1) to get the reset index, then reset the bit and add the prime number for the next bit to reset.Code: [Select]The Total Count of the Primes in all of the blocks is 16,028,906,205.
The current time is: 11:23:40.00
The current time is: 9:17:42.04
-----------
02:05:57.96
Dave.
My, people has switched to 64 bits.
jj2007 mentioned that shifting is slow, and with a few Tests I could see that it costs some time. So I was lucky to find bts, which can set a bit in memory without the c-stylisch mem[i/64] |= 1UL << i%64.
But still I have to add to my bit-position a number and then look if I got over 64-bit, in order to jump i/64 "lines" forward.
Do a search for 'Prime Number Circle' (Peter Plitcha)
This method seems to be simpler, and maybe faster.
8)
his nama is Peter Plichta (https://de.wikipedia.org/wiki/Peter_Plichta) and it seems to me that he's a weirdo.
i'm a little surprised to hear you say that, Gunther :biggrin:
it sounds to me like a case of people not listening to someone who's found something new
not the first time people laughed at the smart guy
but - he was talking about building a saucer-shaped spaceship - lol
he may have some unique ideas on fuel
so - let's allow him to build it - and see how it goes :biggrin:
to find prime numbers, I use this technique, I use a period of 30, where I avoid multiples of 3, I compute directly the first prime numbers less than 31, and I begin my cycle with 31, in a period of 30 you got 8 possible candidates to be primes, this period is divided in three parts a) numbers whose Lsb are 1, and 7 first decade, b) numbers with 1, 7, 3, 9 Lsb in the second decade, and c) numbers whose Lsb are 3, and 9, in a period of 30, you got 8 candidates to test for primes, I do the trial, testing to the limit of prime numbers less than some given p*p prime, begining testing with 7, is a pretty optimized algorithm. :biggrin:
Do a search for 'Prime Number Circle' (Peter Plitcha)
This method seems to be simpler, and maybe faster.
8)
Here is a link to the CodeProject, they had a long discussion about this back in Nov 2008.
http://www.codeproject.com/Messages/2815908/Wheel-Factorization-to-simplify-a-Sieve-of-Eratost.aspx
Dave.
Note: Primes 2, 3, 5, and 7 are removed.
(numbers in each group are read vertically)
positions:
000000000011111111112222222222333333333344444444
012345678901234567890123456789012345678901234567
offsets:
000000000000000000000011111111111111111111111112
011112233444556677788900001223334455666778899990
113793917137391713939713793171793917379391713799
primes from 000 to 209:
-00000000000000000000011111-1111-11111-111-1111-
-11112233444556677788900001-2333-45566-778-9999-
-13793917137391713939713793-7179-91737-391-1379-
primes from 210 to 419:
2-222222-2-2222222-2-3333--33-3333-33-333-34--44
1-222334-5-5667788-9-0111--33-4455-67-788-90--01
1-379391-1-7391713-3-7137--17-7939-73-939-71--99
primes from 420 to 629:
444-444-4444-4-44-455-55---55-5-5555-5-5566-666-
233-344-5666-7-89-900-22---44-5-6677-8-9900-111-
113-939-7137-9-71-939-13---17-7-3917-7-3917-379-
primes from 630 to 839:
6666-666--666-6-7-7-77-7-77777-77--7-7--88-88888
3444-556--778-9-0-0-12-3-34556-67--8-9--01-22223
1137-391--373-1-1-9-97-3-93171-93--7-7--91-13799
primes from 840 to 1049:
--0000--0000---00-0-000-0-0-000-0-00--1111-11-11
--8888--8888---99-9-999-9-9-999-9-99--0000-00-00
--5556--7888---01-1-234-4-5-677-8-99--0112-33-34
--3793--7137---71-9-971-7-3-717-3-17--9391-13-99
Sheldon Prime Sieve Method :biggrin:
base-210 isn't such a bad idea
if you are using each bit as odd number values, you are getting a "bit density" of 16 values per byte
by using base-210, you can get an equivalent bit density of 70 values per byte
48 positions is 3 bytes - you cover 210 values with 3 bytes of data
by following the pattern in the "offsets" list, you signifigantly speed up the sieve :t
001
011
013
017
019
023
029
031
037
041
043
047
053
059
061
067
071
073
079
083
089
097
101
103
107
109
113
121
127
131
137
139
143
149
151
157
163
167
169
173
179
181
187
191
193
197
199
209
------------0
001 01
011 11
013 13
017 17
019 19
023 23
029 29
031 31
------------35
037 02
041 06
043 08
047 12
053 18
059 24
061 26
067 32
------------70
071 01
073 03
079 09
083 13
089 19
097 27
101 31
103 33
------------105
107 02
109 04
113 08
121 16
127 22
131 26
137 32
139 34
------------140
143 03
149 09
151 11
157 17
163 23
167 27
169 29
173 33
------------175
179 04
181 06
187 12
191 16
193 18
197 22
199 24
209 34
that worked out nicely :biggrin:high order low order
base4294967296digit base35digit
in this case, we need to take the base-4294967296 digit and MOD 6 to figure out how to parse the low-order base-35 digit into bitshigh order low order
base4294967296digit
base35digit
mod6digit
the base-4294967296 digit can be used to address bytesmax file: 4gb
range: 140g = 150,323,855,360
high order low order
base4294967296digit base6digit base35digit
max file: 24gb
range: 840g = 901,943,132,160
which makes it a little tricky to address bytes, but it's do-able
high order low order
base4294967296digit base210digit
max file: 24gb
range: 840g = 901,943,132,160
i can MUL the high-order digit by 6 and add the offset to obtain the address
this keeps the number of DIV operations to a minimum