3 ms·
I did it in C, my code was a bit longer. (And it has the advantage that you do not need an initial estimate for the problem to be solved in a very short time.)
by tspiteri 17y ago
I did it in C, my code was a bit longer. (And it has the advantage that you do not need an initial estimate for the problem to be solved in a very short time.)
#include <math.h>
#include <stdio.h>
double p(int throws, double pwin, int req_wins)
{
int win, i;
double log_dp = log(pwin) * throws;
double log_loss_win = log((1 - pwin) / pwin);
double ret = 0;
for (win = throws, i = 0; win >= req_wins; win -= 2, ++i) {
ret += exp(log_dp);
log_dp += log_loss_win + log((throws - i) / (i + 1.0));
}
return ret;
}
int main()
{
double pwin = 0.51;
int req_wins = 10;
double conf = 0.99;
int min, max = 1;
while (p(max, pwin, req_wins) < conf)
max *= 2;
min = max / 2;
while (min < max) {
int mid = (min + max) / 2;
if (p(mid, pwin, req_wins) < conf)
min = mid + 1;
else
max = mid;
}
printf("For %d throws, P(win $10 or more) = %f\n"
"For %d throws, P(win $10 or more) = %f\n",
min - 1, p(min - 1, pwin, req_wins),
min, p(min, pwin, req_wins));
}
The output from this program:
For 14413 throws, P(win $10 or more) = 0.989777
For 14414 throws, P(win $10 or more) = 0.990004