Today, the following question came up: How many times do i have to roll the dice to get every number at least once.
I calculated, that the expected value shoud be 6*(1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6) = 14,7 and that i would need 6^2 = 36 throws to be 99% sure.
Well, but i wasn’t really sure about it. That’s why, i thought, that i should write a little php script for that:
<?php
if(!is_numeric($_SERVER['argv'][1])) die("Zahl eingeben!\n");
$erfolg=0;
$fails=array();
for($i=6; $i<=36; $i++) $fails[$i]=0;
// $fails=array(15=>0, 25=>0, 36=>0);
for($i=0; $i<$_SERVER['argv'][1]; $i++) {
$ii=0;
$array=array(false, false, false, false, false, false);
while($ii<100000) {
$ii++;
$array[rand()%6]=true;
$leave=true;
foreach($array as $val) {
if($val===false) {
$leave=false;
break;
}
}
if($leave) break;
}
for($num=6; $num<=36; $num++) {
if($ii>$num) $fails[$num]++;
}
$erfolg+=$ii;
}
echo "Erfolgschnitt : ".($erfolg/$_SERVER['argv'][1])."\n";
foreach($fails as $num=>$val) {
echo "Failquote $num: ".(($fails[$num]/$_SERVER['argv'][1])*100)."%\n";
}
I realized, that it took a lot of time and i wanted to have some results today!
After approximately 20 seconds i stopped the script. I think, php’s internal datastructure isn’t that optimal.
So i thought, let’s write a c version to get the results, that i wanted to have:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#define bool int
#define true 1
#define false 0
int main (int nArgs_p, char *pszArg_p[])
{
long lSize = 0;
int i=0;
int ii=0;
int iii=0;
bool leave=true;
bool wuerfl[6];
int fails[37];
long long erfolg=0;
long long llSum;
srand ( time(NULL) );
for(i=0; i<37; i++) fails[i]=0;
if (nArgs_p > 1)
{
lSize = atol(pszArg_p[1]);
}
else {
printf("Zahl eingeben!\n");
return 1;
}
for(i=0; i<lSize; i++) {
for(ii=0; ii<6; ii++) wuerfl[ii]=false;
ii=0;
while(ii<100000) {
ii++;
wuerfl[rand()%6]=true;
leave=true;
for(iii=0; iii<6; iii++) {
if(wuerfl[iii]==false) {
leave=false;
break;
}
}
if(leave) break;
}
erfolg+=ii;
for(iii=6; iii<=36; iii++) {
if(ii>iii) fails[iii]++;
}
}
printf("\nErfolgsschnitt bei %ld: %14.9lf", lSize, ((double)erfolg / (double)lSize));
for(i=6; i<=36; i++) {
printf("\nFailquote %2ld: %14.6lf%%", i, ((double)fails[i] / (double)lSize)*100);
}
printf("\n");
return 0;
}
After that, i was a bit curious about hiphop’s performance on this. According to facebook they compile your php source to c++ source.
At the end i’ve run each version in the following order: C, hiphop(hphp) and php.
…and the results are:
- approx. 1s in C
- approx. 9.5s in hphp (so the c version is 9.5 times faster)
- approx. 34.3s in php (so the hphp version is 3.6 times faster)
Amazing! I think hiphop uses another datastructure to store the values.
mweber@ubuntu:~# time ./wuerfeln 1000000
Erfolgsschnitt bei 1000000: 14.704265000
Failquote 6: 98.441900%
Failquote 7: 94.586800%
Failquote 8: 88.612600%
Failquote 9: 81.068600%
Failquote 10: 72.816500%
Failquote 11: 64.368000%
Failquote 12: 56.239300%
Failquote 13: 48.642500%
Failquote 14: 41.773900%
Failquote 15: 35.687500%
Failquote 16: 30.299300%
Failquote 17: 25.612700%
Failquote 18: 21.578400%
Failquote 19: 18.172300%
Failquote 20: 15.255100%
Failquote 21: 12.770600%
Failquote 22: 10.671400%
Failquote 23: 8.923200%
Failquote 24: 7.464500%
Failquote 25: 6.230700%
Failquote 26: 5.212600%
Failquote 27: 4.352800%
Failquote 28: 3.634500%
Failquote 29: 3.025400%
Failquote 30: 2.513500%
Failquote 31: 2.092600%
Failquote 32: 1.738300%
Failquote 33: 1.449800%
Failquote 34: 1.200900%
Failquote 35: 1.002800%
Failquote 36: 0.833600%
real 0m0.965s
user 0m0.964s
sys 0m0.000s
mweber@ubuntu:~# time ./wuerfelnhphp/program 1000000
Erfolgschnitt : 14.709768
Failquote 6: 98.4506%
Failquote 7: 94.5824%
Failquote 8: 88.5587%
Failquote 9: 81.0715%
Failquote 10: 72.8546%
Failquote 11: 64.4157%
Failquote 12: 56.2674%
Failquote 13: 48.6804%
Failquote 14: 41.7905%
Failquote 15: 35.6534%
Failquote 16: 30.2511%
Failquote 17: 25.5854%
Failquote 18: 21.5718%
Failquote 19: 18.1589%
Failquote 20: 15.276%
Failquote 21: 12.7943%
Failquote 22: 10.7217%
Failquote 23: 8.9401%
Failquote 24: 7.4972%
Failquote 25: 6.2734%
Failquote 26: 5.2445%
Failquote 27: 4.3744%
Failquote 28: 3.6513%
Failquote 29: 3.0443%
Failquote 30: 2.5386%
Failquote 31: 2.1068%
Failquote 32: 1.761%
Failquote 33: 1.4654%
Failquote 34: 1.2189%
Failquote 35: 1.0189%
Failquote 36: 0.8557%
real 0m9.449s
user 0m9.437s
sys 0m0.012s
mweber@ubuntu:~# time php ./wuerfeln.php 1000000
Erfolgschnitt : 14.694884
Failquote 6: 98.4516%
Failquote 7: 94.5731%
Failquote 8: 88.5453%
Failquote 9: 81.0262%
Failquote 10: 72.7975%
Failquote 11: 64.3744%
Failquote 12: 56.1996%
Failquote 13: 48.5864%
Failquote 14: 41.6888%
Failquote 15: 35.5515%
Failquote 16: 30.157%
Failquote 17: 25.4991%
Failquote 18: 21.492%
Failquote 19: 18.0759%
Failquote 20: 15.1766%
Failquote 21: 12.7463%
Failquote 22: 10.6968%
Failquote 23: 8.9528%
Failquote 24: 7.4691%
Failquote 25: 6.2347%
Failquote 26: 5.2058%
Failquote 27: 4.3439%
Failquote 28: 3.6347%
Failquote 29: 3.0244%
Failquote 30: 2.5226%
Failquote 31: 2.0964%
Failquote 32: 1.7409%
Failquote 33: 1.447%
Failquote 34: 1.2037%
Failquote 35: 1.0115%
Failquote 36: 0.842%
real 0m34.257s
user 0m34.218s
sys 0m0.032s