20090821, 17:12  #1 
Jul 2009
31 Posts 
Mersenne trial division candidate counts
Another thread mentioned the nice benchmark page listing hardware speeds for FFT and trial division. But I don't understand the "its" column for the trial division.
It seems like this is listing the number of division tests that are needed for a particular trial divisor range. So for the 2^64 row, the benchmark shows that 1,136,364 tests are needed, and this hardware takes 41.455 milliseconds per test, so the 2^64 range band will be tested in 47,108 seconds. Thie number of tests obviously depends on the Mersenne exponent you're choosing, and I assume the table is using a mersenne number of roughly 2^8,250,000 as seen in the first column. So my question is about the number of tests needed. I don't see where the 1,136,364 test count comes from. My estimate is as follows: We know test candidates are prime. We know they're in the form 1+ 2*P*k for integer k. We know they are 1 or 7 mod 8. So for the 2^64 range band there are 2^63 numbers. Roughly 1 in 44 of those numbers is prime. (ln(2^63)). The 1 or 7 mod 8 restriction lets us cut that down by 1/2. (Only 1/2 since the prime count already took care of 0 2 4 6 remainders). Finally, of those remaining, only 1 in 2*P will be tested because of the spacing of the candidates. So the rough number of tests for N=2^63 to 2^64, with P=8250000 would be 2^63 / 44 / 2 / (2*8250000) ~= 6 billion candidates. So why does this chart list a mere 1,136,364? The answer is probably I'm reading it wrong. 
20090821, 22:03  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
Yes, "its" means iterations.
IIRC the person who made that page reverseengineered the number of iterations for various bit levels by seeing the ms per test and total time for the range and working the (simple) math. I'm not sure of the reason for the large discrepancy between what you found (which seems quite logical to me) and what the page lists. Wild guess: maybe something with what Prime95 calls one iteration, e.g. it tests several factors in each 'iteration'. 
20090822, 07:12  #3 
Jul 2009
11111_{2} Posts 
Yes, it's pretty clear that "its" are more than one test. But it's unclear how many, or if it really has any meaning.
Prime95 doesn't give any stats about the number of values it's tested. I could hack some of the trial testers from here to report counts, but that may be more effort than it's worth. 
20090822, 08:24  #4 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
16BA_{16} Posts 
The trial division candidates are trial divided themselves.

20090822, 11:53  #5 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
4267_{10} Posts 

20090822, 14:36  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5818_{10} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sublinear complexity of trial division?  yih117  Math  5  20180202 02:49 
Mersenne trial division implementation  mathPuzzles  Math  8  20170421 07:21 
P95 trial division strategy  SPWorley  Math  8  20090824 23:26 
Trial division software for Mersenne  SPWorley  Factoring  7  20090816 00:23 
Need GMP trialdivision timings  ewmayer  Factoring  7  20081211 22:12 