Prime Sieve again - stumbling through quite a bit of memory

[Gunther]

Dave,

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   

that's another point. His spaceship may fly or not fly. I can't say much about that because my research interests are the Maxwell equations. But what he wrote about prime numbers and God's hidden formula (which he had found) sounds like nonsense to me. That was my point.

Gunther

[K_F]

It looks like he's pizzed off nearly all the scientific community because he's a renegade/rebel in the scientific world, telling them that they're 'barking up the wrong tree'.

In a way I agree with him, as the idea of science research is to simplify the world around us, whereas science seems to have made it more complicated and really messy - IOW something has gone wrong.
He has come up with hypothetical new theories/postulates, without any funding or research grants - and this is the BIG difference between himself and other researchers who are paid to come up with an 'answer'.
They're very scared of him, as if proven correct (which they're probably will not try to do as they're not going to shoot themselves in the foot..)  - there goes Quantum Theory..Relativity .. and a few other heavily funded theories.

There's a quote out there by someone I cannot remember - goes along the lines..
"All major advances in science are made by the rebels/outsiders"

I wouldn't dispel his theories just yet..
;)

[georg]

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) number 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, beginning testing with 7, is a pretty optimized algorithm. 

[georg]

I got to work with some code to make it in assembly, I haven't done that yet.

[georg]

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. 

that makes you think of the possibility of a finite quantity of prime numbers, due to the ever increasing possibility of finding non prime numbers as a combination of previous findings, but because Euler we know there are infinite prime numbers.

[KeepingRealBusy]

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.

[Gunther]

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.

interesting discussion. My impression is that a modified sieve algorithm will do the job.

Gunther

[dedndave]

Sheldon Prime Sieve Method   

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 35 values per byte
48 positions is 6 bytes - you cover 210 values with 6 bytes of data
by following the pattern in the "offsets" list, you signifigantly speed up the sieve   :t
~77% of all values are already eliminated

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

also, base conversion between binary and base-210 is fairly compact
each data byte can represent a base-210 digit

(C)opyright David R. Sheldon, November 4, 2013

[Gunther]

Dave,

Sheldon Prime Sieve Method   

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

excellent proposal. That'll do the job.

Gunther

[dedndave]

little snafu with my math - lol
48 positions is 6 bytes - doh !

[K_F]

There must be a way of doing this 'logically' (Har Har)..
Test bit-0..
- if == 0 then even >>> Not Prime unless 2
-Then Odd >> now comes the fun bit... just that I haven't thought about it yet!!  :t

There might be a pattern cycling through the bit positions from bit-1 upwards... thinking off my head  :icon_eek:
Possibly a prime pattern within the primes....
I always enjoyed watching those cartoons with my kids .. Prime Evil - I think he was from the Power Rangers series

[dedndave]

the steps follow these offsets

Code Select Expand

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

the Eratosthenes algorithm runs on multiples, not additive steps
i am trying to let the algo "fall into place" in my head - lol
it will come to me

i think the ling long kai fang base conversion algo will get me there

[dedndave]

well - i wanted to start by spliting those offsets into the 6 groups for each byte
a bit of luck - that went surprisingly well   :t
because of the fact that bytes have 8 bits, we can split the low-order base-210 into a base-6 digit and a base-35 digit
that way, we can use the base-6 digit to address 1 of 6 bytes and the base-35 digit to address bits
we can also use the base-6 digit to select the "parse" values for the base-35 values
you can do that by a set of look-up tables or by branching, i guess

nonetheless, when the offsets are split into 6 groups of 8....

Code Select Expand

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

so, it would seem that the best approach is to actually mix bases
a simple example...

Code Select Expand

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 bits

rather than constantly dividing to get the mod-6 "remainder", we can keep another high-order digit in parallel

Code Select Expand

high order             low order
base4294967296digit
                     base35digit
          mod6digit
the base-4294967296 digit can be used to address bytes
and, the mod-6 digit can be used to parse the low-order digit

the limits of the above method are

Code Select Expand

max file: 4gb
   range: 140g = 150,323,855,360

if we wanted a larger range, we could use a real mixture of bases - lol

Code Select Expand

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

[dedndave]

when it came to implementing this in code, i realized the best method is probably:

Code Select Expand

high order              low order
base4294967296digit  base210digit

max file: 24gb
   range: 840g = 901,943,132,160

then, i use a 210-element look-up table that has byte offsets (0-5) and bit masks
if the mod-210 digit is for a non-prime, the table entry is 0
i could use a word LUT, but i think i'll spend the extra 420 bytes to eliminate the size override operators   :P
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

[Gunther]

Dave,

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

good idea.  :t Go forward.

Gunther