Mersenne trial division candidate counts
 

Another thread [URL="http://mersenne-aries.sili.net/throughput.php?cpu=Intel%28R%29+Atom%28TM%29+CPU+330+%40+1.60GHz%7C512%7C0&mhz=1600"]mentioned the nice benchmark page[/URL] 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.

Yes, "its" means iterations.
IIRC the person who made that page reverse-engineered 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'.

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[URL="http://www.mersenne.org/various/freeware.htm"] hack some of the trial testers from here[/URL] to report counts, but that may be more effort than it's worth.

The trial division candidates are trial divided themselves.

[quote=henryzz;186992]The trial division candidates are trial divided themselves.[/quote]
What do you mean? That 2kp+1 must be prime? Worley included that in his estimate.

[quote=Mini-Geek;187007]What do you mean? That 2kp+1 must be prime? Worley included that in his estimate.[/quote]
Yes, the 2kp+1 must be prime to be a possible factor(unless you have already missed factors).
Ok.