mersenneforum.org Primes in π
 Register FAQ Search Today's Posts Mark Forums Read

2016-05-31, 17:56   #144
rogue

"Mark"
Apr 2003
Between here and the

2×53×61 Posts

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.

 2016-06-01, 02:53 #145 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 265016 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-01, 18:31   #146
paulunderwood

Sep 2002
Database er0rr

393410 Posts

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

Last fiddled with by paulunderwood on 2016-06-01 at 18:33

 2016-06-01, 19:03 #147 rogue     "Mark" Apr 2003 Between here and the 145028 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, 17:01 #148 J F     Sep 2013 23×7 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) 3·1,979 Posts How hard would it be to design a sieve that would sieve any ABC/ABC2 file?
2016-06-02, 19:03   #150
rogue

"Mark"
Apr 2003
Between here and the

2×53×61 Posts

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.

Last fiddled with by rogue on 2016-06-02 at 19:05

2016-06-02, 19:04   #151
rogue

"Mark"
Apr 2003
Between here and the

2·53·61 Posts

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.

 2016-06-02, 20:24 #152 J F     Sep 2013 23×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, 20:30 #153 rogue     "Mark" Apr 2003 Between here and the 11001010000102 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.
 2016-06-02, 21:09 #154 J F     Sep 2013 708 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Mickey1 Miscellaneous Math 1 2013-05-30 12:32 Unregistered Information & Answers 0 2011-01-31 15:41 troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 10:23.

Wed Dec 1 10:23:59 UTC 2021 up 131 days, 4:52, 1 user, load averages: 1.37, 1.23, 1.19