mersenneforum.org  

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

Reply
 
Thread Tools
Old 2013-02-05, 18:26   #1
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

265268 Posts
Default How to guess M#48's exponent to < 1% (based on qwiki-leaks)

In the 48th Mersenne prime discovered?!! thread I promised to show how one could have ascertained the new prime's exponent to within 1% using only information inadvertently leaked in that thread by "people in the know" plus a bit of math, without any recourse to Primenet server data. OK, so here's how:

In post #38, I let slip that Serge's verify run used a vector length of 3328 Kdoubles, which is larger than default for the exponent in question. In posts #40-41 Ralf and ATH dig up fossilized data from the days when Mlucas still used hard-coded FFT-length / exponent breakpoints, and ATH correctly concludes that the exponent must be less that the lower limit for 3328 K, which for that earlier version of the code implies p < 58050000. In post #43 I note that the Current Mlucas breakpoint for transitioning from 3072 K to 3328 K is p = 58569855, so that is the true upper bound on the new prime's exponent.

[Using the runlengths supported by Mlucas, the other possibility besides 3072 K is 2816 K, but that is unlikely because it implies an exponent < ~54 M, well below the range of most recent first-time tests.]

Now here is where things could very quickly have gotten very interesting ... In post #63 Mike gives a millionth-iteration status line from his Mlucas run, with exponent obscured. Mike was so busy being clever in also replacing the true hex residue with a hex string that reads amusingly that he failed to realize that the roundoff error stats in the same printouts also convey useful information, in this case

MaxErr = 0.218750000

It's widely known that for Prime95 and similar code MaxErr ~= 0.4 is the danger threshold, so it makes sense that the FFT length breakpoints occur at roughly that level of ROE. Thus, p = 58569855 (or whatever the closest prime is to that) gives MaxErr ~= 0.4 at 3072 K. What exponent gives MaxErr = 0.21875 at that FFT length?

To figure that out it helps to refer to the paper I referenced in post 43, which is the basis for the breakpoint-computing code snippet there. (The PDF I have at the hogranch.com ftp server is easily found via cursory web search). Specifically, eqn [7] in the paper shows that for a given FFT length, ROE scales as the square of the average input wordsize. sqrt(0.21875/0.4) ~= 0.74, so the new M-prime yields an average input wordsize 0.74 that of p = 58569855 at 3072 K. To estimate p we need to compute the ratio of average *bits* per word which corresponds to that wordsize ratio: 2b1/2b2 = 0.74, with b2 = 58569855/(3072*210) = 18.618... .

Thus the new prime has average bits per word of roughly b1 = lg(0.74*2b2) = 18.1834969... average bits per input word. Multiplying by 3072 K gives p ~= 57200335, which is just a tad over 1% off from the true value, 57885161.

----

But one further improve on that, since it not necessary to "take my word for it" that the aforementioned breakpoint-computing function uses a roundoff threshold of 0.4. In fact anyone who was written FFT code, especially including non-power-of-2 runlengths, will notice that the breakpoint function makes no allowance for the kinds of systematic error-level variations arising as a result of the details of the FFT radices used: radices which factor less smoothly due to the presence of one or more odd primes tend to have more roundoff accumulation due to their relatively higher cost in terms of operations-per-input, for example. In this case the actual code is easy to obtain; running a 1000-iteration timing self-test at 3072 K yields this sort of output:

1000 iterations of M58569809 with FFT length 3145728 = 3072 K
Res64: DC08E05E46E39ECF. AvgMaxErr = 0.216503057. MaxErr = 0.281250000. Program: E3.0x

The prime used, 58569809, is trivially different from the above (composite) breakpoint value of 58569855, but simply substituting it and the actual error level observed - which is appreciably less than 0.4 due to the smoothness of 3072 K - we get sqrt(0.21875/0.28125) ~= 0.88, so the new M-prime yields an average input wordsize 0.88 that of p = 58569809 at 3072 K. To estimate p we again compute the ratio of average *bits* per word which corresponds to that wordsize ratio: 2b1/2b2 = 0.88..., with b2 = 58569809/(3072*210) = 18.6188... .

Thus the new prime yields an average of b1 = lg(0.88*2b2) = 18.4375558... bits per input word. Multiplying by 3072 K gives p ~= 57999536, which is less than 0.2% away from the true value, 57885161.

Last fiddled with by ewmayer on 2013-02-05 at 22:59 Reason: Ficksen der misch-schpellinkes, use [sup] for exponents
ewmayer is offline   Reply With Quote
Old 2013-02-05, 21:59   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

cheesehead is offline   Reply With Quote
Old 2013-02-05, 22:06   #3
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

22×3×5×7×19 Posts
Default

Quote:
…failed to realize that the roundoff error stats in the same printouts also convey useful information…

Last fiddled with by ewmayer on 2013-02-05 at 22:49 Reason: It's gonna take more than 1 kitten to atone for your leakage-crime, buster ... I want a basketful. And they better be extra fluffy, and enjoy being juggled.
Xyzzy is offline   Reply With Quote
Old 2013-02-06, 02:56   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·3·1,013 Posts
Default

Nice analysis, BUT ...

There is a problem that you haven't covered. We can't trust any of the figures that are posted here. It could be that figures have been deliberately doctored to mislead and generally mess with people's heads. It could be that the round-off figures were doctored and not genuine. It could be that the FFT size was secretly discussed amongst those in-the-know and decided to publicly give a fake value. It could be that pretty much every other indicator was a pure fabrication. Even the M(xxxxxxxx) milestone values could have been fakes deliberately designed to mislead. Without seeing actual figures that one knows have not been doctored it becomes simply a guessing game with which information to trust and which to ignore.

When you are in-the-know then you implicitly know which figures are accurate and thus how to make the computations. For outsiders it becomes a lot more problematic with following false trails and dead-ends that complicate matters considerably.
retina is online now   Reply With Quote
Old 2013-02-06, 04:08   #5
axn
 
axn's Avatar
 
Jun 2003

23·607 Posts
Default

Quote:
Originally Posted by retina View Post
There is a problem that you haven't covered. We can't trust any of the figures that are posted here.
PWNED
axn is offline   Reply With Quote
Old 2013-02-06, 04:44   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101010101102 Posts
Default

Well, as with any interrogation, ya gotta try to figure out which data are more likely genuine. My note about Serge running @3328 K didn't strike a false chord, because it fit with the current GIMPS wavefront, and in itself was not very revealing.

In Mike's note, the res64 was obviously fake, but the two ROE numbers both 'looked real', the larger had the kind of simple bit pattern that ROE data anywhere close to 0.5 do, and the max/avg ratio could easily be checked against those output by an actual build. And since ROE numbers not-really-close-to-a-breakpoint are unrevealing to the unpracticed eye, it didn't need a huge leap of faith to figure those might be unfudged.

Easy? No. But not out of the realm of cleverness of our more eagle-eyed members, IMO.
ewmayer is offline   Reply With Quote
Old 2013-02-06, 08:39   #7
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×3×1,013 Posts
Default

Quote:
Originally Posted by ewmayer View Post
... the two ROE numbers both 'looked real', ...
I agree. But that doesn't mean it is real. You are all clever people and making it 'look real' would not be too difficult a task.
Quote:
Originally Posted by ewmayer View Post
... the larger had the kind of simple bit pattern that ROE data anywhere close to 0.5 do, and the max/avg ratio could easily be checked against those output by an actual build.
Yes, and just as easily those numbers could be copy-pasted from a different exponent to make a fake result 'look real'.
Quote:
Originally Posted by ewmayer View Post
And since ROE numbers not-really-close-to-a-breakpoint are unrevealing to the unpracticed eye, it didn't need a huge leap of faith to figure those might be unfudged.
Leaps of faith are great and all, but ultimately still faith based and requires belief in all the numbers posted by the various parties.
Quote:
Originally Posted by ewmayer View Post
Easy? No. But not out of the realm of cleverness of our more eagle-eyed members, IMO.
I actually never bothered to even try this time because of the potential for misleading posts to make all that effort a pointless exercise with those in-the-know laughing from the sidelines. It was only when I saw the milestone post that I decided I would give that one a shot since I already had the relevant data available to count exponents and see which one it was. But even that was faith based and depended upon the milestone page not being fudged in any way, which was certainly not guaranteed.

Anyhow, the point is that when you know the numbers are real then it is not too difficult to work out such things. But we minions, from the unwashed masses, had no guarantee that the numbers given were real. Our lord masters, the privileged verifiers with limitless intelligence and clevertudiness, have tricksy unfathomable ways of fooling with our efforts at discovery.
retina is online now   Reply With Quote
Old 2013-02-06, 09:15   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

23·19·61 Posts
Default

See? That is why I asked for it! To avoid arguments like this

(not that I would have any chance to guess it, my expectation (after the first posts about finding a new prime) was in the 61M area, I was a bit disappointed when my man told me the expo, and didn't really believe it until the official announcement).

Last fiddled with by LaurV on 2013-02-06 at 09:16
LaurV is offline   Reply With Quote
Old 2013-02-06, 09:27   #9
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

Quote:
Originally Posted by ewmayer View Post
In the 48th Mersenne prime discovered?!! thread I promised to show how one could have ascertained the new prime's exponent to within 1% using only information inadvertently leaked in that thread by "people in the know" plus a bit of math, without any recourse to Primenet server data. OK, so here's how:

< the big snip>
So simple, how could I have missed it?
Must be the Ardbeg.

D
davieddy is offline   Reply With Quote
Old 2013-02-06, 17:21   #10
flashjh
 
flashjh's Avatar
 
"Jerry"
Nov 2011
Vancouver, WA

1,123 Posts
Default

I knew the exponent this time, for obvious reasons. However, for next time your explanation is very informative.

Personally, I wish I knew more about the math (and I'm working on learning). Really, the challenge of finding the exponent is a lot of fun.

Thanks!
flashjh is offline   Reply With Quote
Old 2013-02-06, 17:33   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by flashjh View Post
I knew the exponent this time, for obvious reasons. However, for next time your explanation is very informative.

Personally, I wish I knew more about the math (and I'm working on learning). Really, the challenge of finding the exponent is a lot of fun.

Thanks!

once the milestone thing came up I kinda tried but failed to find the correct one, the number of primes in between the known exponents , and the amount needed to prove that one is the x-th one can be used to roughly figure how many have no need to be double checked in that range and so you add the difference of these to the amount needed to be checked until the exponent in question and a few other things and I still messed it up by 20 million when I tried.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I guess this is OPN-related fivemack Factoring 1 2017-01-05 17:55
I guess my computer is getting old... ixfd64 Hardware 3 2009-03-05 13:20
Guess my IQ 10metreh Lounge 7 2008-12-29 20:34
Guess a Number davar55 Puzzles 11 2008-03-19 21:33
Guess the Polynomial Kevin Puzzles 15 2007-09-25 17:22

All times are UTC. The time now is 11:22.

Sun Feb 28 11:22:28 UTC 2021 up 87 days, 7:33, 0 users, load averages: 1.39, 1.49, 1.35

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.