mtsieve

rogue · 2018-02-11, 00:05

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 · 2018-02-14, 04:12

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.

pepi37 · 2018-02-14, 09:04

Quote:

Originally Posted by rogue

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!

rogue · 2018-02-14, 14:01

Quote:

Originally Posted by pepi37

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 · 2018-02-15, 03:32

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.

pepi37 · 2018-02-17, 13:08

Quote:

Originally Posted by rogue

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.

rogue · 2018-02-17, 14:33

Quote:

Originally Posted by pepi37

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.

pepi37 · 2018-02-17, 14:47

Quote:

Originally Posted by rogue

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?

rogue · 2018-02-17, 15:05

Quote:

Originally Posted by pepi37

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.

pepi37 · 2018-02-17, 16:33

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

rogue · 2018-02-17, 18:19

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.

2018-02-11, 00:05	#1
rogue "Mark" Apr 2003 Between here and the 2⁶×3²×13 Posts	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.

2018-02-14, 04:12	#2
rogue "Mark" Apr 2003 Between here and the 2⁶×3²×13 Posts	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.

2018-02-15, 03:32	#5
rogue "Mark" Apr 2003 Between here and the 2⁶×3²×13 Posts	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.

2018-02-17, 18:19	#11
rogue "Mark" Apr 2003 Between here and the 16500₈ Posts	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.