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

2018-02-15, 16:15   #23
Mark Rose

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

53428 Posts

Quote:
 Originally Posted by VictordeHolland 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?
There's nothing wrong with PHP, but it's a very incoherent language. I've been using it professionally for nine years, and a lot longer before that. It's the Visual Basic of the modern era.

 2018-02-15, 18:47 #24 CRGreathouse     Aug 2006 133448 Posts
2018-02-15, 21:52   #25
VictordeHolland

"Victor de Hollander"
Aug 2011
the Netherlands

22308 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.
Quote:
 Originally Posted by alpertron the computer found factors of M2301251 and M2301421.
These 6 had known factors before. I THINK the formula is for finding a first factor (GIMPS doesn't really care if a exponent has 1 or multiple factors, it just knows it doesn't need to run the 'expensive' LL test.) Also it assumes it has had decent trial factoring before, which rarely happens with exponents with known factors. Could the discrepancy come from this? (apart from the small sample size).

I can understand why people are reluctant to spend 0.12 GHzday to try P-1 if a PRP test on these low exponents only takes 0.15 GHzday

 2018-02-15, 23:39 #26 alpertron     Aug 2002 Buenos Aires, Argentina 2·659 Posts GIMPS does care about all prime factors of Mersenne numbers. That's why it stores all prime factors found (not only the first one) and on GIMPS you can select to perform ECM on numbers that have at least one factor known, and you can also perform PRP on cofactors. Notice that with the ECM worktype (3 curves with B1=50000, B2=5M), my computer found factors for the following Mersenne numbers: M2302451, M2314951, M2333651, M2339797, M2357791, M2364161, M2365313 and M2379851 (14 days, two threads) while using P-1 (B1=500000, B2=15M) my computer found factors for the following Mersenne numbers: M2300017, M2300057, M2300153, M2300563, M2300731, M2300999, M2301199, M2301251 and M2301421 (1 day, 1 thread). In both cases these numbers already had factors found. It is clear the P-1 in this range can find a lot more factors than ECM. From TJAOI's work, the prime factors to be found will be greater than 34*1018 (about 65 bits). Last fiddled with by alpertron on 2018-02-15 at 23:43
2018-02-16, 03:17   #27
axn

Jun 2003

10001111100012 Posts

Quote:
 Originally Posted by VictordeHolland These 6 had known factors before. I THINK the formula is for finding a first factor
No. The formula is for finding a "smooth" factor above the TF limit. It isn't affected by the existence of smaller factors.

However, ...

Now that I think about it, it might be underestimating the probability.

Basically, the formula looks at the probability of k part of P=2kp+1 being B1/B2 smooth. It assumes that k is a random number.

However k is not a random number. It is a factor of a (prime - 1). This ought to have different probabilities of divisibility by other primes. (For example, if k is truly random, it will be divisible by 3 with probability 1/3. However, since 3 cannot divide P, it will divide P-1 with probability 1/2, hence it will divide k with probability 1/2).

This might mean that the formula needs to be tweaked by a correction factor. It might not matter much in the end though -- the formula as such is a crude approximation.

Anybody willing to work on a more sophisticated estimate?

2018-02-16, 16:35   #28
chris2be8

Sep 2009

13·139 Posts

Quote:
 Originally Posted by Mark Rose The Black Speech of Mordor.
Or the modern equivalent from intercal.txt.gz:
Code:
//INTERCAL PROC
//COMPILE EXEC PGM=INTERCAL
//STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR
//             DD DSN=SYS1.FORTLIB,DISP=SHR
//SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA)
//SYSPUNCH DD DUMMY
//SCRATCH DD DSN=&COMPSET,UNIT=SYSDA,SPACE=(CYL,(3,1)),DISP=(,PASS)
//EXECUTE EXEC PGM=EXECUTE,COND=(4,LT)
//SOURCES DD DSN=U.INTERCAL.SOURCES,DISP=SHR
//STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR
//             DD DSN=SYS5.SPITLIB,DISP=SHR
//             DD DSN=SYS1.FORTLIB,DISP=SHR
//SYSIN DD DSN=&COMPSET,DISP=(OLD,DELETE)
//SYSOBJ DD SYSOUT=B,DCB=(BLKSIZE=80,LRECL=80,RECFM=F)
//SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA)
//SYSPUNCH DD DUMMY
// PEND
Chris

2018-02-16, 20:28   #29
ET_
Banned

"Luigi"
Aug 2002
Team Italia

72×97 Posts

Quote:
 Originally Posted by chris2be8 Or the modern equivalent from intercal.txt.gz: Code: //INTERCAL PROC //COMPILE EXEC PGM=INTERCAL //STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR // DD DSN=SYS1.FORTLIB,DISP=SHR //SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA) //SYSPUNCH DD DUMMY //SCRATCH DD DSN=&COMPSET,UNIT=SYSDA,SPACE=(CYL,(3,1)),DISP=(,PASS) //EXECUTE EXEC PGM=EXECUTE,COND=(4,LT) //SOURCES DD DSN=U.INTERCAL.SOURCES,DISP=SHR //STEPLIB DD DSN=U.INTERCAL.LIBRARY,DISP=SHR // DD DSN=SYS5.SPITLIB,DISP=SHR // DD DSN=SYS1.FORTLIB,DISP=SHR //SYSIN DD DSN=&COMPSET,DISP=(OLD,DELETE) //SYSOBJ DD SYSOUT=B,DCB=(BLKSIZE=80,LRECL=80,RECFM=F) //SYSPRINT DD SYSOUT=A,DCB=(BLKSIZE=992,LRECL=137,RECFM=VBA) //SYSPUNCH DD DUMMY // PEND Chris
That's JCL...

2018-02-17, 04:43   #30
LaurV
Romulan Interpreter

Jun 2011
Thailand

8,543 Posts

Quote:
 Originally Posted by axn Anybody willing to work on a more sophisticated estimate?
I always use to multiply that by 2, which somehow matched with my results (number of factors) in the past when I had like 20 GPUs doing TF assignments from Chris' site. You may remember that I was always finding more factors than expected, and I used to joke that I am a lucky guy (which I still do sometimes). But a real reason may be that we need to multiply everything by 2 or so, including for P-1. I can not offer a more "mathematical" explanation for it, but a reason may be the fact that indeed, k in q=2kp+1 is not a random number, but it can only be "0 or 1 (mod 4)" if p=3 (mod 4), or it can be "0 or 3 (mod 4)" if p=1 (mod 4). So, it is somehow "half" of the four possible cases in each category.

For the case in this thread, the sample is too small. I also remember having long strikes of bad luck, where I could not uncover a P-1 factor for weeks, and then finding lots of factors in the same day (or week).

2018-02-17, 17:35   #31
chris2be8

Sep 2009

13·139 Posts

Quote:
 Originally Posted by ET_ That's JCL...
I know what it is. But it's the best candidate for The Black Speech of Mordor I've seen.

My happiest memory of it was the expression on my sister's face after I explained the COND statement to her...

Chris

2018-02-20, 23:27   #32
wblipp

"William"
May 2003
New Haven

44668 Posts

Has anybody checked if the heuristic for B1/B2 smooth is near the real value? The comments in the code sample indicate that the code generates a smashup estimate calculated from the function for being b-smooth at multiple values of b. But there is a known formula for being B1/B2 smooth. It may be more complex than we want to calculate on the fly, but a handful of test cases could be calculated.

Quote:
 Originally Posted by VictordeHolland The calculator uses more or less the same code as Prime95: Code: /* 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 */
The exact B1/B2 formula has been discussed a few time. I had a pissing contest with RDS about it in 2004 because it is wrong in his famous Wagstaff paper. We finally agreed my guess was correct when we discovered Richard Brent saying the same thing in 1985 - see equation 3.3 in the full pdf.

I don't currently have access to good tools to do the numerical integration - perhaps someone else can check a few cases?

 2018-02-21, 14:09 #33 CRGreathouse     Aug 2006 16E416 Posts I don't think Dickman's rho is particularly accurate in that range -- I wonder if we'd be better off checking numbers for smoothness directly.

 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 18:40.

Tue Jun 2 18:40:27 UTC 2020 up 69 days, 16:13, 3 users, load averages: 1.62, 1.74, 1.70