Primes in π - Page 14

rogue · 2016-05-31, 17:56

Quote:

Originally Posted by Batalov

Incidentally, an interesting entry was added to PRPtop last month.
PIPrime(613373) (613373 digits, ...obviously) -- Adrian Bondrescu 05/2016

Nice. I wonder what kind of sieving he was doing.

LaurV · 2016-06-01, 02:53

Oooo! It pleases me to see Romanian names there! It means some people still do serious things in that country... (assuming he is not already in a western place, like a university or famous company already).

Congratulations mate!

paulunderwood · 2016-06-01, 18:31

Quote:

Originally Posted by Batalov

Incidentally, an interesting entry was added to PRPtop last month.
PIPrime(613373) (613373 digits, ...obviously) -- Adrian Bondrescu 05/2016

On my 4770k, I ran my gwnum-based program against it, to remove some of the doubt about it being a Carmichael, as only Fermat-PRP tests had been run on it. Since a=1 is minimal such that kronecker(a^2-4,n)==-1, I ran the following, which tests (x+2)^(n+1) == 5+1*2 (mod n, x^2-1*x+1):

Code:

time ~/coding/gwnum/s2 Pi_613373 1
Likely prime!

real	600m23.209s
user	392m46.660s
sys	0m4.616s

rogue · 2016-06-01, 19:03

After making some changes to the assembler code to not return data, I have been able to get pixsieve to work on Windows and OS X. You can download the source and Windows executable from here.

The -lmin option now works correctly and restarting from a pre-existing file should work as well, although it requires the -i option for the index file. I'll eventually eliminate that and let it use the pfgw file as the only input.

A few caveats. First, it fails on OS X with -O2, but will run correctly with -O1. I have an idea why, but I haven't investigated yet. Since the vast majority of time is spent in the asm code, there won't be much of a gain between -O1 and -O2. Second, multi-threading does not work on OS X. I suspect this is a problem in the use of semaphores. OS X has deprecated POSIX semaphores and uses what it calls a "dispatch semaphore". It is possible that I did not code that correctly. Third, it still fails to eliminate some composite numbers in the sieve. I don't know how many, but if it fails to eliminate them, then it might also be eliminating prime numbers. Nevertheless even with the caveats it is better than trying to factorize with pfgw and I know that it should eliminate 97% to 98% of the terms for many inputs fairly quickly.

I intend to eventually replace the sieving and threading code, but I don't know when I'm going to do that because that will be a lot more work.

J F · 2016-06-02, 17:01

Indeed it does not eliminate all composite factor candidates, I still
get lines like
p=13509635, 1.351M p/sec, 187 terms left, 13.5% done
p=35525635, 2.200M p/sec, 178 terms left, 35.5% done

Missing prime FCs: there is probably something going on with how work
is split up multithreaded.
I did some dozen runs with -sPi1M.txt -S110 -l15K -L20K -P1e8
-t1 always returns 135 terms remaining, missing a composite divisible by 14177
-t2, -t3, -t4 return either 134 or 135, sort of random
-t7 returns something between 134 and 193
-t15 always 135
'Always' means, in at least 6 test with this thread number I didn't see anything else.

But, unless it doesnt sort PRPs into the factored file, I dont mind much if
there is a composite slipping through occasionally - still way faster
than PFGW-TF!
Thanks a lot!

henryzz · 2016-06-02, 17:33

How hard would it be to design a sieve that would sieve any ABC/ABC2 file?

rogue · 2016-06-02, 19:03

Quote:

Originally Posted by J F

Indeed it does not eliminate all composite factor candidates, I still
get lines like
p=13509635, 1.351M p/sec, 187 terms left, 13.5% done
p=35525635, 2.200M p/sec, 178 terms left, 35.5% done

Missing prime FCs: there is probably something going on with how work
is split up multithreaded.
I did some dozen runs with -sPi1M.txt -S110 -l15K -L20K -P1e8
-t1 always returns 135 terms remaining, missing a composite divisible by 14177
-t2, -t3, -t4 return either 134 or 135, sort of random
-t7 returns something between 134 and 193
-t15 always 135
'Always' means, in at least 6 test with this thread number I didn't see anything else.

But, unless it doesnt sort PRPs into the factored file, I dont mind much if
there is a composite slipping through occasionally - still way faster
than PFGW-TF!
Thanks a lot!

I know that multi-threaded doesn't work and I know why. That will be fixed in 2.0. 2.0 will be built upon primesieve instead of the sieve originally written by Geoff Reynolds so it will eliminate the composite numbers being tested. It will also provide a factor removal rate.

rogue · 2016-06-02, 19:04

Quote:

Originally Posted by henryzz

How hard would it be to design a sieve that would sieve any ABC/ABC2 file?

A generic file? Fairly hard if you want any optimizations.

J F · 2016-06-02, 20:24

Factor removal rate? *perk up* Sounds interesting - with known PRP-test
runtimes I can probably use that to determine a better TF depth.

rogue · 2016-06-02, 20:30

I have posted 2.0 here. 1.2 is still available, for now. There are a number of differences from 1.2 as this framework for this version is completely different. For example you run with this pixsieve -P1e10 -l2000 -L3000 -C20000 -oterms.out -spi.txt -t4 -S15. -i is now used only for input when continuing a sieve, although I know that isn't working yet. Without -i, it will start a new sieve. -o is the output file that you use with pfgw. -C is new. Use that to tell the program how many chunks of primes each thread will get. The default is 5000, but you will want to play around with it to get optimal performance. The -r option is gone. The reporting time is 30 seconds. -F will output the factors to pixsieve.log The output file (right now) is only written upon ^C or reaching the end of the sieve.

Here is an example with the input and output:

Code:

/pixsieve -P1e8 -l20000 -L30000 -C20000 -oterms.out -spi.txt -t4 -S15
pixsieve v2.0, a CPU program to find factors of substrings of decimal string
Sieve started: (cmdline) 0 <= p < 100000000 with 2770 terms
1028569 | 15926535897932384626 . . . 24874754031617969941 (23005 digits)
2170583 | 15926535897932384626 . . . 79470269232297186832 (20386 digits)
. . . more factors . . .
56660377 | 15926535897932384626 . . . 66461900010350049018 (29467 digits)
  p=53533511, 100.9K p/sec, 2438 factors found at 0 secs/factor, 3.65 CPU cores, 53.5% done. ETA 02 Jun 15:18
64140539 | 15926535897932384626 . . . 89106524570802447493 (26469 digits)
. . .  more factors . . .
85822097 | 15926535897932384626 . . . 07248172987637569816 (20618 digits)
90358069 | 15926535897932384626 . . . 20599850235828918336 (28575 digits)

Sieve complete: 0 <= p < 100000000  6001455 primes tested
Clock time: 57.64 seconds at 104119 p/sec.  Factors found: 2445
Processor time: 210.24 sec. (0.10 init + 210.14 sieve).
CPU utilization: 3.65 (cores)
325 terms written to terms.out

So you can see the CPU utilization and modify the -C parameter to get better utilization. So with 4 threads, I got about 91% utilization of each core. The rate "p/sec" is "primes tested per second". It is not pmax - pmin, which most sieves do (and which makes little sense to me).

BTW, I fixed the issue with optimization not working on OS X. All I can say is that I find x86 assembly confusing and annoying to work with. Not being an expert means that I don't fully understand what some instructions will do.

J F · 2016-06-02, 21:09

Cool toy!

Note: v2.0 complained 3 DLLs missing (libgcc_s_seh-1, libstdc++-6
and libwinpthread-1 - someting MinGW-ish?). I could use the ones
from my SMPlayer (portable, so no DLLs registered system-wide)
Don't know how common these are on a non-programmers machine,
static link might be better for others who want to use this too.

2016-06-01, 19:03	#147
rogue "Mark" Apr 2003 Between here and the 11·577 Posts	After making some changes to the assembler code to not return data, I have been able to get pixsieve to work on Windows and OS X. You can download the source and Windows executable from here. The -lmin option now works correctly and restarting from a pre-existing file should work as well, although it requires the -i option for the index file. I'll eventually eliminate that and let it use the pfgw file as the only input. A few caveats. First, it fails on OS X with -O2, but will run correctly with -O1. I have an idea why, but I haven't investigated yet. Since the vast majority of time is spent in the asm code, there won't be much of a gain between -O1 and -O2. Second, multi-threading does not work on OS X. I suspect this is a problem in the use of semaphores. OS X has deprecated POSIX semaphores and uses what it calls a "dispatch semaphore". It is possible that I did not code that correctly. Third, it still fails to eliminate some composite numbers in the sieve. I don't know how many, but if it fails to eliminate them, then it might also be eliminating prime numbers. Nevertheless even with the caveats it is better than trying to factorize with pfgw and I know that it should eliminate 97% to 98% of the terms for many inputs fairly quickly. I intend to eventually replace the sieving and threading code, but I don't know when I'm going to do that because that will be a lot more work. Last fiddled with by rogue on 2016-06-01 at 19:04

2016-06-02, 20:30	#153
rogue "Mark" Apr 2003 Between here and the 11×577 Posts	I have posted 2.0 here. 1.2 is still available, for now. There are a number of differences from 1.2 as this framework for this version is completely different. For example you run with this pixsieve -P1e10 -l2000 -L3000 -C20000 -oterms.out -spi.txt -t4 -S15. -i is now used only for input when continuing a sieve, although I know that isn't working yet. Without -i, it will start a new sieve. -o is the output file that you use with pfgw. -C is new. Use that to tell the program how many chunks of primes each thread will get. The default is 5000, but you will want to play around with it to get optimal performance. The -r option is gone. The reporting time is 30 seconds. -F will output the factors to pixsieve.log The output file (right now) is only written upon ^C or reaching the end of the sieve. Here is an example with the input and output: Code: /pixsieve -P1e8 -l20000 -L30000 -C20000 -oterms.out -spi.txt -t4 -S15 pixsieve v2.0, a CPU program to find factors of substrings of decimal string Sieve started: (cmdline) 0 <= p < 100000000 with 2770 terms 1028569 \| 15926535897932384626 . . . 24874754031617969941 (23005 digits) 2170583 \| 15926535897932384626 . . . 79470269232297186832 (20386 digits) . . . more factors . . . 56660377 \| 15926535897932384626 . . . 66461900010350049018 (29467 digits) p=53533511, 100.9K p/sec, 2438 factors found at 0 secs/factor, 3.65 CPU cores, 53.5% done. ETA 02 Jun 15:18 64140539 \| 15926535897932384626 . . . 89106524570802447493 (26469 digits) . . . more factors . . . 85822097 \| 15926535897932384626 . . . 07248172987637569816 (20618 digits) 90358069 \| 15926535897932384626 . . . 20599850235828918336 (28575 digits) Sieve complete: 0 <= p < 100000000 6001455 primes tested Clock time: 57.64 seconds at 104119 p/sec. Factors found: 2445 Processor time: 210.24 sec. (0.10 init + 210.14 sieve). CPU utilization: 3.65 (cores) 325 terms written to terms.out So you can see the CPU utilization and modify the -C parameter to get better utilization. So with 4 threads, I got about 91% utilization of each core. The rate "p/sec" is "primes tested per second". It is not pmax - pmin, which most sieves do (and which makes little sense to me). BTW, I fixed the issue with optimization not working on OS X. All I can say is that I find x86 assembly confusing and annoying to work with. Not being an expert means that I don't fully understand what some instructions will do.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Mersenne Primes p which are in a set of twin primes is finite?	carpetpool	Miscellaneous Math	3	2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found	emily	Math	34	2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2	Mickey1	Miscellaneous Math	1	2013-05-30 12:32
A conjecture about Mersenne primes and non-primes	Unregistered	Information & Answers	0	2011-01-31 15:41
possible primes (real primes & poss.prime products)	troels munkner	Miscellaneous Math	4	2006-06-02 08:35

2016-06-01, 02:53	#145
LaurV Romulan Interpreter Jun 2011 Thailand 22613₈ Posts	Oooo! It pleases me to see Romanian names there! It means some people still do serious things in that country... (assuming he is not already in a western place, like a university or famous company already). Congratulations mate!

2016-06-02, 17:01	#148
J F Sep 2013 70₈ Posts	Indeed it does not eliminate all composite factor candidates, I still get lines like p=13509635, 1.351M p/sec, 187 terms left, 13.5% done p=35525635, 2.200M p/sec, 178 terms left, 35.5% done Missing prime FCs: there is probably something going on with how work is split up multithreaded. I did some dozen runs with -sPi1M.txt -S110 -l15K -L20K -P1e8 -t1 always returns 135 terms remaining, missing a composite divisible by 14177 -t2, -t3, -t4 return either 134 or 135, sort of random -t7 returns something between 134 and 193 -t15 always 135 'Always' means, in at least 6 test with this thread number I didn't see anything else. But, unless it doesnt sort PRPs into the factored file, I dont mind much if there is a composite slipping through occasionally - still way faster than PFGW-TF! Thanks a lot!

2016-06-02, 17:33	#149
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2³·3·5·7² Posts	How hard would it be to design a sieve that would sieve any ABC/ABC2 file?

2016-06-02, 20:24	#152
J F Sep 2013 2³·7 Posts	Factor removal rate? perk up Sounds interesting - with known PRP-test runtimes I can probably use that to determine a better TF depth.

2016-06-02, 21:09	#154
J F Sep 2013 2³×7 Posts	Cool toy! Note: v2.0 complained 3 DLLs missing (libgcc_s_seh-1, libstdc++-6 and libwinpthread-1 - someting MinGW-ish?). I could use the ones from my SMPlayer (portable, so no DLLs registered system-wide) Don't know how common these are on a non-programmers machine, static link might be better for others who want to use this too.