Experimental n=1.7M sieving

[Bottom Quark]

Not sure if this deserves its own thread, but there's a new experimental quad sieving program at https://github.com/galloty/qsieve that may or may not be faster than NewPGen and TwinGenX. The idea is that you'd sieve a range of n and k, make it small enough to fit in a GPU (16 GB of RAM?) and move on to another range until a twin and SG are found. For bitmap size optimization purposes, each range of n is 64 wide (n_max = n_min+63)

We could first start out with testing n=1700001-1700064 for k<70G, which should be good for most GPUs. Although the GPU version hasn't been finalized yet, a speedup of ~100x over the CPU version is expected based on what we've seen for similar k*2^n-1 sieves.

I'm on my phone and currently don't have access to a computer, but could someone run some benchmarks with it on a CPU and confirm that the results match NewPGen/TwinGenX? If the speed is fast enough, it may be a good idea to move from n=1700000 to n=1700001-17xxxxx once the current p=1047T sieve limit is exceeded.

[The Carnivore]

If the program does turn out to be fast and reliable, should we just re-think the whole n=1.7M project and just do something like n=1.3M - 2.0M for k<2G?

[rogue]

Why choose that value for n?

[Bottom Quark]

Originally Posted by The Carnivore

If the program does turn out to be fast and reliable, should we just re-think the whole n=1.7M project and just do something like n=1.3M - 2.0M for k<2G?

The drawback is that doing work just over a FFT threshold is not efficient. n=1708500 and n=1709000 take almost the same amount of time to test, but n=1709500 takes significantly longer than either of them.

[Bottom Quark]

Originally Posted by rogue

Why choose that value for n?

I think n=1.7M was chosen because it was just below the n=1.709M threshold, was a nice round number (both the 1,700,000 value and the >500,000 decimal digits length), and was a reasonable increase from the n=1.29M tests.

Are there better alternatives that you'd suggest?

[The Carnivore]

Originally Posted by Bottom Quark

Are there better alternatives that you'd suggest?

The question wasn't directed at me, but what about testing exponents that use a power-of-2 FFT length? Those are more efficient:
https://www.mersenneforum.org/showpo...37&postcount=8

n=1700000 uses an FFT length of 168K. Perhaps testing one or more exponents with an FFT length of 128K or 256K would be better?

[MooMoo2]

Originally Posted by The Carnivore

The question wasn't directed at me, but what about testing exponents that use a power-of-2 FFT length? Those are more efficient:
https://www.mersenneforum.org/showpo...37&postcount=8

n=1700000 uses an FFT length of 168K. Perhaps testing one or more exponents with an FFT length of 128K or 256K would be better?

I've run some timings and got the following:

Exponent	FFT Length	Testing Time
1290000		128K		0.374 ms/iteration
1311000		128K		0.374 ms/iteration
1312000		140K		0.439 ms/iteration
1430000		140K		0.439 ms/iteration
1431000		144K		0.464 ms/iteration
1470000		144K		0.465 ms/iteration
1471000		160K		0.474 ms/iteration
1631000		160K		0.475 ms/iteration
1632000		168K		0.559 ms/iteration
1700000		168K		0.557 ms/iteration
1709000		168K		0.555 ms/iteration
1710000		192K		0.572 ms/iteration
1951000		192K		0.572 ms/iteration
1952000		200K		0.654 ms/iteration
2029000		200K		0.654 ms/iteration
2030000		224K		0.688 ms/iteration
2270000		224K		0.688 ms/iteration
2271000		240K		0.737 ms/iteration
2425000		240K		0.734 ms/iteration
2426000		256K		0.777 ms/iteration
2586000		256K		0.775 ms/iteration
2587000		288K		0.912 ms/iteration
2898000		288K		0.914 ms/iteration

An excel graph is also attached. The x-axis is the exponent size, while the y-axis is the time (in milliseconds) it took to test one iteration. The further an exponent is below the red line, the more efficient it is. Two promising areas, where the blue line is furthest below the red line, are n=1950000 and n=2580000. Those exponents have FFT lengths of 192K (1.5*2^7) and 256K (2^8). n=1950000 is 10 times the original TPS value of n=195000, and n=2580000 is twice the size of PrimeGrid's n=1.29M search.

For bitmap size optimization purposes, each range of n is 64 wide (n_max = n_min+63)

We could first start out with testing n=1700001-1700064 for k<70G, which should be good for most GPUs.

Despite trying out several different compilers, I've so far been unable to compile the qsieve code at: https://github.com/galloty/qsieve/bl...src/qsieve.cpp . Various errors keep popping up. If anyone can get it to run properly, I'd definitely be interested in seeing some benchmarks.

[The Carnivore]

Originally Posted by MooMoo2

I've run some timings and got the following:

Exponent	FFT Length	Testing Time
1290000		128K		0.374 ms/iteration
1311000		128K		0.374 ms/iteration
1312000		140K		0.439 ms/iteration
1430000		140K		0.439 ms/iteration
1431000		144K		0.464 ms/iteration
1470000		144K		0.465 ms/iteration
1471000		160K		0.474 ms/iteration
1631000		160K		0.475 ms/iteration
1632000		168K		0.559 ms/iteration
1700000		168K		0.557 ms/iteration
1709000		168K		0.555 ms/iteration
1710000		192K		0.572 ms/iteration
1951000		192K		0.572 ms/iteration
1952000		200K		0.654 ms/iteration
2029000		200K		0.654 ms/iteration
2030000		224K		0.688 ms/iteration
2270000		224K		0.688 ms/iteration
2271000		240K		0.737 ms/iteration
2425000		240K		0.734 ms/iteration
2426000		256K		0.777 ms/iteration
2586000		256K		0.775 ms/iteration
2587000		288K		0.912 ms/iteration
2898000		288K		0.914 ms/iteration

An excel graph is also attached. The x-axis is the exponent size, while the y-axis is the time (in milliseconds) it took to test one iteration. The further an exponent is below the red line, the more efficient it is. Two promising areas, where the blue line is furthest below the red line, are n=1950000 and n=2580000. Those exponents have FFT lengths of 192K (1.5*2^7) and 256K (2^8).

So are we switching to n=1950000 and n=2580000 then? They're both big enough for the top 5000 list.

[storm5510]

Originally Posted by rogue

Why choose that value for n?

Good question. 1.7-million is in the ECM area.

[Happy5214]

Originally Posted by MooMoo2

Despite trying out several different compilers, I've so far been unable to compile the qsieve code at: https://github.com/galloty/qsieve/bl...src/qsieve.cpp . Various errors keep popping up. If anyone can get it to run properly, I'd definitely be interested in seeing some benchmarks.

I got the program to compile with GCC 11 on Linux. I had to edit the code to change the starting n, as there was no parameter. At this time, it is not suitable for production use. I directed it to sieve n=[1700001, 1700064], k_max = 6e9 (1/100 of what Yves suggested in https://www.primegrid.com/forum_thre...ap=true#165303), to p_max = 1e10. It said it would only sieve to 2^20 when the program started, and after about 14 minutes, it only ended up sieving to p_max = 8100. It claimed to have "23950114 candidates" remaining, and I decided to kill the program rather than fill up my SSD with a huge temporary file. We can shelve this idea until Yves finishes a production-ready GPU version.

[VBCurtis]

Originally Posted by storm5510

Good question. 1.7-million is in the ECM area.

Huh? ECM area for what? Are you talking about some project totally unrelated to this one, like GIMPS?