php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #40114 mt_srand() generates the same sequences with consecutive seeds
Submitted: 2007-01-12 21:29 UTC Modified: 2007-01-13 16:42 UTC
From: Pedro Gimeno <phpbugs at personal dot formauri dot Assigned:
Status: Closed Package: Math related
PHP Version: 5.2.0 OS: any
Private report: No CVE-ID: None
 [2007-01-12 21:29 UTC] Pedro Gimeno <phpbugs at personal dot formauri dot
Description:
------------
When calling mt_srand with seed 0, the resulting sequence is the same as with seed 1; when calling it with seed 2, the sequence is the same as with seed 3, etc., generating the same sequences for even numbers as for these numbers + 1.

The problem seems to come from this line:

register php_uint32 x = (seed | 1U) & 0xFFFFFFFFU, *s = BG(state);

The | 1U is apparently there to force the seed being odd, due to the fact that the initialization uses a pure multiplicative linear-congruential generator. Replacing the line:

  *s++ = (x *= 69069U) & 0xFFFFFFFFU);

with e.g.:

  *s++ = (x *= 69069U, ++x) & 0xFFFFFFFFU);

should eliminate the requirement that the seed be odd. The generator X <- (X*69069+1) mod 2**32 is the 'VAX generator', has decent short-term randomness properties and works fairly well for this purpose (Wikipedia's article about MT uses it). The pure multiplicative X <- (X*69069) mod 2**32 is not so well studied and does not work well with all seeds. The seeding requirements of MT are just that not all elements are zero, which is guaranteed in this case.

However, please consider using e.g. the algorithm in init_genrand() in <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c> instead. See justification in <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html>.


Reproduce code:
---------------
<?php
  for ($i = 0; $i < 10; $i++) {
    mt_srand($i);
    echo mt_rand(0, mt_getrandmax()), ", ",
         mt_rand(0, mt_getrandmax()), "\n";
  }
?>


Expected result:
----------------
All lines different.


Actual result:
--------------
Lines are equal by pairs.


Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2007-01-13 16:42 UTC] iliaa@php.net
This bug has been fixed in CVS.

Snapshots of the sources are packaged every three hours; this change
will be in the next snapshot. You can grab the snapshot at
http://snaps.php.net/.
 
Thank you for the report, and for helping us make PHP better.

This issues appears to have already been resolved. With latest 
CVS each line is different.
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Fri Mar 29 13:01:29 2024 UTC