Sieving discussion thread - Page 24

axn · 2009-08-13, 16:31

Quote:

Originally Posted by mdettweiler

50T? Hmm...that sounds a little high. For NPLB, we had an optimal depth of 30T for the range of k=2000-3400, n=50K-650K. Obviously TPS's sieve is a completely different type of range, though I would think that, since it's only for 480K-500K (even for a rather large range of k's), the optimal depth would be somewhat lower than that.

Is there any way to get tpsieve to produce an expected # of factors in a given range, a la sr(x)sieve? If we can get that information, calculating optimal depth is a rather straightforward matter.

<Back-of-the-envelope>
The optimal depth of Equivalent single-n effort would be 100P. The 20000n sieve is about 300x slower than single n sieve (5000n is about 75x slower --> extrapolating to 20000n). So you can sieve to 100P/300 or around 300T. Remove another factor of 1.5 (for more efficient LLR) and we get 200T. Really, a factor of two either way, and we'd be fine. So sieve to somewhere between 100T and 400T
</Back-of-the-envelope>

TimSorbet · 2009-08-13, 16:35

485000<n<490000, 200G<p<400G complete. 2,064,696 factors
http://www.sendspace.com/file/xirwwu

Quote:

Originally Posted by mdettweiler

Is there any way to get tpsieve to produce an expected # of factors in a given range, a la sr(x)sieve? If we can get that information, calculating optimal depth is a rather straightforward matter.

Wouldn't it simply be the expected # in the Riesel side + the expected # in the Sierp side, (ignoring anything like finding a factor in both the Riesel and Sierp sides for one candidate) which would be about twice the expected # in either side? All you should need to do is swap out the header with a one-sided version, feed it into sr(x)sieve, and double the expected # it says.

mdettweiler · 2009-08-13, 17:21

Quote:

Originally Posted by axn

<Back-of-the-envelope>
The optimal depth of Equivalent single-n effort would be 100P. The 20000n sieve is about 300x slower than single n sieve (5000n is about 75x slower --> extrapolating to 20000n). So you can sieve to 100P/300 or around 300T. Remove another factor of 1.5 (for more efficient LLR) and we get 200T. Really, a factor of two either way, and we'd be fine. So sieve to somewhere between 100T and 400T
</Back-of-the-envelope>

Oh, I see. That's much higher than I would ever expect for a multiple-fixed-k sieve; is this due to some sort of speed boost by sieving (multiple) fixed n's instead?

axn · 2009-08-13, 18:13

Quote:

Originally Posted by mdettweiler

Oh, I see. That's much higher than I would ever expect for a multiple-fixed-k sieve; is this due to some sort of speed boost by sieving (multiple) fixed n's instead?

I don't know the speed difference between srsieve (which sieves multiple k's for a large range of n) and tpsieve (which sieves multiple n's for a large range of k's) for this particular range size. Probably there is a speed boost (particularly since k >> n).

Ken_g6 · 2009-08-13, 22:33

I have one more update out (at the same link). 15% speed improvement for both 64-bit and 32-bit SSE2. Plus "quiet" can now be added to the config file.

I think that's as fast as it gets with this methodology. Although I think the regular 32-bit code could be improved with MMX, that would make any single-N sieve noticeably slower.

axn · 2009-08-13, 23:47

Quote:

Originally Posted by Ken_g6

I have one more update out (at the same link). 15% speed improvement for both 64-bit and 32-bit SSE2. Plus "quiet" can now be added to the config file.

Nice! Another 12% increase!

cipher · 2009-08-14, 02:31

Quote:

Originally Posted by Ken_g6

I have one more update out (at the same link). 15% speed improvement for both 64-bit and 32-bit SSE2. Plus "quiet" can now be added to the config file.

I think that's as fast as it gets with this methodology. Although I think the regular 32-bit code could be improved with MMX, that would make any single-N sieve noticeably slower.

Ken_g6 are you missing windows 64 bit client in the new folder? For windows all i see is tpsieve-x86-windows.exe & tpsieve-x86-windows_sse2.exe

also is there such a thing as 64 Bit SSE Enabled client? Same way we see improvement in 32 bit regular client vs 32sse enabled client.
thanks
cipher

Ken_g6 · 2009-08-14, 02:43

I still can't figure out how to make a 64-bit Windows client. The 64-bit MinGW has no instructions I can find. I tried using it like I do the 32-bit Windows MinGW: plop it in a directory in Linux and call that gcc directly, but it didn't work. Even if I made one, I couldn't test it.

cipher · 2009-08-14, 04:15

Quote:

Originally Posted by Ken_g6

I still can't figure out how to make a 64-bit Windows client. The 64-bit MinGW has no instructions I can find. I tried using it like I do the 32-bit Windows MinGW: plop it in a directory in Linux and call that gcc directly, but it didn't work. Even if I made one, I couldn't test it.

check with pschoefer i am using the 64 bit client he made. Hopefully he can help you.

Ken_g6 · 2009-08-14, 04:37

OK, I found a compiler for 32-bit Windows that I used in a VM to make a Win64 binary. It's in the zipfile; hopefully it works!

Edit: I tried SSE2 in Linux 64-bit; it didn't seem to do any better than the 32-bit SSE2.

pschoefer · 2009-08-14, 06:27

Quote:

Originally Posted by Ken_g6

OK, I found a compiler for 32-bit Windows that I used in a VM to make a Win64 binary. It's in the zipfile; hopefully it works!

Yes, it works. :)

2009-08-14, 04:37	#263
Ken_g6 Jan 2005 Caught in a sieve 5×79 Posts	OK, I found a compiler for 32-bit Windows that I used in a VM to make a Win64 binary. It's in the zipfile; hopefully it works! Edit: I tried SSE2 in Linux 64-bit; it didn't seem to do any better than the 32-bit SSE2. Last fiddled with by Ken_g6 on 2009-08-14 at 04:40

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
S9 and general sieving discussion	Lennart	Conjectures 'R Us	31	2014-09-14 15:14
Sieving discussion thread	philmoore	Five or Bust - The Dual Sierpinski Problem	66	2010-02-10 14:34
Combined sieving discussion	ltd	Prime Sierpinski Project	76	2008-07-25 11:44
Sieving Discussion	ltd	Prime Sierpinski Project	26	2005-11-01 07:45
Sieving Discussion	R.D. Silverman	Factoring	7	2005-09-30 12:57

2009-08-13, 22:33	#258
Ken_g6 Jan 2005 Caught in a sieve 18B₁₆ Posts	I have one more update out (at the same link). 15% speed improvement for both 64-bit and 32-bit SSE2. Plus "quiet" can now be added to the config file. I think that's as fast as it gets with this methodology. Although I think the regular 32-bit code could be improved with MMX, that would make any single-N sieve noticeably slower.

2009-08-14, 02:43	#261
Ken_g6 Jan 2005 Caught in a sieve 18B₁₆ Posts	I still can't figure out how to make a 64-bit Windows client. The 64-bit MinGW has no instructions I can find. I tried using it like I do the 32-bit Windows MinGW: plop it in a directory in Linux and call that gcc directly, but it didn't work. Even if I made one, I couldn't test it.