C Objetivo: Modulo sesgo

Question

Usando

value = arc4random() % x 

¿Cómo puedo evitar o eliminar el sesgo de módulo?

Gracias a todos.

Por cierto, al menos según Wikipedia, el sesgo del módulo es un problema cuando se programan juegos de azar .

Answer 1

arc4random devuelve un entero sin signo de 32 bits (0 a 2 -1).

Probablemente no habrá un sesgo de módulo notable para una x suficientemente pequeña. Sin embargo, si quieres estar realmente seguro, haga lo siguiente:

y = 2 ^p donde 2 ^p-1 < x ≤ 2 ^p

val = arc4random() % y; 
while(val >= x) 
    val = arc4random() % y; 

Answer 2

Si el valor máximo de arc4random mod x es mayor que x, ignore cualquier valor mayor que el arc4random-max mod x más grande, llamando al arc4random nuevamente.

Answer 3

u_int32_t maxValue = ~((u_int32_t) 0);  // equal to 0xffff... 
maxValue -= maxValue % x;     // make maxValue a multiple of x 
while((value = arc4random()) >= maxValue) { // loop until we get 0 ≤ value < maxValue 
} 
value %= x; 

aunque menos que esté utilizando cualquier x menos de un millón (o más) yo no me preocuparía por eso

Answer 4

u_int32_t maxValue = ~((u_int32_t) 0);  // equal to 0xffff... 
maxValue -= maxValue % x;     // make maxValue a multiple of x 
while((value = arc4random()) >= maxValue) { // loop until we get 0 ≤ value < maxValue 
} 
value %= x; 

objeción Un poco pedante a la respuesta de cobbal. "Funciona", es decir, elimina el sesgo del módulo, pero rechaza más valores de los necesarios. El caso más extremo es x = 2^31. Todos los valores de arc4random() deberían aceptarse aquí, pero el código tal como está escrito rechazará la mitad de ellos.

En su lugar, agregue 1 a la inicialización de maxValue (que lo pone en 2^32 por lo que tendrá que usar un int de 64 bits), y luego está bien. También puede evitar el uso de un int de 64 bits. Pruebe de antemano si 2^32% x == 0, si es así, todos los valores de arc4random() son aceptables y puede omitir el bucle; de ​​lo contrario, puede mantener maxValue en 32 bits restando 2^32% x en la inicialización.

Answer 5

Use arc4random_uniform(x). Esto lo hace por ti.

Según la página hombre:

arc4random_uniform() devolverá un número aleatorio distribuido uniformemente menos de upper_bound. arc4random_uniform() se recomienda en construcciones como arc4random() % upper_bound ya que evita el "sesgo de módulo" cuando el límite superior no es una potencia de dos.

Answer 6

Utilice el siguiente método. Evita el "sesgo de módulo" y es rápido en iphone. Ahorre algunos ciclos de CPU.

SI usted quiere 4-7:

(random()/(float)RAND_MAX)*3+4 

o si desea 0-8

(random()/(float)RAND_MAX)+8