Smarandache-Wellin Primes - Page 2

rogue · 2015-11-05, 02:23

I've got GAS.

No me. My compiler. It is a syntax problem which is now fixed. Now if I could only figure out why the output are wrong...

LaurV · 2015-11-05, 05:40

I was thinking to that too, therefore I assumed automatically (without other knowledge) that you consider "odd prime" and not just "prime".
In this case, they end in 3, worth searching for.

rogue · 2015-11-05, 13:37

I tracked down my problem after learning a little bit about using lldb. Unfortunately I won't have time to fix it until Saturday.

fivemack · 2015-11-05, 14:47

Code:

        VFMADD132SD %xmm1, %xmm0, %xmm9

Since processors with FMA3 have AVX2 by definition, I don't quite understand why the code is dealing with one number at a time ... when I was trying to work out how to write the sieve in the shower this morning, I assumed you stored the number modulo 4 different primes in the 4 slots of a YMM register.

(4 registers for the number modulo each of 16 primes; 4 registers for the primes, 4 for the reciprocals, and one to store the magic number you add and subtract again to do the modulus)

rogue · 2015-11-05, 16:18

Quote:

Originally Posted by fivemack

Code:

        VFMADD132SD %xmm1, %xmm0, %xmm9

Since processors with FMA3 have AVX2 by definition, I don't quite understand why the code is dealing with one number at a time ... when I was trying to work out how to write the sieve in the shower this morning, I assumed you stored the number modulo 4 different primes in the 4 slots of a YMM register.

(4 registers for the number modulo each of 16 primes; 4 registers for the primes, 4 for the reciprocals, and one to store the magic number you add and subtract again to do the modulus)

I started with the code that Geoff Reynold's wrote as I figured that would save the most time WRT getting something written. My belief in that hasn't changed.

As for other optimizations, I haven't considered them as I don't know x86 asm. Trying to learn is made more difficult because different websites assume different syntaxes and most don't indicate which syntax they are using. Others have very cryptic documentation and most don't give good examples on how to use the instructions.

A quick search reveals that using the ymm registers requires Sandy Bridge. The computer I am writing and testing this code is too old. It is 64-bit, but not Sandy Bridge.

ewmayer · 2015-11-06, 01:24

Quote:

Originally Posted by rogue

A quick search reveals that using the ymm registers requires Sandy Bridge. The computer I am writing and testing this code is too old. It is 64-bit, but not Sandy Bridge.

AVX support (==> ymm registers) is not enough - that instruction requires FMA support, which means Haswell and beyond.

rogue · 2015-11-07, 02:17

I need to do some more testing, but I think that I'm ready to sieve. I was able to remove over 80% of the terms (below p(80000)) in about a minute. The main thing to test is that the factors are valid, but I also want to change how the inputs work.

rogue · 2015-11-07, 17:42

I'm sieving a range for all p < 1e7. After sieving to p=1e7 there are less than 60,000 terms left. I'll be loading up a server later today so I can keep my various cores busy with PRP testing as they finish up what they are currently working on. There are only about 3200 tests to reach the current limit of testing (p=407083 according to MathWorld) so I will be double-checking what has been tested to this point. I expect to reach that sometime Monday.

rogue · 2015-11-10, 01:16

I have tested all p < 510000 with no new PRPs and am continuing. I found a bug with the sieving code that caused it to miss factors. I had been wondering because finding factors were few and far between one I reached 1e6. The factors that it found were good so at least I don't need to add numbers to be tested. It also means that I can remove a lot more tests than what I thought. I was at about 58000 tests. It is now down to about 50000 and keeps going down.

ATH · 2015-11-10, 16:09

I started factoring shortly after this thread started with my own slow code. Only factoring to n=200,000 (p=2,750,159). Down to 14,315 candidates left after factoring to 388M, so that fits ok with ~50k up to p=10M.

rogue · 2015-11-10, 17:09

Quote:

Originally Posted by ATH

I started factoring shortly after this thread started with my own slow code. Only factoring to n=200,000 (p=2,750,159). Down to 14,315 candidates left after factoring to 388M, so that fits ok with ~50k up to p=10M.

It was down to 42,000 this morning. I am double-checking all factors with pfgw, but that takes a lot of time because pfgw evaluates the expression before applying the mod.

2015-11-05, 14:47	#15
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	Code: VFMADD132SD %xmm1, %xmm0, %xmm9 Since processors with FMA3 have AVX2 by definition, I don't quite understand why the code is dealing with one number at a time ... when I was trying to work out how to write the sieve in the shower this morning, I assumed you stored the number modulo 4 different primes in the 4 slots of a YMM register. (4 registers for the number modulo each of 16 primes; 4 registers for the primes, 4 for the reciprocals, and one to store the magic number you add and subtract again to do the modulus)

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Smarandache prime(s)	Batalov	And now for something completely different	90	2018-06-15 01:48
Distribution of Mersenne primes before and after couples of primes found	emily	Math	34	2017-07-16 18:44
Smarandache-Fibonacci Primes	rogue	And now for something completely different	5	2016-07-18 14:33
Smarandache semiprimes	sean	Factoring	15	2014-11-09 06:05
possible primes (real primes & poss.prime products)	troels munkner	Miscellaneous Math	4	2006-06-02 08:35

2015-11-05, 02:23	#12
rogue "Mark" Apr 2003 Between here and the 14313₈ Posts	I've got GAS. No me. My compiler. It is a syntax problem which is now fixed. Now if I could only figure out why the output are wrong...

2015-11-05, 05:40	#13
LaurV Romulan Interpreter Jun 2011 Thailand 258B₁₆ Posts	I was thinking to that too, therefore I assumed automatically (without other knowledge) that you consider "odd prime" and not just "prime". In this case, they end in 3, worth searching for.

2015-11-05, 13:37	#14
rogue "Mark" Apr 2003 Between here and the 18CB₁₆ Posts	I tracked down my problem after learning a little bit about using lldb. Unfortunately I won't have time to fix it until Saturday.

2015-11-07, 02:17	#18
rogue "Mark" Apr 2003 Between here and the 11·577 Posts	I need to do some more testing, but I think that I'm ready to sieve. I was able to remove over 80% of the terms (below p(80000)) in about a minute. The main thing to test is that the factors are valid, but I also want to change how the inputs work.

2015-11-07, 17:42	#19
rogue "Mark" Apr 2003 Between here and the 14313₈ Posts	I'm sieving a range for all p < 1e7. After sieving to p=1e7 there are less than 60,000 terms left. I'll be loading up a server later today so I can keep my various cores busy with PRP testing as they finish up what they are currently working on. There are only about 3200 tests to reach the current limit of testing (p=407083 according to MathWorld) so I will be double-checking what has been tested to this point. I expect to reach that sometime Monday.

2015-11-10, 01:16	#20
rogue "Mark" Apr 2003 Between here and the 11×577 Posts	I have tested all p < 510000 with no new PRPs and am continuing. I found a bug with the sieving code that caused it to miss factors. I had been wondering because finding factors were few and far between one I reached 1e6. The factors that it found were good so at least I don't need to add numbers to be tested. It also means that I can remove a lot more tests than what I thought. I was at about 58000 tests. It is now down to about 50000 and keeps going down.

2015-11-10, 16:09	#21
ATH Einyen Dec 2003 Denmark 3⁵·13 Posts	I started factoring shortly after this thread started with my own slow code. Only factoring to n=200,000 (p=2,750,159). Down to 14,315 candidates left after factoring to 388M, so that fits ok with ~50k up to p=10M.