Sieving discussion thread

[cipher]

Originally Posted by geoff

You might be biting off more than you can chew with this range.

Edit: The sieve efficiency will decrease as the range on n increases.

Geoff: You are correct. I just Tested a range of approx 100n it was going @ a rate of 26,000 p/s vs 130Mil p/sec i get for individual n.

[MooooMoo]

Originally Posted by Ken_g6

I'll hazard an educated guess that each extra K takes 1/10 the time of the first K. That still means that testing each P will take about 500 times as long as normal for the same size range of candidates. How much longer does LLR take with those bigger K's? Twice as long? In that case, we're better off with a range of 10 or maybe 20 K's.

edit: You meant that each extra n takes 1/10th the time of the first n?

Anyway, we may still be better off with a range of 20000 n's than a range of 10 or 20 n's. The previous effort (for n=333333) reached a sieving depth of 25P with about 300 k per M. If this effort does 20000 times less work and only reaches a sieving depth of 1.25T, there'll be about 500 k per M. Bigger k's take about 70% longer to LLR than smaller ones, so sieving a huge range of n with smaller k's would be worth it in this case.

Even if those assumptions are off by a lot, it still wouldn't make sense to do a range of 10 or 20 n's - the benefits of shorter LLR testing times are gone once the k value is greater than a few M. Doing 10 or 20 n's would save a few days of LLR testing at most.

[Ken_g6]

Originally Posted by MooooMoo

edit: You meant that each extra n takes 1/10th the time of the first n?

Yep. I shouldn't post late at night, I always get something wrong.

Originally Posted by MooooMoo

Anyway, we may still be better off with a range of 20000 n's than a range of 10 or 20 n's...

Let's look at this mathematically. On one side, we have the proportion of time saved by shorter LLRs. You say that's 1.7 times as long. On the other side we have the time wasted by having more candidates to LLR. The time used by LLR is about 1+1/10*R, where R is the size of the range of n's. Assuming we're going to do a constant amount of sieve work, which may or may not be to the optimal point, let P be the prime we would get to with a single n.

Now the point we would get to with a range R is Pr = P/(1+1/10*R). The log of the ratio P/Pr = (1+1/10*R) gives the proportion of extra candidates to be tested with LLR. So assuming a given R will halve LLR time, we need ln(1+1/10*R) < 1.7. Exponentiate both sides to get 1+1/10*R < e^1.7 which is about 5.5. So R can maybe be 45.

Edit: I think it's actually the ratio of the logs, not the log of the ratio, but I still can't imagine it's big enough for 20,000 n's.

Originally Posted by MooooMoo

Even if those assumptions are off by a lot, it still wouldn't make sense to do a range of 10 or 20 n's - the benefits of shorter LLR testing times are gone once the k value is greater than a few M. Doing 10 or 20 n's would save a few days of LLR testing at most.

Right, one of my assumptions was that the possible R would get the K's low enough to get the LLR time down. So it's probably pointless to do more than just one n.

[axn]

Originally Posted by Ken_g6

Let's look at this mathematically. [snip]

The saving from sieving 20000 n's simultaneously is a factor of 1/10 per n. However, we lose a factor of 20000 (compared to single n). So, on the whole, sieving 20000n simultaneously to the same depth as one n, will take 2000x effort.

Let's say the optimal sieving point of single-n approach is 100P. For the same effort, we can, therefore get 20000 n's to 100P/2000 = 50T.

The ratio of number of candidates surviving after 50T vs 100P is:
[ln(100P)/ln(50T)]^2 = 1.54. So if the _average_ LLR for single n takes more than 1.54 times as much as _average_ LLR of 20000 n, the latter is more efficient. If not, the former is more efficient. [PS:- The 1/10 number may not be the actual number. We need to do benchmarks to figure out that factor]

[Ken_g6]

That's amazing! I had no idea how little a few extra orders of magnitude mattered on sieving. I guess I have a limited imagination.

One interesting thing to look at is what happens if the factor is 1. We do [ln(100P)/ln(5T)]^2 = 1.79, which is almost worth it by itself!

Now, I've done some benchmarks on an improved tpsieve, which is approximately twice as fast as V0.2.2 for large groups of N's. For my version, the ratio is about 1/62! So assuming your formula is right, that gets [ln(100P)/ln(310T)]^2 = 1.38.

Do we need to benchmark LLR, or has somebody already done that?

[Mini-Geek]

Originally Posted by gribozavr

Unfortunately, I don't know how to decompress lzma archives on Windows, but on a modern Linux system (Debian at least) you should already have lzma command.

7-zip can open just about anything, and uses the LZMA compression method for .7z by default, so it seems quite likely that it'll work. I'm downloading that file now to check if it can open it. I'll edit this with the results. Note that it doesn't associate .lzma with itself, so you need to open it manually.
Edit: It's not opening it, but perhaps the download was corrupted. I can't download again because I reached the download limit for free users (should reset in 12 minutes). Should the MD5 be 9A2F77A956D60BE4A84F088435CB9A62?

[mdettweiler]

Originally Posted by Mini-Geek

7-zip can open just about anything, and uses the LZMA compression method for .7z by default, so it seems quite likely that it'll work. I'm downloading that file now to check if it can open it. I'll edit this with the results. Note that it doesn't associate .lzma with itself, so you need to open it manually.
Edit: It's not opening it, but perhaps the download was corrupted. I can't download again because I reached the download limit for free users (should reset in 12 minutes). Should the MD5 be 9A2F77A956D60BE4A84F088435CB9A62?

7-Zip opens .lzma files just fine for me. I'm using v4.65, and even though in my case I have 7-zip associated with .lzma files, it should work fine even without that if you just navigate to the file in Z-Zip's file manager.

[gribozavr]

Originally Posted by Mini-Geek

Should the MD5 be 9A2F77A956D60BE4A84F088435CB9A62?

MD5 is correct.

[Mini-Geek]

I upgraded to 4.65 (from 4.57) and now it works. From http://www.7-zip.org/history.txt:

4.58 beta 2008-05-05
-------------------------
..
- 7-Zip now can unpack .lzma archives.
..

So if anybody is using 4.57 or older, upgrade and you can open the file.

[cipher]

The client is for Linux only? where is .exe for windows ken_g6.
thanks
cipher

Originally Posted by Ken_g6

That's amazing! I had no idea how little a few extra orders of magnitude mattered on sieving. I guess I have a limited imagination.

One interesting thing to look at is what happens if the factor is 1. We do [ln(100P)/ln(5T)]^2 = 1.79, which is almost worth it by itself!

Now, I've done some benchmarks on an improved tpsieve, which is approximately twice as fast as V0.2.2 for large groups of N's. For my version, the ratio is about 1/62! So assuming your formula is right, that gets [ln(100P)/ln(310T)]^2 = 1.38.

Do we need to benchmark LLR, or has somebody already done that?

[Ken_g6]

I was wondering when someone would ask about Windows. I'll look at making a 32-bit Windows .exe tomorrow. But I don't have a 64-bit Windows. Is there a gcc for 32-bit Windows or 32 or 64-bit Linux that will compile a 64-bit Windows binary? Or does someone want to compile it for me?

By the way, I just made another ~20% speed improvement to the 64-bit code. It now runs 4 times as fast as the 32-bit code for many-N sieves. I also tried the 64-bit code with "-t 4", and I think because it does most of its work in the processor registers, 4 threads seem to be as effective as two instances of 2 threads would be.