mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-01-26, 02:33   #1
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

7·419 Posts
Default Probability of TF per bit level

The answer is probably on the forums somewhere (pretty sure I remember reading it years ago), but I was unable to find it.

How do you calculate the probability of finding a trial factor for exponent between 2^A and 2^B?
James Heinrich is online now   Reply With Quote
Old 2011-01-26, 03:02   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100000111000012 Posts
Default

From http://v5www.mersenne.org/various/math.php
Looking at past factoring data we see that the chance of finding a factor between 2X and 2X+1 is about 1/x.

Last fiddled with by Uncwilly on 2011-01-26 at 03:05
Uncwilly is online now   Reply With Quote
Old 2011-01-26, 03:29   #3
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

7×419 Posts
Default

Ah, that's where it's hiding! Thanks Uncwilly.

Does this look like a reasonable set of probabilities for TF to various bit levels?
Code:
2^2 += 50.000% = 50.000%
2^3 += 33.333% = 66.667%
2^4 += 25.000% = 75.000%
2^5 += 20.000% = 80.000%
2^6 += 16.667% = 83.333%
2^7 += 14.286% = 85.714%
2^8 += 12.500% = 87.500%
2^9 += 11.111% = 88.889%
2^10 += 10.000% = 90.000%
2^11 += 9.091% = 90.909%
2^12 += 8.333% = 91.667%
2^13 += 7.692% = 92.308%
2^14 += 7.143% = 92.857%
2^15 += 6.667% = 93.333%
2^16 += 6.250% = 93.750%
2^17 += 5.882% = 94.118%
2^18 += 5.556% = 94.444%
2^19 += 5.263% = 94.737%
2^20 += 5.000% = 95.000%
2^21 += 4.762% = 95.238%
2^22 += 4.545% = 95.455%
2^23 += 4.348% = 95.652%
2^24 += 4.167% = 95.833%
2^25 += 4.000% = 96.000%
2^26 += 3.846% = 96.154%
2^27 += 3.704% = 96.296%
2^28 += 3.571% = 96.429%
2^29 += 3.448% = 96.552%
2^30 += 3.333% = 96.667%
2^31 += 3.226% = 96.774%
2^32 += 3.125% = 96.875%
2^33 += 3.030% = 96.970%
2^34 += 2.941% = 97.059%
2^35 += 2.857% = 97.143%
2^36 += 2.778% = 97.222%
2^37 += 2.703% = 97.297%
2^38 += 2.632% = 97.368%
2^39 += 2.564% = 97.436%
2^40 += 2.500% = 97.500%
2^41 += 2.439% = 97.561%
2^42 += 2.381% = 97.619%
2^43 += 2.326% = 97.674%
2^44 += 2.273% = 97.727%
2^45 += 2.222% = 97.778%
2^46 += 2.174% = 97.826%
2^47 += 2.128% = 97.872%
2^48 += 2.083% = 97.917%
2^49 += 2.041% = 97.959%
2^50 += 2.000% = 98.000%
2^51 += 1.961% = 98.039%
2^52 += 1.923% = 98.077%
2^53 += 1.887% = 98.113%
2^54 += 1.852% = 98.148%
2^55 += 1.818% = 98.182%
2^56 += 1.786% = 98.214%
2^57 += 1.754% = 98.246%
2^58 += 1.724% = 98.276%
2^59 += 1.695% = 98.305%
2^60 += 1.667% = 98.333%
2^61 += 1.639% = 98.361%
2^62 += 1.613% = 98.387%
2^63 += 1.587% = 98.413%
2^64 += 1.563% = 98.438%
2^65 += 1.538% = 98.462%
2^66 += 1.515% = 98.485%
2^67 += 1.493% = 98.507%
2^68 += 1.471% = 98.529%
2^69 += 1.449% = 98.551%
2^70 += 1.429% = 98.571%
2^71 += 1.408% = 98.592%
2^72 += 1.389% = 98.611%
2^73 += 1.370% = 98.630%
2^74 += 1.351% = 98.649%
2^75 += 1.333% = 98.667%
2^76 += 1.316% = 98.684%
2^77 += 1.299% = 98.701%
2^78 += 1.282% = 98.718%
2^79 += 1.266% = 98.734%
2^80 += 1.250% = 98.750%
2^81 += 1.235% = 98.765%
2^82 += 1.220% = 98.780%
2^83 += 1.205% = 98.795%
2^84 += 1.190% = 98.810%
2^85 += 1.176% = 98.824%
2^86 += 1.163% = 98.837%
2^87 += 1.149% = 98.851%
2^88 += 1.136% = 98.864%
2^89 += 1.124% = 98.876%
2^90 += 1.111% = 98.889%

Last fiddled with by James Heinrich on 2011-01-26 at 03:48
James Heinrich is online now   Reply With Quote
Old 2011-01-26, 12:00   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
From http://v5www.mersenne.org/various/math.php
Looking at past factoring data we see that the chance of finding a factor between 2X and 2X+1 is about 1/x.
When I first read this, the wording led me to interpret it as only an empirical finding derived from looking at the factoring data.

It's not merely empirical; it's analytically derived. The proof was in some thread a few years ago

Quote:
Originally Posted by James Heinrich View Post
Does this look like a reasonable set of probabilities for TF to various bit levels?
Code:
2^2 += 50.000% = 50.000%
2^3 += 33.333% = 66.667%
2^4 += 25.000% = 75.000%
2^5 += 20.000% = 80.000%
2^6 += 16.667% = 83.333%
2^7 += 14.286% = 85.714%
2^8 += 12.500% = 87.500%
2^9 += 11.111% = 88.889%
2^10 += 10.000% = 90.000%
2^11 += 9.091% = 90.909%
2^12 += 8.333% = 91.667%
2^13 += 7.692% = 92.308%
2^14 += 7.143% = 92.857%
2^15 += 6.667% = 93.333%
2^16 += 6.250% = 93.750%
2^17 += 5.882% = 94.118%
2^18 += 5.556% = 94.444%
2^19 += 5.263% = 94.737%
2^20 += 5.000% = 95.000%
2^21 += 4.762% = 95.238%
2^22 += 4.545% = 95.455%
2^23 += 4.348% = 95.652%
2^24 += 4.167% = 95.833%
2^25 += 4.000% = 96.000%
2^26 += 3.846% = 96.154%
2^27 += 3.704% = 96.296%
2^28 += 3.571% = 96.429%
2^29 += 3.448% = 96.552%
2^30 += 3.333% = 96.667%
2^31 += 3.226% = 96.774%
2^32 += 3.125% = 96.875%
2^33 += 3.030% = 96.970%
2^34 += 2.941% = 97.059%
2^35 += 2.857% = 97.143%
2^36 += 2.778% = 97.222%
2^37 += 2.703% = 97.297%
2^38 += 2.632% = 97.368%
2^39 += 2.564% = 97.436%
2^40 += 2.500% = 97.500%
2^41 += 2.439% = 97.561%
2^42 += 2.381% = 97.619%
2^43 += 2.326% = 97.674%
2^44 += 2.273% = 97.727%
2^45 += 2.222% = 97.778%
2^46 += 2.174% = 97.826%
2^47 += 2.128% = 97.872%
2^48 += 2.083% = 97.917%
2^49 += 2.041% = 97.959%
2^50 += 2.000% = 98.000%
2^51 += 1.961% = 98.039%
2^52 += 1.923% = 98.077%
2^53 += 1.887% = 98.113%
2^54 += 1.852% = 98.148%
2^55 += 1.818% = 98.182%
2^56 += 1.786% = 98.214%
2^57 += 1.754% = 98.246%
2^58 += 1.724% = 98.276%
2^59 += 1.695% = 98.305%
2^60 += 1.667% = 98.333%
2^61 += 1.639% = 98.361%
2^62 += 1.613% = 98.387%
2^63 += 1.587% = 98.413%
2^64 += 1.563% = 98.438%
2^65 += 1.538% = 98.462%
2^66 += 1.515% = 98.485%
2^67 += 1.493% = 98.507%
2^68 += 1.471% = 98.529%
2^69 += 1.449% = 98.551%
2^70 += 1.429% = 98.571%
2^71 += 1.408% = 98.592%
2^72 += 1.389% = 98.611%
2^73 += 1.370% = 98.630%
2^74 += 1.351% = 98.649%
2^75 += 1.333% = 98.667%
2^76 += 1.316% = 98.684%
2^77 += 1.299% = 98.701%
2^78 += 1.282% = 98.718%
2^79 += 1.266% = 98.734%
2^80 += 1.250% = 98.750%
2^81 += 1.235% = 98.765%
2^82 += 1.220% = 98.780%
2^83 += 1.205% = 98.795%
2^84 += 1.190% = 98.810%
2^85 += 1.176% = 98.824%
2^86 += 1.163% = 98.837%
2^87 += 1.149% = 98.851%
2^88 += 1.136% = 98.864%
2^89 += 1.124% = 98.876%
2^90 += 1.111% = 98.889%
No, it's not reasonable. Your last column of (100% - 2nd column) makes no sense.

First, understand that the 1/x probability of finding one factor does not necessarily refer to a case where there are only two factors.

Next, the series 1/1 + 1/2 + 1/3 + 1/4 + ... is divergent. As x increases, the sum up to 1/x increases, and goes past 100%, then 200%, then 300%, ...

Third, since the form of Mersenne (2p-1) factors is 2kp+1, the probability of a factor in the interval 2x and 2x+1 is actually zero until 2x+1 exceeds 2p+1 (the smallest possible candidate factor).

As long as 2x < 2p+1, there can be no factor less than 2x. Thus, trial factoring can never, ever, hope to find a factor until it searches in the range above 2floor(log[sub]2[/sub] p)+1.

(For example, an initial TF run up to 2^31 on a Mersenne number with exponent above 2 billion is practically instantaneous and proves nothing because it will never find a factor.)

Last fiddled with by cheesehead on 2011-01-26 at 12:20
cheesehead is offline   Reply With Quote
Old 2011-01-26, 14:08   #5
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

B7516 Posts
Default

First, thank you for taking the time to correct and enlighten me

Quote:
Originally Posted by cheesehead View Post
When I first read this, the wording led me to interpret it as only an empirical finding derived from looking at the factoring data.
It is, however, quoted directly from the linked page. Perhaps that page should be updated with clearer wording. That page is also missing the upper range of TF limits
(actually, I'm not sure that the whole thing shouldn't be shifted up one level, so that 516000000 => 80?)
Quote:
115300000 => 72
147500000 => 73
186400000 => 74
227300000 => 75
264600000 => 76
337400000 => 77
420400000 => 78
516000000 => 79

Quote:
First, understand that the 1/x probability of finding one factor does not necessarily refer to a case where there are only two factors.
A blindingly obvious item that slipped by me. Thanks.

Quote:
Next, the series 1/1 + 1/2 + 1/3 + 1/4 + ... is divergent. As x increases, the sum up to 1/x increases, and goes past 100%, then 200%, then 300%, ...
That's what I originally had, and then retracted, because it didn't seem to make much sense to me. I'm still not sure what a 200% chance of finding a factor means.

Quote:
Third ... trial factoring can never, ever, hope to find a factor until it searches in the range above 2floor(log[sub]2[/sub] p)+1.
Perfect, I knew the exponent size was important somewhere, but wasn't sure how it tied in.

Does this make more sense?
Code:
function TFprobability($exponent, $bits1, $bits2) {
	$chance = 0;
	$bits1 = max($bits1, floor(log($exponent, 2)) + 1);
	if ($bits2 > $bits1) {
		for ($i = $bits1; $i < $bits2; $i++) {
			$chance += (1 / $bits1);
		}
	}
	return $chance;
}
Code:
M53656597 TF to 2^1 = 0.0%
M53656597 TF to 2^2 = 0.0%
M53656597 TF to 2^3 = 0.0%
M53656597 TF to 2^4 = 0.0%
M53656597 TF to 2^5 = 0.0%
M53656597 TF to 2^6 = 0.0%
M53656597 TF to 2^7 = 0.0%
M53656597 TF to 2^8 = 0.0%
M53656597 TF to 2^9 = 0.0%
M53656597 TF to 2^10 = 0.0%
M53656597 TF to 2^11 = 0.0%
M53656597 TF to 2^12 = 0.0%
M53656597 TF to 2^13 = 0.0%
M53656597 TF to 2^14 = 0.0%
M53656597 TF to 2^15 = 0.0%
M53656597 TF to 2^16 = 0.0%
M53656597 TF to 2^17 = 0.0%
M53656597 TF to 2^18 = 0.0%
M53656597 TF to 2^19 = 0.0%
M53656597 TF to 2^20 = 0.0%
M53656597 TF to 2^21 = 0.0%
M53656597 TF to 2^22 = 0.0%
M53656597 TF to 2^23 = 0.0%
M53656597 TF to 2^24 = 0.0%
M53656597 TF to 2^25 = 0.0%
M53656597 TF to 2^26 = 0.0%
M53656597 TF to 2^27 = 3.8%
M53656597 TF to 2^28 = 7.7%
M53656597 TF to 2^29 = 11.5%
M53656597 TF to 2^30 = 15.4%
M53656597 TF to 2^31 = 19.2%
M53656597 TF to 2^32 = 23.1%
M53656597 TF to 2^33 = 26.9%
M53656597 TF to 2^34 = 30.8%
M53656597 TF to 2^35 = 34.6%
M53656597 TF to 2^36 = 38.5%
M53656597 TF to 2^37 = 42.3%
M53656597 TF to 2^38 = 46.2%
M53656597 TF to 2^39 = 50.0%
M53656597 TF to 2^40 = 53.8%
M53656597 TF to 2^41 = 57.7%
M53656597 TF to 2^42 = 61.5%
M53656597 TF to 2^43 = 65.4%
M53656597 TF to 2^44 = 69.2%
M53656597 TF to 2^45 = 73.1%
M53656597 TF to 2^46 = 76.9%
M53656597 TF to 2^47 = 80.8%
M53656597 TF to 2^48 = 84.6%
M53656597 TF to 2^49 = 88.5%
M53656597 TF to 2^50 = 92.3%
M53656597 TF to 2^51 = 96.2%
M53656597 TF to 2^52 = 100.0%
M53656597 TF to 2^53 = 103.8%
M53656597 TF to 2^54 = 107.7%
M53656597 TF to 2^55 = 111.5%
M53656597 TF to 2^56 = 115.4%
M53656597 TF to 2^57 = 119.2%
M53656597 TF to 2^58 = 123.1%
M53656597 TF to 2^59 = 126.9%
M53656597 TF to 2^60 = 130.8%
M53656597 TF to 2^61 = 134.6%
M53656597 TF to 2^62 = 138.5%
M53656597 TF to 2^63 = 142.3%
M53656597 TF to 2^64 = 146.2%
M53656597 TF to 2^65 = 150.0%
M53656597 TF to 2^66 = 153.8%
M53656597 TF to 2^67 = 157.7%
M53656597 TF to 2^68 = 161.5%
M53656597 TF to 2^69 = 165.4%
M53656597 TF to 2^70 = 169.2%
M53656597 TF to 2^71 = 173.1%
M53656597 TF to 2^72 = 176.9%
M53656597 TF to 2^73 = 180.8%
M53656597 TF to 2^74 = 184.6%
M53656597 TF to 2^75 = 188.5%
M53656597 TF to 2^76 = 192.3%
M53656597 TF to 2^77 = 196.2%
M53656597 TF to 2^78 = 200.0%
M53656597 TF to 2^79 = 203.8%
M53656597 TF to 2^80 = 207.7%
M53656597 TF to 2^81 = 211.5%
M53656597 TF to 2^82 = 215.4%
M53656597 TF to 2^83 = 219.2%
M53656597 TF to 2^84 = 223.1%
M53656597 TF to 2^85 = 226.9%
M53656597 TF to 2^86 = 230.8%
M53656597 TF to 2^87 = 234.6%
M53656597 TF to 2^88 = 238.5%
M53656597 TF to 2^89 = 242.3%
I guess the part I still don't understand is how probability goes over 100% past 2^52, and yet there's still no factors found to 2^68?

Last fiddled with by James Heinrich on 2011-01-26 at 14:11
James Heinrich is online now   Reply With Quote
Old 2011-01-26, 14:50   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
I guess the part I still don't understand is how probability goes over 100% past 2^52, and yet there's still no factors found to 2^68?
I can't say I'm 100% sure on this, but here's what I think is going on:
You should be adding expected factors, not the probability of finding a factor. For small amounts, such as most single bit levels, these two figures are about the same, but the exact formula for expected factors F given the probability of at least one factor P, is F=-log(1-P). (I should note that I'm not sure whether 1/x probability or 1/x expected factors is closer to the truth, but GIMPS's Math page implies it's the probability, not the expected factors) When you expect y factors in a range (or any other approximately Poisson-distributed random events), the probability of at least 1 factor is about 1-(e^(-y)) (which you can see, from looking at the formula in that link for the probability of exactly k occurrences, as being the probability of not having 0 factors, or 1-[probability of having exactly 0 factors]). As y grows, the probability of at least 1 factor approaches 1 (100%), but never reaches it.
e.g. in your example, from 1 to 2^78, you estimate a 200% probability of a factor at some point, which of course doesn't make sense. I think a more accurate statement would be to expect 2 factors, which gives a ~86.5% probability of at least one factor.

I also suspect that the usual 1/x probability doesn't apply in the lowest possible bit levels, due to the extremely low number of k's that make potential factors. But there's also the fact that "if a Sophie Germain prime p is congruent to 3 (mod 4), then its matching safe prime 2p + 1 will be a divisor of the Mersenne number 2^p-1" (quote from the linked Wikipedia article). It should be possible to look at GIMPS stats to draw some decent conclusions regarding this, but I don't know off hand of an easy way to do it.

Last fiddled with by Mini-Geek on 2011-01-26 at 15:09
Mini-Geek is offline   Reply With Quote
Old 2011-01-26, 18:18   #7
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

293310 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I think a more accurate statement would be to expect 2 factors, which gives a ~86.5% probability of at least one factor.
I like those numbers better. But how to get there still evades me (my math understanding is painfully lacking (you say Poisson distribution and I think of this)).

Transcribing that formula I get this:
Code:
function PoissonProbability($occurances, $expected_number) {
	$e = M_E; // 2.718281828459
	$k = $occurances;
	$Y = $expected_number;
	return (pow($Y, $k) * pow($e, -$Y)) / factorial($k);
}
(did I interpret correctly?)
But I'm not sure what to feed it to get your ~86.5% result?
James Heinrich is online now   Reply With Quote
Old 2011-01-26, 18:31   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
I like those numbers better. But how to get there still evades me (my math understanding is painfully lacking (you say Poisson distribution and I think of this)).

Transcribing that formula I get this:
Code:
function PoissonProbability($occurances, $expected_number) {
	$e = M_E; // 2.718281828459
	$k = $occurances;
	$Y = $expected_number;
	return (pow($Y, $k) * pow($e, -$Y)) / factorial($k);
}
(did I interpret correctly?)
But I'm not sure what to feed it to get your ~86.5% result?
All you want to know is [probability of at least 1 factor], which is the same as 1-[the probability of 0 factors], and the equation you have simplifies to e^-Y for [the probability of 0 factors] (because it's (Y^0*e^-Y)/0!=(1*e^-Y)/1). This should work:
Code:
function PoissonProbability($expected_number) {
	$e = M_E; // 2.718281828459
	return 1-pow($e, -$expected_number);
}
To get the ~86.5% result, you'd call PoissonProbability(2). The old function looks correct to me, but to get ~86.5%, which is the sort of figure you're after, you'd need to do 1-PoissonProbability(0, 2). Since you'd always want to find 1-PoissonProbability(0, y) (i.e. the chance of at least one factor given y expected factors), simplifying the function is the best option.

Last fiddled with by Mini-Geek on 2011-01-26 at 18:41
Mini-Geek is offline   Reply With Quote
Old 2011-01-26, 18:54   #9
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

293310 Posts
Default

Oooh, now I'm getting there!

This is what I have now:
Code:
function PoissonProbability($expected_number) {
	return 1 - pow(M_E, -$expected_number);
}

function TFprobability($exponent, $bits1, $bits2) {
	$expected = 0;
	$bits1 = max($bits1, floor(log($exponent, 2)) + 1);
	if ($bits2 > $bits1) {
		for ($i = $bits1; $i < $bits2; $i++) {
			$expected += (1 / $bits1);
		}
	}
	return PoissonProbability($expected);
}
And that outputs this kind of probabilities:
Code:
M53656597 TF to 2^1: expected=0.00; prob=0.000%
M53656597 TF to 2^2: expected=0.00; prob=0.000%
M53656597 TF to 2^3: expected=0.00; prob=0.000%
M53656597 TF to 2^4: expected=0.00; prob=0.000%
M53656597 TF to 2^5: expected=0.00; prob=0.000%
M53656597 TF to 2^6: expected=0.00; prob=0.000%
M53656597 TF to 2^7: expected=0.00; prob=0.000%
M53656597 TF to 2^8: expected=0.00; prob=0.000%
M53656597 TF to 2^9: expected=0.00; prob=0.000%
M53656597 TF to 2^10: expected=0.00; prob=0.000%
M53656597 TF to 2^11: expected=0.00; prob=0.000%
M53656597 TF to 2^12: expected=0.00; prob=0.000%
M53656597 TF to 2^13: expected=0.00; prob=0.000%
M53656597 TF to 2^14: expected=0.00; prob=0.000%
M53656597 TF to 2^15: expected=0.00; prob=0.000%
M53656597 TF to 2^16: expected=0.00; prob=0.000%
M53656597 TF to 2^17: expected=0.00; prob=0.000%
M53656597 TF to 2^18: expected=0.00; prob=0.000%
M53656597 TF to 2^19: expected=0.00; prob=0.000%
M53656597 TF to 2^20: expected=0.00; prob=0.000%
M53656597 TF to 2^21: expected=0.00; prob=0.000%
M53656597 TF to 2^22: expected=0.00; prob=0.000%
M53656597 TF to 2^23: expected=0.00; prob=0.000%
M53656597 TF to 2^24: expected=0.00; prob=0.000%
M53656597 TF to 2^25: expected=0.00; prob=0.000%
M53656597 TF to 2^26: expected=0.00; prob=0.000%
M53656597 TF to 2^27: expected=0.04; prob=3.773%
M53656597 TF to 2^28: expected=0.08; prob=7.404%
M53656597 TF to 2^29: expected=0.12; prob=10.898%
M53656597 TF to 2^30: expected=0.15; prob=14.260%
M53656597 TF to 2^31: expected=0.19; prob=17.495%
M53656597 TF to 2^32: expected=0.23; prob=20.608%
M53656597 TF to 2^33: expected=0.27; prob=23.603%
M53656597 TF to 2^34: expected=0.31; prob=26.486%
M53656597 TF to 2^35: expected=0.35; prob=29.260%
M53656597 TF to 2^36: expected=0.38; prob=31.929%
M53656597 TF to 2^37: expected=0.42; prob=34.497%
M53656597 TF to 2^38: expected=0.46; prob=36.969%
M53656597 TF to 2^39: expected=0.50; prob=39.347%
M53656597 TF to 2^40: expected=0.54; prob=41.635%
M53656597 TF to 2^41: expected=0.58; prob=43.838%
M53656597 TF to 2^42: expected=0.62; prob=45.957%
M53656597 TF to 2^43: expected=0.65; prob=47.996%
M53656597 TF to 2^44: expected=0.69; prob=49.958%
M53656597 TF to 2^45: expected=0.73; prob=51.846%
M53656597 TF to 2^46: expected=0.77; prob=53.663%
M53656597 TF to 2^47: expected=0.81; prob=55.411%
M53656597 TF to 2^48: expected=0.85; prob=57.094%
M53656597 TF to 2^49: expected=0.88; prob=58.713%
M53656597 TF to 2^50: expected=0.92; prob=60.271%
M53656597 TF to 2^51: expected=0.96; prob=61.770%
M53656597 TF to 2^52: expected=1.00; prob=63.212%
M53656597 TF to 2^53: expected=1.04; prob=64.600%
M53656597 TF to 2^54: expected=1.08; prob=65.936%
M53656597 TF to 2^55: expected=1.12; prob=67.221%
M53656597 TF to 2^56: expected=1.15; prob=68.458%
M53656597 TF to 2^57: expected=1.19; prob=69.648%
M53656597 TF to 2^58: expected=1.23; prob=70.793%
M53656597 TF to 2^59: expected=1.27; prob=71.895%
M53656597 TF to 2^60: expected=1.31; prob=72.956%
M53656597 TF to 2^61: expected=1.35; prob=73.976%
M53656597 TF to 2^62: expected=1.38; prob=74.958%
M53656597 TF to 2^63: expected=1.42; prob=75.903%
M53656597 TF to 2^64: expected=1.46; prob=76.812%
M53656597 TF to 2^65: expected=1.50; prob=77.687%
M53656597 TF to 2^66: expected=1.54; prob=78.529%
M53656597 TF to 2^67: expected=1.58; prob=79.339%
M53656597 TF to 2^68: expected=1.62; prob=80.119%
M53656597 TF to 2^69: expected=1.65; prob=80.869%
M53656597 TF to 2^70: expected=1.69; prob=81.591%
M53656597 TF to 2^71: expected=1.73; prob=82.285%
M53656597 TF to 2^72: expected=1.77; prob=82.954%
M53656597 TF to 2^73: expected=1.81; prob=83.597%
M53656597 TF to 2^74: expected=1.85; prob=84.216%
M53656597 TF to 2^75: expected=1.88; prob=84.811%
M53656597 TF to 2^76: expected=1.92; prob=85.384%
M53656597 TF to 2^77: expected=1.96; prob=85.936%
M53656597 TF to 2^78: expected=2.00; prob=86.466%
M53656597 TF to 2^79: expected=2.04; prob=86.977%
M53656597 TF to 2^80: expected=2.08; prob=87.468%
M53656597 TF to 2^81: expected=2.12; prob=87.941%
M53656597 TF to 2^82: expected=2.15; prob=88.396%
M53656597 TF to 2^83: expected=2.19; prob=88.834%
M53656597 TF to 2^84: expected=2.23; prob=89.255%
M53656597 TF to 2^85: expected=2.27; prob=89.661%
M53656597 TF to 2^86: expected=2.31; prob=90.051%
M53656597 TF to 2^87: expected=2.35; prob=90.426%
M53656597 TF to 2^88: expected=2.38; prob=90.788%
M53656597 TF to 2^89: expected=2.42; prob=91.135%
M53656597 TF to 2^90: expected=2.46; prob=91.470%
M53656597 TF to 2^91: expected=2.50; prob=91.792%
M53656597 TF to 2^92: expected=2.54; prob=92.101%
M53656597 TF to 2^93: expected=2.58; prob=92.399%
M53656597 TF to 2^94: expected=2.62; prob=92.686%
M53656597 TF to 2^95: expected=2.65; prob=92.962%
M53656597 TF to 2^96: expected=2.69; prob=93.228%
M53656597 TF to 2^97: expected=2.73; prob=93.483%
M53656597 TF to 2^98: expected=2.77; prob=93.729%
M53656597 TF to 2^99: expected=2.81; prob=93.966%
Those numbers look reasonable to me, but I'd like to hear that from someone who knows more what they're talking about (i.e. anyone but me in this thread ).
James Heinrich is online now   Reply With Quote
Old 2011-01-26, 19:20   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
First, thank you for taking the time to correct and enlighten me
You're welcome.

Quote:
It is, however, quoted directly from the linked page.
Oh, that's what I meant: first time I read it from that page. Sorry I didn't explain that.

Quote:
Originally Posted by James Heinrich View Post
This is what I have now:
Code:
function PoissonProbability($expected_number) {
    return 1 - pow(M_E, -$expected_number);
}

function TFprobability($exponent, $bits1, $bits2) {
    $expected = 0;
    $bits1 = max($bits1, floor(log($exponent, 2)) + 1);
    if ($bits2 > $bits1) {
        for ($i = $bits1; $i < $bits2; $i++) {
            $expected += (1 / $bits1);
        }
    }
    return PoissonProbability($expected);
}
And that outputs this kind of probabilities:
Code:
M53656597 TF to 2^1: expected=0.00; prob=0.000%
M53656597 TF to 2^2: expected=0.00; prob=0.000%
M53656597 TF to 2^3: expected=0.00; prob=0.000%
M53656597 TF to 2^4: expected=0.00; prob=0.000%
M53656597 TF to 2^5: expected=0.00; prob=0.000%
M53656597 TF to 2^6: expected=0.00; prob=0.000%
M53656597 TF to 2^7: expected=0.00; prob=0.000%
M53656597 TF to 2^8: expected=0.00; prob=0.000%
M53656597 TF to 2^9: expected=0.00; prob=0.000%
M53656597 TF to 2^10: expected=0.00; prob=0.000%
M53656597 TF to 2^11: expected=0.00; prob=0.000%
M53656597 TF to 2^12: expected=0.00; prob=0.000%
M53656597 TF to 2^13: expected=0.00; prob=0.000%
M53656597 TF to 2^14: expected=0.00; prob=0.000%
M53656597 TF to 2^15: expected=0.00; prob=0.000%
M53656597 TF to 2^16: expected=0.00; prob=0.000%
M53656597 TF to 2^17: expected=0.00; prob=0.000%
M53656597 TF to 2^18: expected=0.00; prob=0.000%
M53656597 TF to 2^19: expected=0.00; prob=0.000%
M53656597 TF to 2^20: expected=0.00; prob=0.000%
M53656597 TF to 2^21: expected=0.00; prob=0.000%
M53656597 TF to 2^22: expected=0.00; prob=0.000%
M53656597 TF to 2^23: expected=0.00; prob=0.000%
M53656597 TF to 2^24: expected=0.00; prob=0.000%
M53656597 TF to 2^25: expected=0.00; prob=0.000%
M53656597 TF to 2^26: expected=0.00; prob=0.000%
M53656597 TF to 2^27: expected=0.04; prob=3.773%
M53656597 TF to 2^28: expected=0.08; prob=7.404%
M53656597 TF to 2^29: expected=0.12; prob=10.898%
M53656597 TF to 2^30: expected=0.15; prob=14.260%
M53656597 TF to 2^31: expected=0.19; prob=17.495%
M53656597 TF to 2^32: expected=0.23; prob=20.608%
M53656597 TF to 2^33: expected=0.27; prob=23.603%
M53656597 TF to 2^34: expected=0.31; prob=26.486%
M53656597 TF to 2^35: expected=0.35; prob=29.260%
M53656597 TF to 2^36: expected=0.38; prob=31.929%
M53656597 TF to 2^37: expected=0.42; prob=34.497%
M53656597 TF to 2^38: expected=0.46; prob=36.969%
M53656597 TF to 2^39: expected=0.50; prob=39.347%
M53656597 TF to 2^40: expected=0.54; prob=41.635%
M53656597 TF to 2^41: expected=0.58; prob=43.838%
M53656597 TF to 2^42: expected=0.62; prob=45.957%
M53656597 TF to 2^43: expected=0.65; prob=47.996%
M53656597 TF to 2^44: expected=0.69; prob=49.958%
M53656597 TF to 2^45: expected=0.73; prob=51.846%
M53656597 TF to 2^46: expected=0.77; prob=53.663%
M53656597 TF to 2^47: expected=0.81; prob=55.411%
M53656597 TF to 2^48: expected=0.85; prob=57.094%
M53656597 TF to 2^49: expected=0.88; prob=58.713%
M53656597 TF to 2^50: expected=0.92; prob=60.271%
M53656597 TF to 2^51: expected=0.96; prob=61.770%
M53656597 TF to 2^52: expected=1.00; prob=63.212%
M53656597 TF to 2^53: expected=1.04; prob=64.600%
M53656597 TF to 2^54: expected=1.08; prob=65.936%
M53656597 TF to 2^55: expected=1.12; prob=67.221%
M53656597 TF to 2^56: expected=1.15; prob=68.458%
M53656597 TF to 2^57: expected=1.19; prob=69.648%
M53656597 TF to 2^58: expected=1.23; prob=70.793%
M53656597 TF to 2^59: expected=1.27; prob=71.895%
M53656597 TF to 2^60: expected=1.31; prob=72.956%
M53656597 TF to 2^61: expected=1.35; prob=73.976%
M53656597 TF to 2^62: expected=1.38; prob=74.958%
M53656597 TF to 2^63: expected=1.42; prob=75.903%
M53656597 TF to 2^64: expected=1.46; prob=76.812%
M53656597 TF to 2^65: expected=1.50; prob=77.687%
M53656597 TF to 2^66: expected=1.54; prob=78.529%
M53656597 TF to 2^67: expected=1.58; prob=79.339%
M53656597 TF to 2^68: expected=1.62; prob=80.119%
M53656597 TF to 2^69: expected=1.65; prob=80.869%
M53656597 TF to 2^70: expected=1.69; prob=81.591%
M53656597 TF to 2^71: expected=1.73; prob=82.285%
M53656597 TF to 2^72: expected=1.77; prob=82.954%
M53656597 TF to 2^73: expected=1.81; prob=83.597%
M53656597 TF to 2^74: expected=1.85; prob=84.216%
M53656597 TF to 2^75: expected=1.88; prob=84.811%
M53656597 TF to 2^76: expected=1.92; prob=85.384%
M53656597 TF to 2^77: expected=1.96; prob=85.936%
M53656597 TF to 2^78: expected=2.00; prob=86.466%
M53656597 TF to 2^79: expected=2.04; prob=86.977%
M53656597 TF to 2^80: expected=2.08; prob=87.468%
M53656597 TF to 2^81: expected=2.12; prob=87.941%
M53656597 TF to 2^82: expected=2.15; prob=88.396%
M53656597 TF to 2^83: expected=2.19; prob=88.834%
M53656597 TF to 2^84: expected=2.23; prob=89.255%
M53656597 TF to 2^85: expected=2.27; prob=89.661%
M53656597 TF to 2^86: expected=2.31; prob=90.051%
M53656597 TF to 2^87: expected=2.35; prob=90.426%
M53656597 TF to 2^88: expected=2.38; prob=90.788%
M53656597 TF to 2^89: expected=2.42; prob=91.135%
M53656597 TF to 2^90: expected=2.46; prob=91.470%
M53656597 TF to 2^91: expected=2.50; prob=91.792%
M53656597 TF to 2^92: expected=2.54; prob=92.101%
M53656597 TF to 2^93: expected=2.58; prob=92.399%
M53656597 TF to 2^94: expected=2.62; prob=92.686%
M53656597 TF to 2^95: expected=2.65; prob=92.962%
M53656597 TF to 2^96: expected=2.69; prob=93.228%
M53656597 TF to 2^97: expected=2.73; prob=93.483%
M53656597 TF to 2^98: expected=2.77; prob=93.729%
M53656597 TF to 2^99: expected=2.81; prob=93.966%
Those numbers look reasonable to me, but I'd like to hear that from someone who knows more what they're talking about (i.e. anyone but me in this thread ).
I'm not familiar enough with Poisson distribution to always remember to mention it or apply it when applicable, such as here.

I think that there needs to be further refinement to take account of the digital effect as exponents pass a power-of-two. (Our custom of TFing between exact powers of two is an artificial one.)

As it stands, the same expectation and probability is calculated for any exponent for which floor(log($exponent, 2)) is the same value, but I don't think that's realistic. (Yes, I introduced the floor, but it was to make a different point.)

Perhaps what's happening is that the 1/x approximation was okay for integrating over many values, but as we examine specific cases it needs to be replaced by a different function that approaches 1/x as a limit. But I'm speculating about things I don't know.

Last fiddled with by cheesehead on 2011-01-26 at 19:47
cheesehead is offline   Reply With Quote
Old 2011-01-26, 19:48   #11
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Code:
$expected += (1 / $bits1);
I think it'd be more accurate to do "$expected += -log(1 - (1 / $bits1));". This is so that you're incrementing the number of expected factors by the number of expected factors for that bit level, not by the probability of a factor in that bit level. As for where that equation came from: it's 1-(e^-Y)=P solved for Y: Y=-log(1-P). It's a pretty small difference, but there is a difference, e.g. in your newest example at 2^99 the numbers are expected=2.81; prob=93.966%, but with that change it's 2.86 and 94.291%, respectively. In any case, you're definitely on the right track now!
Quote:
Originally Posted by cheesehead View Post
But I do know that there needs to be further refinement to take out the false imposition of discrete steps as exponents pass a power-of-two.
Yes, I agree. Not sure how to fix it, and it's probably even more minor than the thing I just pointed out, but ideally it should be fixed.
Mini-Geek is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
TF bit level davieddy Puzzles 71 2013-12-22 07:26
ECM level program henryzz GMP-ECM 8 2012-09-15 17:00
any mid -level sequence left? firejuggler Aliquot Sequences 5 2012-02-09 11:02
Reliability and confidence level lidocorc Information & Answers 6 2009-08-11 04:04
Factors appearing at level 62 ric Lone Mersenne Hunters 7 2005-09-06 12:12

All times are UTC. The time now is 18:42.

Tue Aug 11 18:42:49 UTC 2020 up 25 days, 14:29, 2 users, load averages: 2.01, 1.83, 1.66

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.