 mersenneforum.org Probability of TF per bit level
 Register FAQ Search Today's Posts Mark Forums Read  2011-01-26, 02:33 #1 James Heinrich   "James Heinrich" May 2004 ex-Northern Ontario 2·37·43 Posts 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?   2011-01-26, 03:02 #2 Uncwilly 6809 > 6502   """"""""""""""""""" Aug 2003 101×103 Posts 2×4,441 Posts 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   2011-01-26, 03:29 #3 James Heinrich   "James Heinrich" May 2004 ex-Northern Ontario C6E16 Posts 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   2011-01-26, 12:00   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts Quote:
 Originally Posted by Uncwilly 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 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   2011-01-26, 14:08   #5
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

2·37·43 Posts First, thank you for taking the time to correct and enlighten me Quote:
 Originally Posted by cheesehead 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   2011-01-26, 14:50 #6 Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts Quote:  Originally Posted by James Heinrich 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   2011-01-26, 18:18 #7 James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 2×37×43 Posts Quote:  Originally Posted by Mini-Geek 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?   2011-01-26, 18:31 #8 Mini-Geek Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 17×251 Posts Quote:  Originally Posted by James Heinrich 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   2011-01-26, 18:54 #9 James Heinrich "James Heinrich" May 2004 ex-Northern Ontario 2×37×43 Posts 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 ).   2011-01-26, 19:20   #10

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts Quote:
 Originally Posted by James Heinrich 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 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   2011-01-26, 19:48   #11
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts Quote:
 Originally Posted by James Heinrich 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 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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post davieddy Puzzles 71 2013-12-22 07:26 henryzz GMP-ECM 8 2012-09-15 17:00 firejuggler Aliquot Sequences 5 2012-02-09 11:02 lidocorc Information & Answers 6 2009-08-11 04:04 ric Lone Mersenne Hunters 7 2005-09-06 12:12

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

Fri Nov 27 11:13:24 UTC 2020 up 78 days, 8:24, 4 users, load averages: 1.10, 1.24, 1.32