Algebraic factors in sieve files - Page 3

pepi37 · 2017-01-15, 18:09

Compromise: write a small program, ( portable to Linux and WIn) that will remove all other factors that can be removed. In that case, since we all believe at Batalov script it is not needed to have extensive testing, nor we touch ( and possibly broken) srxsieve :)

LaurV · 2017-01-17, 02:21

Quote:

Originally Posted by pepi37

Compromise: write a small program, ( portable to Linux and WIn) that will remove all other factors that can be removed. In that case, since we all believe at Batalov script it is not needed to have extensive testing, nor we touch ( and possibly broken) srxsieve :)

+1

rogue · 2017-01-17, 20:15

srsieve 1.0.8 searches for most of the same algebraic factors that the script finds and is able to find them, but there are two that srsieve does not search for.

pepi37 · 2017-01-17, 20:19

Quote:

Originally Posted by rogue

srsieve 1.0.8 searches for most of the same algebraic factors that the script finds and is able to find them, but there are two that srsieve does not search for.

So after all, we still must to run script in order to find those two, rest algebraic factors?

rogue · 2017-01-18, 02:11

Quote:

Originally Posted by pepi37

So after all, we still must to run script in order to find those two, rest algebraic factors?

Yes, but I will modify srsieve. As much as Gary or others do not want the code modified, they don't own the code. Adding these missing forms (or others) should be very easy to do.

pepi37 · 2017-01-18, 10:05

Quote:

Originally Posted by rogue

Yes, but I will modify srsieve. As much as Gary or others do not want the code modified, they don't own the code. Adding these missing forms (or others) should be very easy to do.

If you are willing to change code: then do it as needed, not do it partially. In that case running srsieve will do job and we dont need to bother does we or does we not have to run scripts after/before sieving. Of corse nobody cannot force you to do not change the code, but srsieve works very well and it is tested in many years of works.
Suggestion to write new, small program that will remove all factors ( from script) then is better option.

gd_barnes · 2017-01-20, 10:53

Quote:

Originally Posted by rogue

Yes, but I will modify srsieve. As much as Gary or others do not want the code modified, they don't own the code. Adding these missing forms (or others) should be very easy to do.

This is ridiculous and I would have responded sooner had I not been out of town. Frankly this statement hacks me off and we don't have to accept it. We don't own the program but you don't own CRUS! We do not have to accept the results of any sieving submission done with any more modified versions of srsieve. I thought that both Masser and I and now more lately Pepi as well as some of the other discussion in this thread made that blatantly clear. Masser was also an admin of base 5 at one point and can completely relate to this kind of frustration.

Yes "it seems" like the change should be very easy to do just like modifying them to previously remove algebraic factors should have been very easy to do before. But it wasn't because no parallel testing was performed. It's very easy to accidently remove incorrect factors. We ended up with multiple bases with multiple problems where there were far too few of primes reported. I remember one was either R35 or S35 for n=25K-50K where 10s of primes were missed and it was a big mess. Bases like that had to have ranges rerun specifically as a result of that change...and who knows how many more are out there that we have not discovered. It is very stressful to always be looking over our shoulder wondering if the programs that we are running are correct without knowing if they have been properly tested.

If you modify the code how can you prove to us that you have not affected anything else like what has happened in both PFGW and srsieve before and has caused us to have to rerun multiple bases? Do you have the personal time available to run multiple parallel tests on multiple different bases both with and without algebraic factors -or- to coordinate the effort to have others do it behind the scenes before releasing the new program to the public?

We do not want the program to be 2-3 months old and hear that usual line of "no problems have been reported so the code must be right". Frequently problems are not found for months or years and then it is realized that there are multiple incorrect outputs. That is not parallel testing. Here is what needs to happen with parallel testing:

(1)
Run base xxx that contains no algebraic factors with the old version of srsieve.
Do the same with the new version of srsieve.
Compare the two outputs. They must match.

Do the above with 4-5 different bases on both the Riesel and Sierp sides. Bases should be small, big, squares, cubes, etc. Make them as random as possible to include as many breaking points as possible. Assume that the program is bad and try to break the program. Do NOT assume that it is good and avoid testing it because the change "was easy".

(2)
Run base xxx that contains type 1 of algebraic factors (that the old version is currently removing) with the old version of srsieve.
Do the same with the new version of srsieve.
Compare the two outputs. They must match.

Also do the above with several different bases on both the Riesel and Sierp sides.

(3)
Run base xxx that contains type 2 of algebraic factors (that the old version is NOT currently removing) with the old version of srsieve.
Do the same with the new version of srsieve.
Compare the two outputs. The differences should be ONLY that the new version is removing the type 2 algebraic factors.

We need to see test plans and results such as this before the new program is released to the public.

If you modify srsieve without this kind of substantial testing being publicly posted in a place where the CRUS admins can see it BEFORE the program is publicly released, we will refuse to accept any sieving at CRUS that uses the new program. We will also make sure that other projects are aware of the risks involved in using the new program without proper testing having been done ahead of time.

Yes I am preaching in a big way but the integrity of CRUS and other prime search efforts needs people to step up and insist on accuracy in testing before using public programs that have had changes made with too little testing having been done.

Continuing to modify a known excellent program to do that which it was not intended to do is IMHO a mistake. The program was designed to remove hard numeric factors not algebraic factors. It should do no more. New programs have already been created for that.

LaurV · 2017-01-21, 07:25

Now slow down a little...

I am myself adept of "if it works do not fix it", and gave a +1 above to pepi's suggestion. But OTOH, I would like to have a new version of srsieve which is more efficient (and eventually removes the "all candidates are divisible by 2" bullshit

or let us skip it intentionally with a command line switch, or better offer command line switches for removing algebraic factors too). In that case, I am willing to be part of testing team, to do comparison testes as Gary suggested. And trust me, I do that testing activity for a living, if it is something good to say about a product, I may "forget" to say it, but if it is something to criticize, I am your man, I will always say it

Batalov · 2017-01-21, 18:32

Quote:

Originally Posted by LaurV

...to do comparison testes...

No adult male should skip on that activity!

Quote:

Originally Posted by LaurV

And trust me, I do that testing activity for a living, if it is something good to say about a product, ...

rogue · 2017-01-21, 19:19

CRUS is not the only user of srsieve. if CRUS chooses to use another program or some older version of srsieve, it is their choice.

I have posted an updated version of srsieve here. Here are the release notes:

Code:

  Rewrote code to find algebraic factorizations so that more can be caught.  It will search for:
     GFNs -> where k*b^n+1 can be written as x^m+1
     Trivial -> where k*b^n-1 can be written as x^m-1
  which will remove all terms for the sequence.

  These algebraic factorizations are now written to algebraic.out so that they can be verified with pfgw:
     where k*b^n+1 can be written as x^q*y^r+1 and r%q=0 and q is odd
     where k*b^n-1 can be written as x^q*y^r-1 and r%q=0
     where k*b^n+1 can be written as x*2^m+1 and m%4=2
     where k*b^n+1 can be written as 4*x^z*y^m+1 and z%4=0 and m%4=0

Note the second section. One can now verify the algebraic factors found by srsieve. I have run a few tests and haven't found any bugs, but that doesn't mean that there aren't any, but they will reveal themselves when running algebraic.out thru pfgw.

In this new release, it is smart enough to deteremine if k and b have the same root, i.e. k = m^x and b = m^y so that it can more easily identify GFN and Trivial forms.

For the first two forms, those algebraic factors are not written to algebraic.out. For GFNs, it doesn't mean that it has a factor, but that if you truly want to sieve GFNs, use gfnsieve, not srsieve.

For the first two forms logs to algebraic.out, it factorizes k and b and can find factorizations where they share a common factor. The previous release could not do that.

I suspect that the last two might have some generalizations, but I haven't investigated.

If Serge or others discover additional algebraic forms, please share and I will incorporate as best I can.

rogue · 2017-01-22, 00:42

Serge found a bug that causes it to crash for large ranges of n. I tested on smaller ranges of n, thus didn't trigger it. It has been fixed and the link has the current code and Windows build.

2017-01-21, 07:25	#30
LaurV Romulan Interpreter Jun 2011 Thailand 23×419 Posts	Now slow down a little... I am myself adept of "if it works do not fix it", and gave a +1 above to pepi's suggestion. But OTOH, I would like to have a new version of srsieve which is more efficient (and eventually removes the "all candidates are divisible by 2" bullshit or let us skip it intentionally with a command line switch, or better offer command line switches for removing algebraic factors too). In that case, I am willing to be part of testing team, to do comparison testes as Gary suggested. And trust me, I do that testing activity for a living, if it is something good to say about a product, I may "forget" to say it, but if it is something to criticize, I am your man, I will always say it Last fiddled with by LaurV on 2017-01-21 at 07:26 Reason: s/Bot/But/

2017-01-21, 19:19	#32
rogue "Mark" Apr 2003 Between here and the 2⁴×397 Posts	CRUS is not the only user of srsieve. if CRUS chooses to use another program or some older version of srsieve, it is their choice. I have posted an updated version of srsieve here. Here are the release notes: Code: Rewrote code to find algebraic factorizations so that more can be caught. It will search for: GFNs -> where kb^n+1 can be written as x^m+1 Trivial -> where kb^n-1 can be written as x^m-1 which will remove all terms for the sequence. These algebraic factorizations are now written to algebraic.out so that they can be verified with pfgw: where kb^n+1 can be written as x^qy^r+1 and r%q=0 and q is odd where kb^n-1 can be written as x^qy^r-1 and r%q=0 where kb^n+1 can be written as x2^m+1 and m%4=2 where kb^n+1 can be written as 4x^z*y^m+1 and z%4=0 and m%4=0 Note the second section. One can now verify the algebraic factors found by srsieve. I have run a few tests and haven't found any bugs, but that doesn't mean that there aren't any, but they will reveal themselves when running algebraic.out thru pfgw. In this new release, it is smart enough to deteremine if k and b have the same root, i.e. k = m^x and b = m^y so that it can more easily identify GFN and Trivial forms. For the first two forms, those algebraic factors are not written to algebraic.out. For GFNs, it doesn't mean that it has a factor, but that if you truly want to sieve GFNs, use gfnsieve, not srsieve. For the first two forms logs to algebraic.out, it factorizes k and b and can find factorizations where they share a common factor. The previous release could not do that. I suspect that the last two might have some generalizations, but I haven't investigated. If Serge or others discover additional algebraic forms, please share and I will incorporate as best I can.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
RSP Sieve Files for k*2^n-1 from PrimeGrid	pinhodecarlos	Riesel Prime Search	94	2021-05-19 02:36
Generalizing algebraic factors on Riesel bases	gd_barnes	Conjectures 'R Us	31	2010-04-06 02:04
Constructing a sieve for trial factors	davieddy	Math	48	2009-07-07 19:42
program to verify factors found by sr(x)sieve?	mdettweiler	Software	16	2009-03-08 02:06
Algebraic factors	henryzz	ElevenSmooth	13	2007-12-18 09:12

2017-01-15, 18:09	#23
pepi37 Dec 2011 After milion nines:) 2³·181 Posts	Compromise: write a small program, ( portable to Linux and WIn) that will remove all other factors that can be removed. In that case, since we all believe at Batalov script it is not needed to have extensive testing, nor we touch ( and possibly broken) srxsieve :)

2017-01-17, 20:15	#25
rogue "Mark" Apr 2003 Between here and the 2⁴×397 Posts	srsieve 1.0.8 searches for most of the same algebraic factors that the script finds and is able to find them, but there are two that srsieve does not search for.

2017-01-22, 00:42	#33
rogue "Mark" Apr 2003 Between here and the 2⁴·397 Posts	Serge found a bug that causes it to crash for large ranges of n. I tested on smaller ranges of n, thus didn't trigger it. It has been fixed and the link has the current code and Windows build.