Sieving discussion thread

[geoff]

In tpsieve version 0.3.0 I have tried to extend the new algorithm (see posts by ken_g6 and biwema above), here is an outline.

If m is maximised subject to kmax*2^{m-1} < pmin, then the n-range can be processed in steps of size m. Each step takes about the same time regardless of the step size, so the sieve becomes progressively faster as the factor size increases.

E.g. for the current sieve where kmax < 2^20 and n-range of 20001: sieving for factors 2^50 < p < 2^51 would need ceiling(20001/31) = 646 steps, factors 2^51 < p < 2^52 would need ceiling(20001/32) = 626 steps, etc.

Ken: I will use odd minor version numbers from now on, could you use even numbers for your versions? 0.3.0 has none of your SSE2 or other optimisations, so I am sure you will be able to make it a lot faster.

[geoff]

tpsieve 0.3.1 just adds the --quiet option to 0.3.0.

[biwema]

It is quite an effort to calculate that (for example)

1234567891 divides 869660759 * 2^480000+1

with this information, the coefficients for 480001, 480002 etc can easily be determined:

I don't know if the sieving sortware already takes advantage of consecutive exponents.

869660759 + 1234567891 = 2104228650

this number is even, so the factor 2 can be taken into the exponent:

2104228650 / 2 = 1052114325

1234567891 divides 1052114325 *2^480001+1

and so on...
1052114325 + 1234567891 = 2286682216

1143341108 * 2^480002+1
571670554 * 2^480003+1
285835277 * 2^480004+1
(add p)
760201584 * 2^480005+1
380100792 * 2^480006+1
190050396 * 2^480007+1
95025198 * 2^480008+1
47512599 * 2^480009+1
(add p)
641040245 * 2^480010+1
937804068 * 2^480011+1
468902034 * 2^480012+1
234451017 * 2^480013+1

and so on.
Looks somewhat like implementing an algorithmus for the 3n+1 problem.

Whenever k gets less than 10 million, it can be looked up in the database of candidates.

The same needs to be done with the the -1 part of the twin candidates.

Even if it is a speedup, it is still slower than sieving a single exponent.
Therefore it is useful to spend more time in removing composite p (deeper sieving of p or do some prp).
I assume tthe software is optimised in this point.

If several exponents are grouped together, a multiple of p needs to be added,
that the sum is divisible by 2^n (for example 20 or 31).
I am not sure if finding that multiple is so quick that the advantage of grouping exponent is not cancelled out.

[henryzz]

Does anyone have any scripts for starting newpgen sieving twins for multiple ns? I then want to be able to put the file into tpsieve.

[Ken_g6]

I have Version 0.3.2 out. I'd like the minor-minor version to be even, but the version number above that to be the same, since it's derived mostly from tpsieve-0.3.0. Very nice algorithm, by the way. The new version is (I think) no faster in 64-bit, but the 32-bit versions are 70% as fast as 64-bit with SSE2, or 45% as fast without it.

Biwema, I couldn't parse everything you said, but even tpsieve-0.2.1 took advantage of consecutive exponents.

Henry, can't you just set the "when complete automatically increment N by 1" and "Stop when N gets to..." options? Or are you looking for a script to merge the files after that?

[henryzz]

Originally Posted by Ken_g6

Henry, can't you just set the "when complete automatically increment N by 1" and "Stop when N gets to..." options? Or are you looking for a script to merge the files after that?

i forgot about them
i am used to using newpgen in windows and i have never used those features although i have noticed them

[Ken_g6]

One more new version, Version 0.3.4 adds a new, 10-15% faster SSE2 algorithm for most inputs. Anything the current TPS seive is doing qualifies.

By the way, this code should be good on a P4 (as much as anything can be on a P4 ) and Athlon64.

Edit: I meant to add that my 64-bit code is just slightly faster than Geoff's (in both 0.3.2 and 0.3.4).

[henryzz]

Would "ABC $a*2^$b-1 & $a*2^$b+1 // {number_primes,$b,1}" stop searching a n after a twin has been found for it or would it stop searching after one riesel prime was found?

edit: from testing with an ABC2 file it stops after 1 riesel prime
Is there a way in PFGW of doing what i want without a complicated script?

[Ken_g6]

I've seen some discussion about where to stop this sieve, with values ranging from 50-100T. So I decided to do the math and try to find where to actually stop.

I found 600,000 factors in my 17T-22T test, in roughly one day (actually less) on 4 cores (well, Core 2's). Let's say half of the factors my test found were unique. Then using axn's formula (thanks again!):

(ln(22*10^12)/ln(17*10^12))^2-1 = 300000/x

x*((ln(22*10^12)/ln(17*10^12))^2-1) = 300000

x = 300000/((ln(22*10^12)/ln(17*10^12))^2-1) =~ 18M

So, assume 1T at this level takes 1 day on one core that can find 60*24/6 = 240 LLR results in the same time.

So F = 18M*((ln((S+L)*10^12)/ln(S*10^12))^2-1)
F = 18M*((ln((S+L)*10^12)/ln(S*10^12))^2-1)

For spreadsheet calculation, I broke out 10^12:

F = 18M*(((ln(S+L)+12*ln(10))/(ln(S)+12*ln(10)))^2-1)

The length, in T, that can be searched increases slightly as P's get bigger, but it's based on log2(P) minus a constant. For my 20T search, the value was 21. So based on this, here's an estimate of how many factors per day per core can be found at given sizes of P:

Size(T)	Bits	Len(T)	Factors/day
20	21	1	57395.73
40	22	1.05	29728.89
80	23	1.1	15294.32
160	24	1.14	7835.11
320	25	1.19	4002.7
640	26	1.24	2040.85
1280	27	1.29	1039.02
2560	28	1.33	528.35
5120	29	1.38	268.4

Looks like we should stop before about 5P.

[axn]

Originally Posted by Ken_g6

Looks like we should stop before about 5P.

Wow! That is certainly much higher than I had expected. What is the speed of the latest-and-greatest tpsieve on a single core of a Core 2 (scaled to a 2 GHz Core 2)? Last time I checked, I saw a speed of 1.7 M/sec. That equated to an optimal sieve depth of 300 T (-ish).

EDIT:- If 5P is the optimal depth, then sieving also should go BOINC?

[Ken_g6]

The sieve is much improved from when you last checked! At 20T, my Core 2 @2.66GHz does 23M/sec/core in 64-bit mode. In 32-bit mode with SSE2, it's about 19M. And that will slowly grow with P.

As for BOINC...each sieve instance takes about 1GB of RAM. If BOINC could run one sieve instance with as many threads as needed (which seems to work for me at least), it might be plausible; but 1GB is still a lot. On the other hand, the file could be broken up more, and it wouldn't cost too much in overhead - at least, not yet.