A Mersenne_Twister Implementation in PHP

I am confused. I found this great Mersenne_Twister implementation to compensate for the fact the at mt_srand() and mt_rand() don’t generate predictable sequences since PHP 5.2.1. From www.php.net:

The Mersenne Twister implementation in PHP now uses a new seeding algorithm by Richard Wagner. Identical seeds no longer produce the same sequence of values they did in previous versions. This behavior is not expected to change again, but it is considered unsafe to rely upon it nonetheless.

What confuses me is that I cannot figure out where I found this code. In my notes have it at www.php.net in the comments – but I cannot re-find that comment on mt_srand() entry – perhaps it was deleted.

So that it is not lost, I reproduce it here.


class Mersenne_Twister
{
  private $state = array ();
  private $index = 0;

  public function __construct($seed = null) {
    if ($seed === null)
      $seed = mt_rand();

    $this->setSeed($seed);
  }

  public function setSeed($seed) {
    $this->state[0] = $seed & 0xffffffff;

    for ($i = 1; $i < 624; $i++) {
      $this->state[$i] = (((0x6c078965 * ($this->state[$i - 1] ^ ($this->state[$i - 1] >> 30))) + $i)) & 0xffffffff;
    }

    $this->index = 0;
  }

  private function generateTwister() {
    for ($i = 0; $i < 624; $i++) {
      $y = (($this->state[$i] & 0x1) + ($this->state[$i] & 0x7fffffff)) & 0xffffffff;
      $this->state[$i] = ($this->state[($i + 397) % 624] ^ ($y >> 1)) & 0xffffffff;

      if (($y % 2) == 1) {
        $this->state[$i] = ($this->state[$i] ^ 0x9908b0df) & 0xffffffff;
      }
    }
  }

  public function getNext($min = null, $max = null) {
    if (($min === null && $max !== null) || ($min !== null && $max === null))
      throw new Exception('Invalid arguments');

    if ($this->index === 0) {
      $this->generateTwister();
    }

    $y = $this->state[$this->index];
    $y = ($y ^ ($y >> 11)) & 0xffffffff;
    $y = ($y ^ (($y << 7) & 0x9d2c5680)) & 0xffffffff;
    $y = ($y ^ (($y << 15) & 0xefc60000)) & 0xffffffff;
    $y = ($y ^ ($y >> 18)) & 0xffffffff;

    $this->index = ($this->index + 1) % 624;

    if ($min === null && $max === null)
      return $y;

    $range = abs($max - $min);

    return min($min, $max) + ($y % ($range + 1));
  }
}

I also wrote a PHP Mersenne_Shuffle() function called that produces a predictable shuffle using the Mersenne_Twister().


// http://stackoverflow.com/questions/6557805/randomize-a-php-array-with-a-seed
// http://bost.ocks.org/mike/algorithms/#shuffling
function Mersenne_Shuffle($arr, $seed=-1)
{
    if ( $seed == -1 ) return $arr;
    $mt = new Mersenne_Twister($seed);
    $new = $arr;
    for ($i = count($new) - 1; $i > 0; $i--)
    {
        $j = $mt->getNext(0,$i);
        $tmp = $new[$i];
        $new[$i] = $new[$j];
        $new[$j] = $tmp;
    }
    return $new;
}

Why PHP chose to break this in the name of progress I don’t understand. Ah well. Here is the workaround. If I need to acknowledge someone – let me know.