fbncsieve - a new fixed n sieve

rogue · 2017-11-26, 16:14

I am pleased to announce new sieving software designed to replace the fixed-k sieving functionality of newpgen. fbncsieve is a piece of software that I have been working on for a few weeks. It has a number of distinct advantages over newpgen including:

It is 2x to 2.5x faster than newpgen.
It is 64-bit, so it doesn't have the memory limitations you get with the newpgen bitmap.
The default output format is ABCD, which is much smaller than the newpgen format.
It can be compiled to run on Windows, Linux, and Mac.

There are two Windows executables included. One yes the FPU (the one ending in 87) for modular arithmetic, the other does not (the one ending in 86). In my testing they are close enough in speed that I can't determine if one is faster than the other. For some machines, I would expect that one will be faster than the other.

The usage is fairly simple. Here are some examples:

fbncsieve -k20e9 -K30e9 -sk*3^^10+1
fbncsieve -k1 -K1e6 -sk*57^10000-1 -P1e15 -x
fbncsieve -k1e6 -K5e6 -sk*1003^5-1 -ob1003e5.npg -fN
fbncsieve -ib1003e5.abcd -ob1003e5.npg -fN
fbncsieve -ik_b57_n1000-1.pfgw -P1e16 -okb57_n1000-1.abc -fA

The default maxp is 2^62, but fbncsieve will terminate at sqrt(kmax*b^n+/-c). fbncsieve will remove remove numbers that are prime from the output, so if kmin*b^n+/-c is prime and p > kmin*b^n+/-c, then kmin will still be in the output file. One thing I discovered in testing is that newpgen removes those k from the output file when b = 2, but does not if b != 2.

For those examples, in the first case, it will stop sieving at sqrt(kmax*b^n+/-c) and output the file k_b3_n10+1.pfbw in ABCD format. For the second, it will sieve to 1e15, verify factors, and output the file k_b57_n10000-1.pfgw in ABCD format. For the third, it will stop at sqrt(kmax*b^n+/-c) and output the file in newpgen format. For the fourth, it would convert from ABCD to newpgen format. If the input is not sieved deeply enough, it will continue sieving. For the last, it will continue sieving the input file to 1e16 (if not already sieved that deeply) and output a file in ABC format.

I have done a lot of testing and comparing outputs between newpgen and fbncsieve and outside of newpgen's base 2 bug, the only difference is when the software chooses the max p to sieve to. The max p is very close, but not exactly the same. It is likely due to small differences between newpgen's and fbncsieve's algorithms in the calculation. Since fbncsieve uses all integer arithmetic in the calculation and newpgen uses floating point arithmetic, I assume that fbncsieve is more accurate.

Of course, even though I done a lot of testing, it is always possible that something was missed. Please give it a spin and let me know if you run into any issues.

Although this will help Conjectures 'R Us more than any other project, I intend to use this code as the base to write a Mac/Linux version of fermfact.

ET_ · 2017-11-26, 18:05

Quote:

Originally Posted by rogue

Although this will help Conjectures 'R Us more than any other project, I intend to use this code as the base to write a Mac/Linux version of fermfact.

Now, that is worth a very BIG THANK YOU! :bow";bow"

axn · 2017-11-27, 03:05

The title says "fixed k", but all the examples appear to be the exact opposite, ie. "variable k" (aka fixed n).

Quote:

fbncsieve will remove remove numbers that are prime from the output, so if kmin*b^n+/-c is prime and p > kmin*b^n+/-c, then kmin will still be in the output file

I am confused - does it or does it not remove the number from output?

rogue · 2017-11-27, 13:46

Quote:

Originally Posted by axn

The title says "fixed k", but all the examples appear to be the exact opposite, ie. "variable k" (aka fixed n).

I am confused - does it or does it not remove the number from output?

I don't know what I was thinking when I wrote "fixed k". If someone could fix that, I would appreciate it.

If k*b^n+c is prime and k*b^n+c < max prime sieved, then k will be in the output file.

pepi37 · 2017-11-27, 14:16

Doesnot work for me on Win 7 x64
First you need to download two dll files ( can you compile it inside exe file) then crah with error 0x00000007 error code

rogue · 2017-11-27, 14:33

Quote:

Originally Posted by pepi37

Doesnot work for me on Win 7 x64
First you need to download two dll files ( can you compile it inside exe file) then crah with error 0x00000007 error code

I build with mingw64, which is what I use for most of the other executables I post.

Just in case this is something specific to my code, what command line arguments are you using?

pepi37 · 2017-11-27, 16:08

Quote:

Originally Posted by rogue

I build with mingw64, which is what I use for most of the other executables I post.

Just in case this is something specific to my code, what command line arguments are you using?

fbncsieve -k20e9 -K30e9 -sk*3^^10+1 ( try both versions)

rogue · 2017-11-27, 17:21

Quote:

Originally Posted by pepi37

fbncsieve -k20e9 -K30e9 -sk*3^^10+1 ( try both versions)

Works fine for me:

Code:

fbncsieve v1.0.0, a CPU program to find factors of k*b^n+c for fixed b, n, and c
Changing p_max to 42088836.  All remaining terms will be prime.
Sieve started: 1 < p < 42088836 with 1410065409 terms
  p=15485863, 4.896K p/sec, 9525905914 factors found, 46.64M f/sec, 36.8% percentDone. ETA 2017-11-27 11:22
Sieve completed at 42088836.  Writing terms file...
...429528886 terms written to k_b3_n10+1.pfgw
Clock time: 215.37 seconds at 11852 p/sec.  Primes tested 2552668.  Factors found: 9570471115.
Processor time: 210.14 sec. (0.02 sieving) (0.98 cores)

I suspect that the dlls you d/led are 32-bit or have another issue. As I stated you should install the mingw64 runtime.

pepi37 · 2017-11-27, 17:59

Quote:

Originally Posted by rogue

Works fine for me:

Code:

fbncsieve v1.0.0, a CPU program to find factors of k*b^n+c for fixed b, n, and c
Changing p_max to 42088836.  All remaining terms will be prime.
Sieve started: 1 < p < 42088836 with 1410065409 terms
  p=15485863, 4.896K p/sec, 9525905914 factors found, 46.64M f/sec, 36.8% percentDone. ETA 2017-11-27 11:22
Sieve completed at 42088836.  Writing terms file...
...429528886 terms written to k_b3_n10+1.pfgw
Clock time: 215.37 seconds at 11852 p/sec.  Primes tested 2552668.  Factors found: 9570471115.
Processor time: 210.14 sec. (0.02 sieving) (0.98 cores)

I suspect that the dlls you d/led are 32-bit or have another issue. As I stated you should install the mingw64 runtime.

I install the mingw64 runtime, restart windows, add GCC to the path... but still same error
There is tutorial how to add those DLL to exe code, so it can be independent

rogue · 2017-11-27, 18:14

Quote:

Originally Posted by pepi37

I install the mingw64 runtime, restart windows, add GCC to the path... but still same error
There is tutorial how to add those DLL to exe code, so it can be independent

Interesting. Which version of gcc? This is what gcc -v gives me:

Code:

Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=C:/Program\ Files/mingw-w64/7.1.0/mingw64/bin/../libexec/gcc/x86_64-w64-mingw32/7.1.0/lto-wrapper.exe
Target: x86_64-w64-mingw32
Configured with: ... excluding list of libraries ...
Thread model: posix
gcc version 7.1.0 (x86_64-posix-seh-rev2, Built by MinGW-W64 project)

This might be a stupid question, but are you running on a 64-bit OS? Can you build from source your own? The instructions are in the readme.txt file.

Do you try some of the other examples?

Is anyone else experiencing this problem?

pepi37 · 2017-11-27, 20:26

Quote:

Originally Posted by rogue

[/code]This might be a stupid question, but are you running on a 64-bit OS? Can you build from source your own? The instructions are in the readme.txt file.
Do you try some of the other examples?

Is anyone else experiencing this problem?

Doesnot work for me on Win 7 x64

2017-11-26, 16:14	#1
rogue "Mark" Apr 2003 Between here and the 14322₈ Posts	fbncsieve - a new fixed n sieve I am pleased to announce new sieving software designed to replace the fixed-k sieving functionality of newpgen. fbncsieve is a piece of software that I have been working on for a few weeks. It has a number of distinct advantages over newpgen including: It is 2x to 2.5x faster than newpgen. It is 64-bit, so it doesn't have the memory limitations you get with the newpgen bitmap. The default output format is ABCD, which is much smaller than the newpgen format. It can be compiled to run on Windows, Linux, and Mac. There are two Windows executables included. One yes the FPU (the one ending in 87) for modular arithmetic, the other does not (the one ending in 86). In my testing they are close enough in speed that I can't determine if one is faster than the other. For some machines, I would expect that one will be faster than the other. The usage is fairly simple. Here are some examples: fbncsieve -k20e9 -K30e9 -sk3^^10+1 fbncsieve -k1 -K1e6 -sk57^10000-1 -P1e15 -x fbncsieve -k1e6 -K5e6 -sk1003^5-1 -ob1003e5.npg -fN fbncsieve -ib1003e5.abcd -ob1003e5.npg -fN fbncsieve -ik_b57_n1000-1.pfgw -P1e16 -okb57_n1000-1.abc -fA The default maxp is 2^62, but fbncsieve will terminate at sqrt(kmaxb^n+/-c). fbncsieve will remove remove numbers that are prime from the output, so if kminb^n+/-c is prime and p > kminb^n+/-c, then kmin will still be in the output file. One thing I discovered in testing is that newpgen removes those k from the output file when b = 2, but does not if b != 2. For those examples, in the first case, it will stop sieving at sqrt(kmaxb^n+/-c) and output the file k_b3_n10+1.pfbw in ABCD format. For the second, it will sieve to 1e15, verify factors, and output the file k_b57_n10000-1.pfgw in ABCD format. For the third, it will stop at sqrt(kmaxb^n+/-c) and output the file in newpgen format. For the fourth, it would convert from ABCD to newpgen format. If the input is not sieved deeply enough, it will continue sieving. For the last, it will continue sieving the input file to 1e16 (if not already sieved that deeply) and output a file in ABC format. I have done a lot of testing and comparing outputs between newpgen and fbncsieve and outside of newpgen's base 2 bug, the only difference is when the software chooses the max p to sieve to. The max p is very close, but not exactly the same. It is likely due to small differences between newpgen's and fbncsieve's algorithms in the calculation. Since fbncsieve uses all integer arithmetic in the calculation and newpgen uses floating point arithmetic, I assume that fbncsieve is more accurate. Of course, even though I done a lot of testing, it is always possible that something was missed. Please give it a spin and let me know if you run into any issues. Although this will help Conjectures 'R Us more than any other project, I intend to use this code as the base to write a Mac/Linux version of fermfact.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sieving k * 2^n +- c with Nvidia GPU's for fixed k	diep	GPU Computing	5	2016-09-23 19:19
A siever for K (b, n, c fixed)?	pepi37	Software	7	2015-07-10 04:42
Sieving k*2^n-1 With Fixed n	c10ck3r	Riesel Prime Search	14	2013-02-03 00:19
User interface bug fixed on LLR V3.8.4	Jean Penné	Software	0	2011-01-22 16:47
KEP is reporting computer fixed	KEP	Twin Prime Search	3	2007-02-13 18:29

2017-11-27, 14:16	#5
pepi37 Dec 2011 After milion nines:) 1,451 Posts	Doesnot work for me on Win 7 x64 First you need to download two dll files ( can you compile it inside exe file) then crah with error 0x00000007 error code