mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-08-21, 17:12   #1
SPWorley
 
Jul 2009

31 Posts
Default 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.
SPWorley is offline   Reply With Quote
Old 2009-08-21, 22:03   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

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'.
Mini-Geek is offline   Reply With Quote
Old 2009-08-22, 07:12   #3
SPWorley
 
Jul 2009

111112 Posts
Default

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.
SPWorley is offline   Reply With Quote
Old 2009-08-22, 08:24   #4
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

16BA16 Posts
Default

The trial division candidates are trial divided themselves.
henryzz is offline   Reply With Quote
Old 2009-08-22, 11:53   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

Quote:
Originally Posted by henryzz View Post
The trial division candidates are trial divided themselves.
What do you mean? That 2kp+1 must be prime? Worley included that in his estimate.
Mini-Geek is offline   Reply With Quote
Old 2009-08-22, 14:36   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

581810 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
What do you mean? That 2kp+1 must be prime? Worley included that in his estimate.
Yes, the 2kp+1 must be prime to be a possible factor(unless you have already missed factors).
Ok.
henryzz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sublinear complexity of trial division? yih117 Math 5 2018-02-02 02:49
Mersenne trial division implementation mathPuzzles Math 8 2017-04-21 07:21
P95 trial division strategy SPWorley Math 8 2009-08-24 23:26
Trial division software for Mersenne SPWorley Factoring 7 2009-08-16 00:23
Need GMP trial-division timings ewmayer Factoring 7 2008-12-11 22:12

All times are UTC. The time now is 03:03.

Thu Feb 25 03:03:42 UTC 2021 up 83 days, 23:15, 0 users, load averages: 1.66, 2.16, 2.29

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.