mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-11-26, 16:14   #1
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·3,001 Posts
Default 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:
  1. It is 2x to 2.5x faster than newpgen.
  2. It is 64-bit, so it doesn't have the memory limitations you get with the newpgen bitmap.
  3. The default output format is ABCD, which is much smaller than the newpgen format.
  4. 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.
rogue is offline   Reply With Quote
Old 2017-11-26, 18:05   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

12A316 Posts
Default

Quote:
Originally Posted by rogue View Post
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"
ET_ is offline   Reply With Quote
Old 2017-11-27, 03:05   #3
axn
 
axn's Avatar
 
Jun 2003

23×3×199 Posts
Default

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?
axn is online now   Reply With Quote
Old 2017-11-27, 13:46   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·3,001 Posts
Default

Quote:
Originally Posted by axn View Post
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.
rogue is offline   Reply With Quote
Old 2017-11-27, 14:16   #5
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

23×132 Posts
Default

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
pepi37 is offline   Reply With Quote
Old 2017-11-27, 14:33   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

135628 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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?
rogue is offline   Reply With Quote
Old 2017-11-27, 16:08   #7
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

25108 Posts
Default

Quote:
Originally Posted by rogue View Post
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)
pepi37 is offline   Reply With Quote
Old 2017-11-27, 17:21   #8
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

600210 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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.
rogue is offline   Reply With Quote
Old 2017-11-27, 17:59   #9
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

101010010002 Posts
Default

Quote:
Originally Posted by rogue View Post
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

Last fiddled with by pepi37 on 2017-11-27 at 18:00 Reason: Add more info
pepi37 is offline   Reply With Quote
Old 2017-11-27, 18:14   #10
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·3,001 Posts
Default

Quote:
Originally Posted by pepi37 View Post
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?
rogue is offline   Reply With Quote
Old 2017-11-27, 20:26   #11
pepi37
 
pepi37's Avatar
 
Dec 2011
After milion nines:)

23×132 Posts
Default

Quote:
Originally Posted by rogue View Post
[/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
pepi37 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 03:12.

Wed Nov 25 03:12:39 UTC 2020 up 76 days, 23 mins, 4 users, load averages: 1.72, 1.56, 1.41

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.