[PHP] Random value generators

[Jurgle]

Deze thread las ik en begon ik me af te vragen wat nou het verschil tussen rand() en mt_rand() is.

Daarom heb ik nu een vraagstuk over de twee random value generators in PHP. Het gaat dus om rand() en mt_rand(). In de PHP manual wordt gesteld dat mt_rand() beter en sneller is.

Maar waarom dan? Dus heb ik een scriptje geschreven dat twee record sets van 100000 records met elk 1 random value genereerd (met een minimum van 0 en maximum van 100). De ene door rand() en de ander door mt_rand().

Daar berekent de standaardafwijking van. Deze zet ik in resp. $_SESSION['rand'][] en $_SESSION['mt_rand'][]. Na dit 100 keer gedaan te hebben rekent PHP de gemiddelden en de standaardafwijkingen uit van de standaardafwijkingen uit de SESSIE.

Hij echo't na 100 gedraait te hebben de laatste bevindingen van de random generator datasets en de gegevens uit de SESSIE.

Het resultaat geeft minimale verschillen aan. Waarom is mt_rand() beter dan rand() (behalve dattie sneller is)? Of is mijn manier van onderzoeken verkeerd? Of hebben de kleine verschillen grote gevolgen?

Hieronder de code:
(mocht je dit script ook willen runnen: per opvraag doettie er op een P4 2,4 GHz, 512MB zo'n 8 seconde over. Met 100 keer runnen (wattie doet) ben je dan dus een klein kwartiertje bezig...)

PHP:

<?PHP

class dataSet
{
   var $data;
   
   function dataSet()
   {
      $this->data = array();
      
      if(func_num_args() > 0)
         if(func_num_args() == 1)
            $this->add(func_get_arg(0));
         else
            $this->add(func_get_args());
   }
   
   function add()
   {
      $n = func_num_args();
      
      if($n == 1)
         $nr = func_get_arg(0);
      else
         $nr = func_get_args();
      
      if(!is_integer($nr) && !is_float($nr))
         if(!is_array($nr))
            return 0;
         else
         {
            for($i = 0; $i < count($nr); $i++)
               $this->add($nr[$i]);
            return;
         }
      
      $this->data[] = $nr;
      
      return 1;
   }
   
   function getMdn()
   {
      if($this->data == array())
         return 0;
      
      $tmp = $this->data;
      
      sort($tmp, SORT_NUMERIC);
      
      $c = count($tmp);
      if($this->isEven($c))
         return (($tmp[floor(count($tmp)/2)] + $tmp[ceil(count($tmp)/2)]) / 2);
      return $tmp[(count($tmp)/2)];
   }
   
   function getMds()
   {
      if($this->data == array())
         return 0;
      
      $mod_arr = array();
      
      for($i = 0; $i < count($this->data); $i++)
      {
         if(!isset($mod_arr[$this->data[$i]]))
            $mod_arr[$this->data[$i]] = 0;
         $mod_arr[$this->data[$i]]++;
      }
      
      arsort($mod_arr, SORT_NUMERIC);
      
      $keys = array_keys($mod_arr);
      
      $n = $mod_arr[$keys[0]];
      $modus = array();
      
      for($i = 0; $i < count($mod_arr); $i++)
         if($mod_arr[$keys[$i]] == $n)
            $modus[] = $keys[$i];
         else
            $i = count($mod_arr);
      
      return $this->getAvg($modus);
   }
   
   function getAvg($a = 0)
   {
      if($a == 0)
         $a = $this->data;
      
      $sum = 0;
      for($i = 0; $i < count($a); $i++)
         $sum += $a[$i];
      
      return $sum/count($a);
   }
   
   function getStdDev()
   {
      $avg = $this->getAvg();
      
      $d = array();
      
      for($i = 0; $i < count($this->data); $i++)
         $d[] = pow(($avg - $this->data[$i]), 2);
      
      return sqrt($this->getAvg($d));
   }
   
   function isEven($nr = "")
   {
      if($nr == "")
         return $this->isEven(counr($this->data));
      return (($nr % 2) == 0)? 1: 0;
   }
   
   function getData()
   {
      return $this->data;
   }
   
   function printSumm()
   {
      echo "Records: ".count($this->data)."<BR />";
      echo "Average: ".$this->getAvg()."<BR />";
      echo "Modus: ".$this->getMds()."<BR />";
      echo "Median: ".$this->getMdn()."<BR />";
      echo "Std.Dev: ".$this->getStdDev()."<BR />";
      echo "<BR />";
   }
}

session_start();


$arr = array();
for($i = 0; $i < 100000; $i++)
   $arr[] = rand(0, 100);
$ds = new dataSet($arr);
echo "rand()<br>";
$_SESSION['rand'][] = $ds->getStdDev();
$ds->printSumm();

$arr = array();
for($i = 0; $i < 100000; $i++)
   $arr[] = mt_rand(0, 100);
$ds = new dataSet($arr);
echo "mt_rand()<br>";
$_SESSION['mt_rand'][] = $ds->getStdDev();
$ds->printSumm();


if(count($_SESSION['rand']) > 99)
{
   $ds = new dataSet($_SESSION['rand']);
   echo "Rand stddev avg: ".$ds->getAvg()."<br>";
   echo "Rand stddev stddev: ".$ds->getStdDev()."<br>";
   
   echo "\n<br>";
   
   $ds = new dataSet($_SESSION['mt_rand']);
   echo "Mt_rand stddev avg: ".$ds->getAvg()."<br>";
   echo "Mt_rand stddev stddev: ".$ds->getStdDev()."<br>";
   
   $_SESSION = array();
   session_destroy();
}
else
{
   echo count($_SESSION['rand']);
   header("Location: ".$_SERVER['PHP_SELF']);
}

?>

/edit
Bij een timeout kan je gewoon refreshen en gaattie verder, vars staan in SESSIE.

[ Voor 9% gewijzigd door Jurgle op 17-10-2003 23:31 ]

[Jurgle]

Het duurde even voordat ik resultaten had, bij deze:

// Dit is de laatste rand() dataSet result
rand()
Records: 100000
Average: 50.03881
Modus: 66
Median: 50
Std.Dev: 29.1526414547

// Dit is de laatste mt_rand() dataSet result
mt_rand()
Records: 100000
Average: 49.96248
Modus: 79
Median: 50
Std.Dev: 29.1395952657

// Dit zijn de overall gegevens:
Rand stddev avg: 29.1579330013
Rand stddev stddev: 0.0418311649879

Mt_rand stddev avg: 29.1584802316
Mt_rand stddev stddev: 0.0381771130969

[Verwijderd]

ik denk dat als ik hier een statistische variatieanalyse (SS Error) op los laat dat er geen significant verschil is..

[Jurgle]

Inderdaad, maar waarom wordt er dan in de PHP manual beweerd dat de mt_rand() betere random numbers genereert dan rand()???

edit:
genereerd is met een t

[ Voor 16% gewijzigd door Jurgle op 18-10-2003 00:00 ]

[Soultaker]

Het gaat om de rand() functie uit de traditionele C libraries. Probleem hiermee is dat 'ie niet over alle bits genoeg varieert. Uit de random man-page:

The difference is that rand(3) produces a much less random sequence -- in fact, the low dozen bits generated by rand go through a cyclic pattern.

Als je dus random bits wil hebben, is het onverstandig om iets in de trant van "rand() % 2" te doen.

[Jurgle]

...trant van "rand() % 2"...

Ja maar... ik heb de regels 137 en 147 veranderd naar respectievelijk:
137 $arr[] = rand()%2;
en
147 $arr[] = mt_rand()%2;

Nu krijg ik dit als result:

rand()
Records: 100000
Average: 0.49926
Modus: 0
Median: 0
Std.Dev: 0.4999994524

mt_rand()
Records: 100000
Average: 0.49789
Modus: 0
Median: 0
Std.Dev: 0.49999554788

Rand stddev avg: 0.499997380269
Rand stddev stddev: 3.47475114137E-006

Mt_rand stddev avg: 0.49999761113
Mt_rand stddev stddev: 3.51970594987E-006

Dit is ook niet echt dat je zegt een verschil.

* Jurgle snapt het nog niet helemaal...

[raoulduke]

Ja maar het gaat niet om de afwijking, maar het kunnen voorspellen. Als je rand() gebruikt, die 'cyclic' gedrag vertoont, zal je al snel kunnen voorspellen of rand()%2 1 of 0 wordt, omdat er zich een patroon voordoet, in het ergste geval gewoon 1010101010101. Dat is niet bepaald willekeurig, maar wel precies statistisch correct verdeeld.

Je controleert dus niet op de kwaliteit van de random nummers, alleen de verdeling. Daarmee kan je absoluut niet bepalen welk algoritme 'willekeuriger' is.

[ Voor 3% gewijzigd door raoulduke op 18-10-2003 12:26 ]

[Jurgle]

ah, ok... is dit wel te testen dan? Of moet je het wiskundig aanpakken door vergelijkingen tegen elkaar weg te strepen en bewijzen dat de ene willekeuriger is dan de ander?

[raoulduke]

Het is niet te testen. Want hoe definieer je 'willekeurig'? Statistisch goed verdeeld is iets anders dan 'willekeurigheid': als ik een PRN-generator maak die als volgt werkt (pseudo-code):

code:

getRand(int max)
{
 static int prev;

 prev=(prev+1)%max;

 return prev;
}

Dan krijg je een perfect statistisch verdeeld resultaat, maar het is gewoon cyclisch en voldoet niet aan de menselijke definitie van 'willekeurig'. Als je je erin wil verdiepen zou ik op Google eens zoeken naar entropie (Engels: entropy), dus de informatiewaarde van een gegeven hoeveelheid data.

[Soultaker]

Statistische basiseigenschappen als spreiding en gemiddelde zijn natuurlijk een eenvoudig begin bij de beschouwing van "randomness".

Er zijn ook (complexere) wiskundige algoritmen die een getalletje kunnen koppelen aan een stroom van "random" getallen, die de mate van "randomness" aangeeft. Algoritmen als Chi² zijn bijvoorbeeld wel te vinden met Google (zoeken op "randomness tests" ofzo). Uiteraard test elk algoritme een net iets andere eigenschap en het is dus belangrijk om de achtergrond van elk algoritme te kennen om de uitvoer ervan op z'n waarde te schatten.

Mijn punt is dus dat je best kunt "bewijzen" hoe random je getallen zijn, zodra je hebt vastgelegd wat voor soort "randomness" je bedoelt.

[ Voor 16% gewijzigd door Soultaker op 19-10-2003 16:48 ]