mersenneforum.org  

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

Reply
 
Thread Tools
Old 2018-02-15, 16:15   #23
Mark Rose
 
Mark Rose's Avatar
 
"/X\(‘-‘)/X\"
Jan 2013
Ͳօɾօղէօ

53428 Posts
Default

Quote:
Originally Posted by VictordeHolland View Post
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.
Mark Rose is offline   Reply With Quote
Old 2018-02-15, 18:47   #24
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

133448 Posts
Default

CRGreathouse is offline   Reply With Quote
Old 2018-02-15, 21:52   #25
VictordeHolland
 
VictordeHolland's Avatar
 
"Victor de Hollander"
Aug 2011
the Netherlands

22308 Posts
Default

Quote:
Originally Posted by alpertron View Post
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 View Post
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
VictordeHolland is offline   Reply With Quote
Old 2018-02-15, 23:39   #26
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2·659 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2018-02-16, 03:17   #27
axn
 
axn's Avatar
 
Jun 2003

10001111100012 Posts
Default

Quote:
Originally Posted by VictordeHolland View Post
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?
axn is offline   Reply With Quote
Old 2018-02-16, 16:35   #28
chris2be8
 
chris2be8's Avatar
 
Sep 2009

13·139 Posts
Default

Quote:
Originally Posted by Mark Rose View Post
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
chris2be8 is offline   Reply With Quote
Old 2018-02-16, 20:28   #29
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

72×97 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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...
ET_ is offline   Reply With Quote
Old 2018-02-17, 04:43   #30
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,543 Posts
Default

Quote:
Originally Posted by axn View Post
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).
LaurV is offline   Reply With Quote
Old 2018-02-17, 17:35   #31
chris2be8
 
chris2be8's Avatar
 
Sep 2009

13·139 Posts
Default

Quote:
Originally Posted by ET_ View Post
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
chris2be8 is offline   Reply With Quote
Old 2018-02-20, 23:27   #32
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

44668 Posts
Default

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.

Here are the code comments:

Quote:
Originally Posted by VictordeHolland View Post
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?
wblipp is offline   Reply With Quote
Old 2018-02-21, 14:09   #33
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16E416 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
p4 - 1.8 ghz - LL tests? joblack Hardware 12 2009-08-26 20:40
More P-1 tests dave_0273 Marin's Mersenne-aries 1 2006-03-23 00:03
PRP => LL-tests? Holmes Math 1 2005-05-13 17:18
Yet another set of 20 P-1 tests GP2 Completed Missions 5 2003-09-30 22:10
Bad LL Tests 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

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