mersenneforum.org Run P-1 before PRP tests
 Register FAQ Search Today's Posts Mark Forums Read

2017-11-24, 22:45   #12
VictordeHolland

"Victor de Hollander"
Aug 2011
the Netherlands

49816 Posts

Quote:
 Originally Posted by petrw1 When I try the "show source" link I get: Code: Fatal error: Call to undefined function htmlentities_safe() in /var/www/vhosts/mersenne.ca/httpdocs/prob.php on line 15
The calculator uses more or less the same code as Prime95:
Code:
function FactorProbability($exponent,$B1, $B2,$HowFarFactoredBits=false) {
// adapted from guess_pminus1_bounds() in ecm.c in Prime95 source

if ($B1 < 30) { return 0; }$B2 = max($B2,$B1);
if (!$HowFarFactoredBits) { //$HowFarFactoredBits = FactorBits($exponent);$HowFarFactoredBits = FactorBits($exponent) - 1; // last level of TF is now done *after* P-1 by default }$ProbabilityThreshold = 0.0001;

$log2 = log(2);$logB1 = log($B1);$logB2 = log($B2);$k =  1; /* K in K*B^N+C. Must be a positive integer. */
$b = 2; /* B in K*B^N+C. Must be two. */$c = -1; /* C in K*B^N+C. */

$kk = 1.5 * pow(2.0,$HowFarFactoredBits);
if (($k == 1.0) && ($b == 2) && ($c == -1)) {$kk = $kk / 2.0 /$exponent;
}
$LogKK = log($kk);

$temp =$kk / (($B1 +$B2) / 2);
$LogTemp = log($temp);

$FactorProbability = 0;$H = $HowFarFactoredBits; while (true) { /* If$temp < 1.0, then there are no factor to find in this bit level */
if ($LogTemp > 0) { /* See how many smooth k's we should find using B1 */ /* Using Dickman's function (see Knuth pg 382-383) we want k^a <= B1 */$Prob1 = DickmansFunction($logB1 /$LogKK);

/* See how many smooth k's we should find using B2 */
/* Adjust this slightly to eliminate k's that have two primes > B1 and < B2 */
/* Do this by assuming the largest factor is the average of B1 and B2 */
/* and the remaining cofactor is B1 smooth */
$Prob2 =$Prob1 + ((DickmansFunction($logB2 /$LogKK) -  $Prob1) * (DickmansFunction($logB1 / $LogTemp) / DickmansFunction($logB2  / $LogTemp))); if ($Prob2 < $ProbabilityThreshold) { break; } /* Add this data in to the total chance of finding a factor */$FactorProbability += $Prob2 / ($H + 0.5);
}
$H++;$LogKK   += $log2;$LogTemp += $log2; } return$FactorProbability;
}

2017-11-24, 22:55   #13
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts

Quote:
 Originally Posted by VictordeHolland The calculator uses more or less the same code as Prime95:
What language is that?

2017-11-24, 23:31   #14
ATH
Einyen

Dec 2003
Denmark

2,837 Posts

Quote:
 Originally Posted by GP2 I did this with UsePrimenet=0 and submitted the results manually. You get no Primenet credit (unless you found a factor), but it does add a line to the History section.
It claimed that I got credit when I submitted the P-1 line even with no factor. I did not check if my P-1 credit was raised by that amount, but I will check next time.

2017-11-25, 00:13   #15
Mark Rose

"/X\(‘-‘)/X\"
Jan 2013
Ͳօɾօղէօ

2×7×199 Posts

Quote:
 Originally Posted by Dubslow What language is that?
The Black Speech of Mordor.

2017-11-25, 15:30   #16
VictordeHolland

"Victor de Hollander"
Aug 2011
the Netherlands

23·3·72 Posts

Quote:
 Originally Posted by Mark Rose The Black Speech of Mordor.
James's site is mainly serving pages created from a database, so PHP makes a lot of sense. What is wrong with using PHP for this case?

Code:
// adapted from guess_pminus1_bounds() in ecm.c in Prime95 source
This is from ecm.c that it is referring to:
Code:
/* Determine the probability of P-1 finding a factor */
/* This code was pulled from guess_pminus1_bounds */

double guess_pminus1_probability (
struct work_unit *w)
{
double    log2, logB1, logB2, h, kk, logkk, temp, logtemp, prob;

/* Constants */

log2 = log ((double) 2.0);
logB1 = log (w->B1);
logB2 = log (w->B2);

/* What is the "average" value that must be smooth for P-1 to succeed? */
/* Ordinarily this is 1.5 * 2^how_far_factored.  However, for Mersenne */
/* numbers the factor must be of the form 2kp+1.  Consequently, the */
/* value that must be smooth (k) is much smaller. */

kk = 1.5 * pow (2.0, w->sieve_depth);
if (w->k == 1.0 && w->b == 2 && w->c == -1) kk = kk / 2.0 / w->n;
logkk = log (kk);

/* Set temp to the number that will need B1 smooth if k has an */
/* average-sized factor found in stage 2 */

temp = kk / ((w->B1 + w->B2) / 2);
logtemp = log (temp);

/* Loop over increasing bit lengths for the factor */

prob = 0.0;
for (h = w->sieve_depth; ; ) {
double    prob1, prob2;

/* If kk < 1.0, then there are no factors to find in this bit level */

if (logkk > 0.0) {

/* See how many smooth k's we should find using B1 */
/* Using Dickman's function (see Knuth pg 382-383) we want k^a <= B1 */

prob1 = F (logB1 / logkk);

/* See how many smooth k's we should find using B2 (if temp < 1.0 then we should find them all) */
/* Adjust this slightly to eliminate k's that have two primes > B1 and < B2 */
/* Do this by assuming the largest factor is the average of B1 and B2 */
/* and the remaining cofactor is B1 smooth */

if (logtemp <= 0.0) prob2 = 1.0;
else prob2 = prob1 + (F (logB2 / logkk) - prob1) *
(F (logB1 / logtemp) / F (logB2 / logtemp));
if (prob2 < 0.0001) break;

/* Add this data in to the total chance of finding a factor */

prob += (1.0 - prob) * prob2 / (h + 0.5);
}

/* Move to next bit level */

h += 1.0;
logkk += log2;
logtemp += log2;
}

/* Return the final probability */

return (prob);
}

2018-02-14, 18:37   #17
alpertron

Aug 2002
Buenos Aires, Argentina

2×659 Posts

Quote:
 Originally Posted by petrw1 I accept the fact that you know WAYYY more about P-1 than I do so feel free to elaborate on the following as you see fit. What I have done is created a table with various B1/B2 bounds (yours is first) for P-1 in the range you suggest. This specific table uses Exponent 2,600,001. I'll explain the columns: B1/B2: various choices for B1 and B2 bound for the new P-1 Pct: The odds of it finding a factor strictly based on this: http://www.mersenne.ca/prob.php GD: The GhzDays to do the P-1 based on the same URL above. -- Then 4 pairs of columns as follows (Most Exponents in the 2.6M range have existing P-1 runs with an estimated success rate of about 3.25% - 4%): 3.25: The number at the top of the pair of columns is the odds of the existing P-1 run finding a factor. PerFac: The calculated number of P-1 with the new bounds required to find a factor taking into account the odds from the prior P-1 run GD/F: The calculated GhzDays required to find a new factor based on the above parms. I suggest we want to minimize this number. For example: From the first row: Statistically, 68.97 P-1 runs would be required to find a factor based on the net Percent of 4.70 - 3.25 (New - Existing P-1). Then based on 0.13 GhzDays per new P-1 it would take 8.97 total GhzDays of P-1 work to find the new factor. NOTE: What this table does NOT take into account is the ECM work already done on these Exponents. More than I could bite off. Code:  3.25 3.50 3.75 4.00 B1 B2 Pct GD PerFac GD/F PerFac GD/F PerFac GD/F PerFac GD/F 500000 15000000 4.70 0.13 68.97 8.97 83.33 10.83 105.26 13.68 142.86 18.57 1000000 20000000 5.45 0.21 45.45 9.32 51.28 10.51 58.82 12.06 68.97 14.14 2000000 40000000 6.62 0.42 29.67 12.46 32.05 13.46 34.84 14.63 38.17 16.03 2600000 52000000 7.08 0.53 26.11 13.84 27.93 14.80 30.03 15.92 32.47 17.21 2600000 26000000 6.32 0.39 32.57 12.70 35.46 13.83 38.91 15.18 43.10 16.81 3000000 60000000 7.34 0.61 24.45 15.01 26.04 15.99 27.86 17.10 29.94 18.38 4000000 80000000 7.86 0.82 21.69 17.77 22.94 18.78 24.33 19.93 25.91 21.22 5200000 104000000 8.33 1.06 19.69 20.87 20.70 21.95 21.83 23.14 23.09 24.48
I reserved all exponents with known factors from 2300000 to 2310000 for ECM, but I changed them in my computer to perform P-1 with bounds B1=500000, B2=15M instead.

Up to this moment, Prime95 ran up to 2300300 (13 numbers) and it found three new factors, for exponents 2300017, 2300057 and 2300153. If it is true that I can find factors only 1 of every 68 numbers, that means that I'm very lucky.

 2018-02-14, 19:25 #18 VictordeHolland     "Victor de Hollander" Aug 2011 the Netherlands 23×3×72 Posts If anybody wants my P95 P-1 savefiles (B=10e6, B2=200e6) from exponents in the range 1.5M-1.7M (on 2500+ exponents without factors) to extend them for instance, let me know. Note that the exponents in question also have had 280 ECM curves @B1=50,000 done since the P-1 runs. Somebody better educated in the subject can probably calculate if it still is useful to run more P-1 or just ECM.
2018-02-15, 00:17   #19

"Kieren"
Jul 2011
In My Own Galaxy!

59·167 Posts

Quote:
 Originally Posted by Mark Rose The Black Speech of Mordor.
The Black Speech of Mordor:
Quote:
 Ash nazg durbatulûk, ash nazg gimbatul, Ash nazg thrakatulûk agh burzum-ishi krimpatul. Translated, the words mean: One ring to rule them all, one ring to find them, One ring to bring them all and in the darkness bind them. When Gandalf recited the inscription in Black Speech at the Council of Elrond, everyone trembled: The change in the wizard's voice was astounding. Suddenly it became menacing, powerful, harsh as stone. A shadow seemed to pass over the high sun, and the porch for a moment grew dark. All trembled, and the Elves stopped their ears.

2018-02-15, 12:00   #20
alpertron

Aug 2002
Buenos Aires, Argentina

2·659 Posts

Quote:
 Originally Posted by alpertron I reserved all exponents with known factors from 2300000 to 2310000 for ECM, but I changed them in my computer to perform P-1 with bounds B1=500000, B2=15M instead. Up to this moment, Prime95 ran up to 2300300 (13 numbers) and it found three new factors, for exponents 2300017, 2300057 and 2300153. If it is true that I can find factors only 1 of every 68 numbers, that means that I'm very lucky.
The computer processed 42 numbers and it found more factors for Mersenne numbers with exponents 2300563, 2300731, 2300999 and 2301199. It is clear that something in the formulas related to the probability of finding factors using P-1 algorithm is wrong.

2018-02-15, 13:24   #21
axn

Jun 2003

3×1,531 Posts

Quote:
 Originally Posted by alpertron The computer processed 42 numbers and it found more factors for Mersenne numbers with exponents 2300563, 2300731, 2300999 and 2301199. It is clear that something in the formulas related to the probability of finding factors using P-1 algorithm is wrong.
http://www.mersenne.ca/prob.php?expo...tton=Calculate says 5.68%. For 42 tests, that amounts to 2.5 factors. You found 7. Sure that's a lot more, but not impossibly so. The problem is low sample size. Maybe once you've run it for about 1000 exponents, we can have some degree of confidence on the numbers.

2018-02-15, 13:47   #22
alpertron

Aug 2002
Buenos Aires, Argentina

2×659 Posts

Quote:
 Originally Posted by axn http://www.mersenne.ca/prob.php?expo...tton=Calculate says 5.68%. For 42 tests, that amounts to 2.5 factors. You found 7. Sure that's a lot more, but not impossibly so. The problem is low sample size. Maybe once you've run it for about 1000 exponents, we can have some degree of confidence on the numbers.
Continuing with the "stroke of luck", after 6 more numbers, the computer found factors of M2301251 and M2301421.

 Similar Threads Thread Thread Starter Forum Replies Last Post joblack Hardware 12 2009-08-26 20:40 dave_0273 Marin's Mersenne-aries 1 2006-03-23 00:03 Holmes Math 1 2005-05-13 17:18 GP2 Completed Missions 5 2003-09-30 22:10 outlnder Lounge 8 2002-10-21 00:12

All times are UTC. The time now is 00:58.

Sat Jun 6 00:58:53 UTC 2020 up 72 days, 22:31, 0 users, load averages: 1.10, 1.27, 1.30