mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2018-02-11, 00:05   #1
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×33×5×11 Posts
Default mtsieve

I am pleased to announce a sieving framework that encompasses many of the sieving programs I have written over the years. I call this framework mtsieve, short for multi-threaded sieve. You can get more information about from here.

Bundled with that framework are working 64-bit Windows versions of afsieve, mfsieve, pixsieve, fbncsieve, gfndsieve, and xyyxsieve. cksieve is also included, but doesn't work yet. It will take me a few days to get that working correctly. A makefile is included, so these programs can be built on OS X and Linux.

You are probably wondering why you should switch. The most important reason is that all of these support multi-threading (what I call workers) out of the box. The previous version of most of these programs did not have any support for multiple cores. Also of note is that fbncsieve (with one thread) is about 20% faster than the previous version of fbncsieve thanks to a optimization I borrowed from gfndsieve.

As always there might be some bugs, but I have done enough smoke testing for everything included (except cksieve) to feel confident that they are working.

Over the coming weeks I will be refining the documentation and fixing cksieve and addressing any issues that are reported. I expect a few issues, but not many. After that I will delve into porting the various OpenCL versions of my programs to this framework. I do not how I will do that yet, but I'm thinking about it.
rogue is offline   Reply With Quote
Old 2018-02-14, 04:12   #2
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×33×5×11 Posts
Default

The multi-threaded version of gfndsieve is not working correctly. It is possible the others are not as well. I need to do some more testing.
rogue is offline   Reply With Quote
Old 2018-02-14, 09:04   #3
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

101010000112 Posts
Default

Quote:
Originally Posted by rogue View Post
The multi-threaded version of gfndsieve is not working correctly. It is possible the others are not as well. I need to do some more testing.

It is possible the others are not as well. .... - your assumption is correct :)
And you have at least two more bugs ( that I found)
I will wait for fixed version. -W is option I am very interested to be in working state!
Great collection of tools! Thanks for them!

Last fiddled with by pepi37 on 2018-02-14 at 09:05
pepi37 is offline   Reply With Quote
Old 2018-02-14, 14:01   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22·33·5·11 Posts
Default

Quote:
Originally Posted by pepi37 View Post
It is possible the others are not as well. .... - your assumption is correct :)
And you have at least two more bugs ( that I found)
I will wait for fixed version. -W is option I am very interested to be in working state!
Great collection of tools! Thanks for them!
Please let me know the other bugs you found.
rogue is offline   Reply With Quote
Old 2018-02-15, 03:32   #5
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×33×5×11 Posts
Default

The testing I have done so far has not revealed a bug in finding factors, but there does appear to be a bug in what it output to the console. I can also say that the multi-threaded gfndsieve and fbncsieve programs perform poorly. Due to high factor density there is a bottleneck when removing candidate from the pool. I will look to see if there is anything I can do to address that.
rogue is offline   Reply With Quote
Old 2018-02-17, 13:08   #6
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

3×449 Posts
Default

Quote:
Originally Posted by rogue View Post
Please let me know the other bugs you found.
Output is always in pfgw format regardless what switch is used
-f --format=f format of output file (A=ABC, D=ABCD (default), N=NEWPGEN)
( to clarify -extension is always pfgw, but header doesnot match , so srfile cannot process file)
-W option doesnot work
-P value is not working

Quote:
C:\Users\Alpha-I7\Desktop\mtsieve>fbncsieve -P 1000000000000 -k1e4 -K1e6 -s k*3^^11+1 --format=A
fbncsieve v1.3, a program to find factors of k*b^n+c numbers for fixed b,n, and c and variable k
Changing p_max to 420890. All remaining terms will be prime.
Sieve started: 1 < p < 420890 with 990001 terms
Sieve completed at p=420899.
Processor time: 0.08 sec. (0.00 sieving) (0.35 cores)
59545 terms written to k_b3_n11+1.pfgw
Primes tested: 35458. Factors found: 930456. Remaining terms: 59545. Time: 0.22 seconds.

Last fiddled with by pepi37 on 2018-02-17 at 13:25
pepi37 is offline   Reply With Quote
Old 2018-02-17, 14:33   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

173416 Posts
Default

Quote:
Originally Posted by pepi37 View Post
Output is always in pfgw format regardless what switch is used
-f --format=f format of output file (A=ABC, D=ABCD (default), N=NEWPGEN)
( to clarify -extension is always pfgw, but header doesnot match , so srfile cannot process file)
-W option doesnot work
-P value is not working
For fbncsieve -P can be overridden by the program if it detects that you are sieving too deeply. In your example, it decides to sieve no deeper than sqrt(1000000*3^11+1). The message states that after sieving to that value, all remaining terms in the output file are prime. This is the exact same behavior as newpgen.

-W does work, but since the sieving in this example is not very deep, a second worker doesn't have any work as all of the primes tested are tested by the first worker. Try again with a larger n that requires much deeper sieving and you will see that.

-f and --format do work. .pfgw is just an extension. Although the programs formats output as documented, it doesn't change the file extension. I made no guarantees that srfile will be able to process the output from fbncsieve. Is there some reason that you need srfile to read the output from fbncsieve?

I have an update on the performance issue. This version of fbncsieve is still faster than the previous one that only supports a single thread which means that fbncsieve is not impacted. I have not looked at the gfndsieve code yet, but I clearly did something really bad when I ported the code into the framework.
rogue is offline   Reply With Quote
Old 2018-02-17, 14:47   #8
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

54316 Posts
Default

Quote:
Originally Posted by rogue View Post

I have an update on the performance issue. This version of fbncsieve is still faster than the previous one that only supports a single thread which means that fbncsieve is not impacted. I have not looked at the gfndsieve code yet, but I clearly did something really bad when I ported the code into the framework.
can you send that new version?
pepi37 is offline   Reply With Quote
Old 2018-02-17, 15:05   #9
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

22×33×5×11 Posts
Default

Quote:
Originally Posted by pepi37 View Post
can you send that new version?
The one bundled with the mtsieve download is the current version. There are no issues with it.

As for gfndsieve, I think I found the cause of the slowdown. I am going to make some changes and se if they improve the performance.
rogue is offline   Reply With Quote
Old 2018-02-17, 16:33   #10
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

25038 Posts
Default

Quote:
-o --outputterms=o output file of remaining candidates
-o --outputfactors=O output file with new factors
This second o ( for output factors ) should be big O


-i --inputterms=i input file of remaining candidates
-I --inputfactors=I input file with factors
-o --outputterms=o output file of remaining candidates
-o --outputfactors=O output file with new factors

this is cosmetic not true one bug

3 | 16127*10^1000000+1
3 | 16130*10^1000000+1
32463413 | 33589*10^1000000+1
15545081 | 20084*10^1000000+1
3 | 16133*10^1000000+1
3 | 16136*10^1000000+1
3 | 16139*10^1000000+1
3 | 16142*10^1000000+1
3 | 16145*10^1000000+1
3 | 16148*10^1000000+1
3 | 16151*10^1000000+1
3 | 16154*10^1000000+1
3 | 16157*10^1000000+1
3 | 16160*10^1000000+1
3 | 16163*10^1000000+1
3 | 16166*10^1000000+1
3 | 16169*10^1000000+1
3 | 16172*10^1000000+1
3 | 16175*10^1000000+1
3 | 16178*10^1000000+1
3 | 16181*10^1000000+1
3 | 16184*10^1000000+1
3 | 16187*10^1000000+1
3 | 16190*10^1000000+1
3 | 16193*10^1000000+1
15545417 | 40203*10^1000000+1
32471381 | 16246*10^1000000+1
3 | 16196*10^1000000+1
3 | 16199*10^1000000+1

I checked, and all factors are good, just not sorted

Last fiddled with by pepi37 on 2018-02-17 at 17:00
pepi37 is offline   Reply With Quote
Old 2018-02-17, 18:19   #11
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10111001101002 Posts
Default

I'll fix the -o/-O issue.

The factors will not be sorted, especially if using multiple workers. In fact when using multiple workers the factor is not necessarily the smallest factor. Neither are important to the functionality of the program.
rogue is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 01:44.

Thu Oct 22 01:44:43 UTC 2020 up 41 days, 22:55, 1 user, load averages: 1.68, 1.60, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.