20110528, 01:15  #1 
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
A real GIMPS math thought
(That was a hint about the location of this subforum).
Suppose we have one reliable CPU which TFs then LLs, no DCs. The universally(?) accepted wisdom (see "The Math" page") is that having TFed to bit level X, one should TF to bit level X+1 unless the time to TF from X to (X+!) > T/X where T is the time of the LL test (1/X being the probability of a factor between 2^X and 2^(X+1)). Thus (1+1/X)T < total time per exponent < (1 + 2/X)T (extra bit takes twice as long). BUT: By TFing to X+1 instead of X, the probability of the exponent being prime is enhanced by (X+1)/X. This compensates for the extra time (T/X) spent. Am I right? David No :)) The extra time is 2T/X Silly me! I know that "bit level" is the natural way of organizing a TF program (not to mention one's thinking) but if we were to consider each potential factor and ask "What is the optimum cutoff point", would not my thought about probability of being prime shift the answer slightly? Last fiddled with by davieddy on 20110528 at 02:08 
20110528, 01:46  #2 
Dec 2010
Monticello
703_{16} Posts 
Uhhh...the chances of an exponent being prime are, well, miniscule...about 1 in 500,000, more or less...and they don't depend on how much TF or P1 or LL testing or anything else is done to them. [Well, there's some evidence that some people have an idea that the exponents of Mersenne primes have certain properties with higher than normal frequencies, and test those exponents first, but once the exponent is chosen, it's primality doesn't depend on the testing for primality that is done]
What does change, for the overwhelming majority of exponents, is the effort to prove that they are not in fact primes. The question is how to allocate the effort such that the maximum number of exponents get proven to be indeed composite for a fixed amount of effort. For example, if I test a group of 100 exponents with P1, and find 10 of them composite (because we have a factor) at a cost of 600GHz days, then there are 20 LL tests (first and doublechecks) that no longer have to be carried out. If one LL test costs 60 GHz days, so 20 would cost 1200GHz days, the 600GHz days of P1 have saved 600GHz days of total effort. Same with TF: If, on average, finding a factor costs less(takes fewer GHz days) than the LL testing, then TF'ing to that level reduces the total cost. Note that I'm ignoring that specialist hardware (GPUs) significantly ease trial factoring, so they can accomplish lots and lots more TF than CPUs can...meaning that GHz day isn't exactly the correct unit of measure for the cost of the computation. 
20110528, 02:24  #3  
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Quote:
For a 50M exponent, the chance would be ~1/2,000,000 with no TF or P1. If a reliable LL test had been done, the probability would be 0 or 1. Mr Silverman enjoys this nicety. David PS to be pedantic, the chance of GIMPS testing 2^exponent  1 is 0 unless the exponent is prime:) Last fiddled with by davieddy on 20110528 at 02:52 

20110528, 08:10  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
So, TFing to X+1 instead of X affects the probability of finding a factor in the range 1X (and the probability of finding a factor in range X+1 to exponent/2), but that's not simply inversely proportional to the probability that the Mersenne number is prime, because of the possible existence of multiple factors. Last fiddled with by cheesehead on 20110528 at 08:11 

20110528, 09:06  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,949 Posts 
Quote:
Why should 100 ALUs clocked at 1GHz not be awarded 100 GHz days just because all 100 are located in a single chip, when you seem to be OK with 4 ALUs, also on a single chip, clocked at 2.5GHz being awarded 10 GHz days? Ok, the numbers are only illustrative and the GPUs are underrewarded by this simple metric but the question is a serious one. Paul 

20110528, 10:37  #6  
"Lucan"
Dec 2006
England
194A_{16} Posts 
Quote:
The probability of no factor between 2^X and 2^(X+1) is 1  1/X =(X1)/X. So the probability of no factor up to exponent/2 is the product (X1)/X * X/(X+1) *.....* (exponent/2  1)/(exponent/2) = (X1)/(exponent/2). Now replace 1/2 with Euler's gamma (because it tastes better), and you have the formula which is generally used, and gives results consistent with Wagstaff's conjecture. Another way of looking at it is that it seems ~5/8 of candidates get factored, but finding which ones does not alter the expected primes in a given range. Why? Because the probability of the remaining candidates being prime is enhanced by 8/3. The same presumably applies to P1 or ECM or whatever. David Last fiddled with by davieddy on 20110528 at 11:00 

20110528, 12:31  #7 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Physics instinct kicks in
Take the curve y = 10 + (x  4)^2.
You want to know the minimum value of y. Evaluate it anywhere near x=4 and you won't be far out. You want to know "at what precise x does the min y occur?" Be bloody careful about what y you choose David Or more practically: "Suck it and see", as an elderly female lab assistant used to advise me whenever I asked her a physics question! i.e. try a few values of x near 4, and note the smallest y. Last fiddled with by davieddy on 20110528 at 13:07 
20110528, 12:54  #8  
Dec 2010
Monticello
5·359 Posts 
Quote:
You can measure everything in GHzDays if you want, but if I understand it correctly, my midrange GPU earns perhaps 50GHzDays per calendar day of TF, perhaps 10GHz days per day of LL. My CPU core earns perhaps 3 GHzDays per day of either LL or TF. GHzDays thus measure progress on the computation, not the effort that goes in...and I claim that it is effective effort we want to minimize for the maximum amount of progress. 

20110528, 14:08  #9  
"Lucan"
Dec 2006
England
2·3·13·83 Posts 
Quote:
Quote:
I started this thread stating one CPU (P4/computer/core/ALU or whatever) with the sole intention of avoiding this digression discussed in many other threads. Richard has at least partly responded to my point. Further debate along the line of thought thereby defined(?) is more than welcome. David. 

20110528, 15:01  #10 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
OTOH think of the normal distribution and/or Dirac's delta function.
I love statistical mechanics, but it is an acquired taste! Maxwell's Demon Last fiddled with by davieddy on 20110528 at 15:02 
20110529, 05:27  #11  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime number thought experiment  MooMoo2  Lounge  59  20180102 18:37 
Just a thought of Quark numbers.  SarK0Y  Miscellaneous Math  44  20111107 18:01 
I thought I found another one.....  schickel  Aliquot Sequences  0  20110221 03:52 
Real Math Forum  BMgf  Homework Help  6  20031209 17:13 
GIMPS get's mentioned at High School math banquet  Kevin  Lounge  1  20030310 14:01 