Conserver une distribution uniforme après le remappage vers une nouvelle plage

Puisqu'il s'agit de remapper une distribution uniforme à une autre avec une plage différente, ce n'est pas une question PHP spécifiquement bien que j'utilise PHP.Conserver une distribution uniforme après le remappage vers une nouvelle plage

J'ai un générateur de nombres aléatoires sécurisé cryptographiquement qui me donne des nombres entiers répartis uniformément (distribution discrète uniforme) entre 0 et PHP_INT_MAX.

Comment remapper ces résultats pour les adapter à une plage différente d'une manière efficace?

Actuellement, je me sers $mappedRandomNumber = $randomNumber % ($range + 1) + $min où $range = $max - $min, mais que le travail ne obvioulsy pas depuis les premiers PHP_INT_MAX%$range entiers de la gamme ont une plus grande chance d'être choisi, rompant l'uniformité de la distribution.

Source

2015-03-25 NotGaeL

Eh bien, ayant zéro connaissance de PHP me qualifie certainement comme un expert, si

convertir mentalement flotter U [0,1)

f = r/PHP_MAX_INT

faire alors

mapped = min + f*(max - min)

aller retour aux nombres entiers

mapped = min + (r * max - r * min)/PHP_MAX_INT

si le calcul est fait par maths 64bit, et PHP_MAX_INT étant 2^31 cela devrait fonctionner

Source

2015-03-25 16:59:40

Merci pour la réponse, mais je suis tout peur impliquant des flotteurs entraînera des problèmes en raison de problèmes de représentation flottante des points et des erreurs d'arrondi. En outre, l'utilisation de maths 64 bits implique PHP_INT_MAX = 2^63 - 1, donc il y a aussi le problème de débordement. – NotGaeL

Non, par rapport à float j'ai spécifiquement dit mentalement, l'expression finale est tout entier. Wrt 'En outre, en utilisant 64 bits mathématiques implique PHP_INT_MAX = 2^63 - 1, donc il y a aussi le problème de débordement», pourriez-vous utiliser maths 64 bits seulement pour les intermédiaires? Encore une fois, je n'ai aucune idée à propos de PHP, mais je ne fais que calculer en accolades avec des maths 64 bits, et ensuite la division devrait fonctionner. –

ouais mais vous pouvez voir (max-min)/PHP_INT_MAX sera toujours un float et il n'y a pas d'autre moyen de faire le calcul sans débordement (faire 'r * (max - min)' premier débordera dans tous les cas, mais trivial) – NotGaeL

C'est ce que j'ai fini par faire. PRNG 101 (s'il ne rentre pas, ignore et génère de nouveau). Pas très sophistiqué, mais simple:

public function rand($min = 0, $max = null){ 

    // pow(2,$numBits-1) calculated as (pow(2,$numBits-2)-1) + pow(2,$numBits-2) 
    // to avoid overflow when $numBits is the number of bits of PHP_INT_MAX 
    $maxSafe = (int) floor(
    ((pow(2,8*$this->intByteCount-2)-1) + pow(2,8*$this->intByteCount-2)) 
    /
    ($max - $min) 
) * ($max - $min); 

    // discards anything above the last interval N * {0 .. max - min -1} 
    // that fits in {0 .. 2^(intBitCount-1)-1} 
    do { 
    $chars = $this->getRandomBytesString($this->intByteCount); 
    $n = 0; 
    for ($i=0;$i<$this->intByteCount;$i++) {$n|=(ord($chars[$i])<<(8*($this->intByteCount-$i-1)));} 
    } while (abs($n)>$maxSafe); 

    return (abs($n)%($max-$min+1))+$min; 

}

Toutes les améliorations sont les bienvenues.

(code complet sur https://github.com/elcodedocle/cryptosecureprng/blob/master/CryptoSecurePRNG.php)

Source

2015-03-28 17:38:23 NotGaeL

Conserver une distribution uniforme après le remappage vers une nouvelle plage

Répondre

Questions connexes