Sieve Discussion - Page 3

Citrix · 2007-03-26, 04:19

Quote:

Originally Posted by hhh

Free-time-Veto again. If somebody wants to do P-1, he can, but then correctly, please. It's still fast enough.

I agree.

I think there should be some LLR ranges in the LLR thread.

Do you plan to go beyond 5M? I might be able to make the sieve program faster, if you plan to.

hhh · 2007-03-26, 09:22

I plan to, if necessary, and if the interest in the project makes it possible. I would wait a month, though, before we decide about that and before you start heavy work. Up to now I'm very happy it is starting well.

As for the LLR-ranges, I will put some as soon as ET_ has done his P-1 job. The sieve-file will be updated this evening.

H.

ET_ · 2007-03-26, 16:50

Quote:

Originally Posted by hhh

As for the LLR-ranges, I will put some as soon as ET_ has done his P-1 job. The sieve-file will be updated this evening.

H.

Done!

Luigi

geoff · 2007-03-28, 00:40

I have implemented the algorithm described by Citrix in this post, with two small improvements:

1. When generating the table of powers 2^1, 2^2, ..., 2^max_gap (all mod p) I take advantage of the regularity of the gaps. For the project data all gaps are multiples of 6, so only 2^6, 2^12, ..., 2^max_gap (all mod p) need to be generated.

2. There are many more small gaps than large gaps, so while almost all of the entries in the first half of the above table are needed, in the second half there are many unused entries. I fill every entry in the first half, but only fill the needed entries in the second half.

Source and some binaries are here. To sieve for factors p in the range P0 < p < P1 run `gcwsieve -i <infile> -o <outfile> -f <factors_file> -p <P0> -P <P1>'.

It is a bit slower than the modified MultiSieve with the Windows machine that I tested it on, but it is better than nothing for Linux users. It may be faster on 64-bit Linux. Very little testing has been done.

I will try to fix any bugs reported, but I don't plan to spend much time making it faster unless I think of a big improvement to the main algorithm. Feel free to use anything in the source to improve MultiSieve (A lot of it is based on rogue's code anyway).

Citrix · 2007-03-28, 01:44

Quote:

Originally Posted by geoff

I have implemented the algorithm described by Citrix in this post, with two small improvements:

1. When generating the table of powers 2^1, 2^2, ..., 2^max_gap (all mod p) I take advantage of the regularity of the gaps. For the project data all gaps are multiples of 6, so only 2^6, 2^12, ..., 2^max_gap (all mod p) need to be generated.

2. There are many more small gaps than large gaps, so while almost all of the entries in the first half of the above table are needed, in the second half there are many unused entries. I fill every entry in the first half, but only fill the needed entries in the second half.

Modified multisieve already does this. I just din't mention it in the algorithm.

Citrix · 2007-03-28, 03:56

Quote:

Originally Posted by geoff

Reserving 150-160.

Do you plan to use your client?

@hhh, please keep track of program used for each range, in case there is a bug in one of the programs and we need to recheck the ranges etc...

geoff · 2007-03-30, 02:36

150-160 done, 13 factors (using gcwsieve 1.0.0).

Reserving 160-200.

Quote:

Originally Posted by Citrix

Do you plan to use your client?

Yes. I have a P3/800 that I can only get to run from a floppy disk, this project is ideal because the sieve and factors files are small. It does 62kp/s for the range above.

Citrix · 2007-03-30, 03:42

I get 62kps with your program on a 2.63 Ghz Intel celeron. What is wrong with the computer?

Any way to speed it up?

geoff · 2007-03-30, 04:00

Quote:

Originally Posted by Citrix

I get 62kps with your program on a 2.63 Ghz Intel celeron. What is wrong with the computer?

Any way to speed it up?

It seems to run slow on P4 machines, I have added an SSE2 version of the main loop in version 1.0.1, but it is still quite slow with GCC 3.4 which is all I have for the Windows build.

The Linux binaries built with GCC 4.1 are faster, but even there the P3 makes the P4 look sick.

Citrix · 2007-03-30, 04:36

Multisieve is also very slow on P4's. I suggest P-1/LLR for all users with P4's.

Any way to use the linux version on windows?

geoff · 2007-03-30, 04:45

Quote:

Originally Posted by Citrix

Multisieve is also very slow on P4's. I suggest P-1/LLR for all users with P4's.

Any way to use the linux version on windows?

It may be possible to compile with cygwin-gcc 4.1, but I don't have a cross-compiler, it needs to be done from Windows.

2007-03-28, 00:40	#26
geoff Mar 2003 New Zealand 13·89 Posts	Linux version I have implemented the algorithm described by Citrix in this post, with two small improvements: 1. When generating the table of powers 2^1, 2^2, ..., 2^max_gap (all mod p) I take advantage of the regularity of the gaps. For the project data all gaps are multiples of 6, so only 2^6, 2^12, ..., 2^max_gap (all mod p) need to be generated. 2. There are many more small gaps than large gaps, so while almost all of the entries in the first half of the above table are needed, in the second half there are many unused entries. I fill every entry in the first half, but only fill the needed entries in the second half. Source and some binaries are here. To sieve for factors p in the range P0 < p < P1 run `gcwsieve -i <infile> -o <outfile> -f <factors_file> -p <P0> -P <P1>'. It is a bit slower than the modified MultiSieve with the Windows machine that I tested it on, but it is better than nothing for Linux users. It may be faster on 64-bit Linux. Very little testing has been done. I will try to fix any bugs reported, but I don't plan to spend much time making it faster unless I think of a big improvement to the main algorithm. Feel free to use anything in the source to improve MultiSieve (A lot of it is based on rogue's code anyway).

2007-03-30, 04:36	#32
Citrix Jun 2003 3×5×107 Posts	Multisieve is also very slow on P4's. I suggest P-1/LLR for all users with P4's. Any way to use the linux version on windows? Last fiddled with by Citrix on 2007-03-30 at 04:37

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
SIEVE GAP	pepi37	Other Mathematical Topics	2	2016-03-19 06:55
Advantage of lattice sieve over line sieve	binu	Factoring	3	2013-04-13 16:32
Combined Sieve Guide Discussion	Joe O	Prime Sierpinski Project	35	2006-09-01 13:44
Sieve discussion Meaning of first/second pass, combined	Citrix	Prime Sierpinski Project	14	2005-12-31 19:39
New Sieve Thread Discussion	Citrix	Prime Sierpinski Project	15	2005-08-29 13:56

2007-03-26, 09:22	#24
hhh Jun 2005 373 Posts	I plan to, if necessary, and if the interest in the project makes it possible. I would wait a month, though, before we decide about that and before you start heavy work. Up to now I'm very happy it is starting well. As for the LLR-ranges, I will put some as soon as ET_ has done his P-1 job. The sieve-file will be updated this evening. H.

2007-03-30, 03:42	#30
Citrix Jun 2003 1605₁₀ Posts	I get 62kps with your program on a 2.63 Ghz Intel celeron. What is wrong with the computer? Any way to speed it up?