Generando números aleatorios o permutaciones de período completo/ciclo completo Similar a LCG pero sin impar/par

Question

Deseo generar números/permutaciones psuedo-aleatorios que 'ocupen' un período completo o un ciclo completo dentro de un rango. Por lo general, un 'Linear congruential Generador' (LCG) se puede utilizar para generar tales secuencias, utilizando una fórmula como:

X = (a*Xs+c) Mod R 

Donde X es la semilla, X es el resultado, a y c son constantes relativamente primos y R es el máximo (rango).

(Por período completo/ciclo completo, quiero decir que las constantes se pueden elegir para que cualquier X ocurra solo una vez en alguna secuencia aleatoria/permutada y estará dentro del rango de 0 a R-1 o 1 a R)

LCG casi cumple con todas mis necesidades. El problema que tengo con LCG es la no aleatoriedad del resultado impar/par, es decir: para una semilla Xn, el resultado X se alternará impar/par.

Preguntas:

1. ¿Alguien sabe cómo crear algo similar que no alternativo par/impar?

2. Creo que se podría construir un 'Compuesto LCG' , pero no tengo detalles de . ¿Alguien puede dar un ejemplo de este CLCG?

3. ¿Hay fórmulas alternativas que pueden cumplir con los detalles anteriores y restricciones a continuación?

Restricciones:

4. quiero algo basado en una simple fórmula a base de semillas de . es decir: para obtener el siguiente número , proporciono la semilla y obtengo el siguiente 'número aleatorio' en la secuencia permutada. Específicamente, No puedo usar matrices precalculadas. (ver siguiente puntos)
5. La secuencia absolutamente tiene que ser 'período completo/ciclo completo'
6. El rango R podría ser de varios millones de o incluso de 32 bits/4 mil millones.

7. El cálculo no debe sufrir desbordamiento y ser eficiente/rápido, es decir: sin exponentes grandes o docenas de multiplicaciones/divisiones.

8. La secuencia no tiene que ser terriblemente aleatoria o segura: no necesito aleatoriedad criptográfica (pero puedo usarla si es viable), solo aleatoriedad "buena" o aleatoriedad aparente, sin secuencias impares/pares.

Cualquier pensamiento apreciado, gracias de antemano.

ACTUALIZACIÓN: Idealmente, la variable de rango puede no ser una potencia exacta de dos, pero debería funcionar en cualquier caso.

Answer 1

Si su único problema es la alternancia par/impar, deje sin cambios el cálculo de cambio de estado.Antes de usar cada salida, puede desplazar los bits inferiores o intercambiarlos.

Editar:

Con la variante de intercambio de bits (patrón fijo), se mantendrá la generación de períodos enteros.

pseudo-código de LCG inicial:

function rand 
    state := update(state) 
    return state 

pseudo-código de LCG incluyendo intercambio:

function rand2 
    state := update(state) -- unchanged state computation 
    return swapped(state) -- output swapped state 

Answer 2

Otra PRNG fácil, eficiente y bien entendido es un Linear Feedback Shift Register. El período completo es fácil de lograr siguiendo los pasos del artículo.

EDIT:

podría considerar algunas de las técnicas desarrolladas para Format-Preserving Encryption. Creo que estos pueden adaptarse fácilmente para generar una permutación.

Answer 3

En el siguiente enlace puede encontrar un ejemplo de LCG combinado. (Documentos y fuentes incluidas) (Nota: algoritmo es abierta, pero la licencia de la fuente no está abierto (es decir, ningún código derivado))

http://resource.npl.co.uk/docs/science_technology/scientific_computing/ssfm/documents/wh_rng_version096.zip

Puede ser que incluso probar este ejemplo 7 etapas XORshift RNG :

https://gist.github.com/709285

Answer 4

solución trivial. Haga un LCG con R un primo algo más grande que el rango que desea, y ambos a y c en algún lugar al azar en ese rango. Si te da un número que es más grande de lo que deseas, itera de nuevo hasta que estés nuevamente dentro del rango.

Los números de salida no tendrán un patrón de patrón 2, 3, 5, etc. particularmente simple hasta cualquier primo menor que el primo que use.

Si el rango que desea es grande, la prima más grande más cercana solo será una cantidad pequeña más grande, por lo que muy raramente necesitará llamarla dos veces. Por ejemplo, si su rango deseado es mil millones, puede usar 1000000007 como su principal, y deberá omitir un número adicional inferior al 0,000001% del tiempo.

Encontré este número yendo al http://primes.utm.edu/curios/includes/primetest.php y poniendo números hasta que obtuve un buen momento. Tuve un poco de suerte. Las probabilidades de que n terminen en 1, 3, 7, 9 son aproximadamente 2.5/log(n) que en mil millones son aproximadamente 12%, así que tuve suerte de encontrar este número después de solo 4 intentos. Pero no tan afortunado, lo encontré en 3 intentos y en promedio debería haberlo necesitado 8.

EDIT: Este generador de números aleatorios puede tener un ciclo más corto. Ver la nota de @dzugaru.

Answer 5

El hecho de que no necesite fuerza criptográfica no significa que no pueda tomar prestadas algunas ideas de la criptografía ... Como la red Feistel (construcción de Luby-Rackoff).

El Wikipedia picture es bastante claro.

Si selecciona una F sencilla y rápida, ni siquiera necesita garantizar una salida única, puede alimentar una secuencia (0, 1, 2, ..., 2^n-1) a algunas rondas de la red Feistel. Dado que la construcción es reversible, esto garantiza que la salida nunca se repita.

Código de ejemplo para 32 bits:

#include <stdint.h> 
#include <stdio.h> 

/* Just some fixed "random" bits... */ 
union magic { 
    double d; 
    uint16_t n[4]; 
}; 

const union magic bits = { 3.141592653589793238462643383 }; 

static uint16_t 
F(uint16_t k, uint16_t x) 
{ 
    return 12345*x + k; 
} 

static uint32_t 
gen_rand(uint32_t n) 
{ 
    uint16_t left = n >> 16; 
    uint16_t right = n & ((1UL << 16) - 1); 

    for (unsigned round=0 ; round < 4 ; ++round) { 
     const uint16_t next_right = left^F(bits.n[round], right); 
     const uint16_t next_left = right; 
     right = next_right; 
     left = next_left; 
    } 

    return (((uint32_t)left) << 16) + right; 
} 

int 
main(int argc, char *argv[]) 
{ 
    for (uint32_t n = 0 ; n < 10 ; ++n) { 
     printf("gen_rand(%lu) == %08lx\n", (unsigned long)n, 
       (unsigned long)gen_rand(n)); 
    } 
    return 0; 
} 

Usted puede perder el tiempo con la definición de F(), el número de rondas, etc., para adaptarse a su gusto. La propiedad de "ciclo completo" está garantizada sin importar lo que use allí. En otras palabras, si tiene el bucle en main vaya de 0 a 2^32-1, cada entero de 32 bits ocurrirá una vez y solo una vez, independientemente de lo que use para F o el número de rondas.

Esto no cumple exactamente con su requisito establecido, ya que la entrada a gen_rand no es el "número aleatorio actual" ... La entrada es solo el siguiente entero. Sin embargo, esto te permite generar cualquier elemento de la secuencia a voluntad (acceso aleatorio). Y es fácil invertirlo si realmente desea pasar el "número aleatorio actual" como entrada.

Bastante fácil de adaptar a diferentes números de bits, aunque sí requiere que el R es una potencia de 2.

Answer 6

generadores congruentes permutados parecen tener todas las cualidades que buscas:

http://www.pcg-random.org

// *Really* minimal PCG32 code/(c) 2014 M.E. O'Neill/pcg-random.org 
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) 

typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t; 

uint32_t pcg32_random_r(pcg32_random_t* rng) 
{ 
    uint64_t oldstate = rng->state; 
    // Advance internal state 
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1); 
    // Calculate output function (XSH RR), uses old state for max ILP 
    uint32_t xorshifted = ((oldstate >> 18u)^oldstate) >> 27u; 
    uint32_t rot = oldstate >> 59u; 
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31)); 
} 

Hay otras variedades disponibles en el sitio web, incluyendo una implementación en C++ la intención de trabajar con el encabezado <random> (por ejemplo, las distribuciones), una más completa C implantar mecanismos ion, y una implementación de Haskell.