mersenneforum.org Experimental n=1.7M sieving
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2023-09-18, 19:42 #1 Bottom Quark   Dec 2010 548 Posts Experimental n=1.7M sieving 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.
 2023-09-18, 20:28 #2 The Carnivore     Jun 2010 24×17 Posts 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?
 2023-09-18, 20:54 #3 rogue     "Mark" Apr 2003 Between here and the 24·467 Posts Why choose that value for n?
2023-09-18, 20:55   #4
Bottom Quark

Dec 2010

2C16 Posts

Quote:
 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.

2023-09-18, 20:59   #5
Bottom Quark

Dec 2010

22·11 Posts

Quote:
 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?

2023-09-19, 01:31   #6
The Carnivore

Jun 2010

1000100002 Posts

Quote:
 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?

2023-09-19, 05:46   #7
MooMoo2

"Michael Kwok"
Mar 2006

121310 Posts

Quote:
 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:

Code:
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.

Quote:
 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.
Attached Thumbnails

2023-09-19, 15:18   #8
The Carnivore

Jun 2010

24·17 Posts

Quote:
 Originally Posted by MooMoo2 I've run some timings and got the following: Code: 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.

2023-09-19, 16:23   #9
storm5510
Random Account

Aug 2009
Oceanus Procellarum

23·13·29 Posts

Quote:
 Originally Posted by rogue Why choose that value for n?
Good question. 1.7-million is in the ECM area.

2023-09-19, 17:27   #10
Happy5214

"Alexander"
Nov 2008
The Alamo City

32×113 Posts

Quote:
 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.

2023-09-19, 20:10   #11
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

53·113 Posts

Quote:
 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?

 Similar Threads Thread Thread Starter Forum Replies Last Post SELROC GPU Computing 26 2019-07-27 05:40 wombatman YAFU 22 2016-02-19 18:59 Dan Ee Factoring 40 2016-02-08 20:32 ixfd64 Lounge 14 2007-12-17 01:22 davieddy Science & Technology 17 2007-08-14 21:29

All times are UTC. The time now is 11:31.

Sun Sep 24 11:31:26 UTC 2023 up 11 days, 9:13, 0 users, load averages: 0.79, 0.86, 0.89

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔