1
\$\begingroup\$

This should be relatively simple, but I want to know if I've done the randomness bit correctly.

<?php
function seeded_shuffle(array &$input, int $seed) {
    $rand = function($max) use (&$seed, &$rand) {
        static $rng_a = 0x41C64E6D;
        static $rng_c = 0x00006073;
        // rng_m = 2^32
        // c is odd => m and c are coprime
        // a is odd => a-1 is divisible by all prime factors of m (ie. 2)
        // m%4 = 0 and (a-1)%4 = 0
        // Therefore this is an LCRNG with a full period.

        $seed = ($rng_a * $seed + $rng_c) & 0xFFFFFFFF;
        $mod = $max + 1;
        // Modulo might not divide 2^32, so if it's too high then re-roll
        if( intdiv($seed,$mod) >= intdiv(1<<32,$mod)) {
            return $rand($max); // seed has advanced
        }
        return $seed % $mod;
    };

    // Fisher-Yates shuffle
    for( $i=count($input)-1; $i>0; $i--) {
        $j = $rand($i);
        list($array[$i],$array[$j]) = [$array[$j],$array[$i]];
    }
}

My main concern is that "Modulo might not divide 2^32" bit. I'm trying to avoid modulo bias, but is just re-rolling until we're not in the top-end range good enough?

(Just in case it's relevant, the length of $input is 18 in this use case)

\$\endgroup\$
  • \$\begingroup\$ I'm not too familiar with PHP, but if you "bitwise and" a random number with 0xFFFFFFFF, is it not guaranteed to be a number within 32 bits? \$\endgroup\$ – Neil Jul 19 '17 at 14:12
  • \$\begingroup\$ @Neil That's the "modulo 2^32" part of the LCRNG. \$\endgroup\$ – Niet the Dark Absol Jul 19 '17 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.