Generador pseudoaleatorio en lenguaje ensamblador

StackOverflow https://stackoverflow.com/questions/90184

  •  01-07-2019
  •  | 
  •  

Pregunta

Necesito un algoritmo generador de números pseudoaleatorios para un programa ensamblador asignado en un curso y preferiría un algoritmo simple.Sin embargo, no puedo utilizar una biblioteca externa.

¿Qué es un algoritmo generador de números pseudoaleatorios bueno y simple para ensamblaje?

¿Fue útil?

Solución

La más fácil es simplemente elegir dos primos relativos grandes a y b, luego seguir multiplicando tu número aleatorio por a y sumando b.Utilice el operador de módulo para mantener los bits bajos como número aleatorio y conservar el valor completo para la siguiente iteración.

Este algoritmo se conoce como generador congruencial lineal.

Otros consejos

Volumen 2 de El arte de la programación informática tiene mucha información sobre la generación de números pseudoaleatorios.Los algoritmos se demuestran en ensamblador, para que puedas comprobar por ti mismo cuáles son los más simples en ensamblador.

Sin embargo, si puede vincular a una biblioteca externa o a un archivo objeto, esa sería su mejor opción.Entonces podrías vincular a, por ejemplo, Tornado de Mersenne.

Tenga en cuenta que la mayoría de los generadores de números pseudoaleatorios son no seguro para la criptografía, por lo que si necesita una generación segura de números aleatorios, debe mirar más allá de los algoritmos básicos (y probablemente debería aprovechar las API criptográficas específicas del sistema operativo).

Código simple para pruebas, no lo use con Crypto

De Prueba de software informático, página 138

Con matemáticas de 32 bits, no necesitas la operación. MOD 2^32

RNG = (69069*RNG + 69069) MOD 2^32

Bueno, como no he visto una referencia al antiguo registro de desplazamiento de retroalimentación lineal, publico un código C basado en intrínseco de SSE.Sólo para completar.Escribí eso hace un par de meses para mejorar mis habilidades de ESS nuevamente.

#include <emmintrin.h>

static __m128i LFSR;

void InitRandom (int Seed)
{
  LFSR = _mm_cvtsi32_si128 (Seed);
}

int GetRandom (int NumBits)
{
  __m128i seed = LFSR;
  __m128i one  = _mm_cvtsi32_si128(1);
  __m128i mask; 
  int i;

  for (i=0; i<NumBits; i++)
  {

    // generate xor of adjecting bits
    __m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));

    // generate xor of feedback bits 5,6 and 62,61
    __m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
                                    _mm_srli_epi64(temp,61));

    // Mask out single bit: 
    NewBit = _mm_and_si128 (NewBit, one);

    // Shift & insert new result bit:
    seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
  }

  // Write back seed...
  LFSR = seed;

  // generate mask of NumBit ones.
  mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);

  // return random number:
  return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}

Traducir este código a ensamblador es trivial.Simplemente reemplace los intrínsecos con las instrucciones SSE reales y agregue un bucle alrededor.

Por cierto, la secuencia que genera este código se repite después de 4.61169E+18 números.Eso es mucho más de lo que obtendrás mediante el método principal y la aritmética de 32 bits.Si se desenrolla también es más rápido.

@jjrv
Lo que estás describiendo es en realidad un generador congresal lineal.Los bits más aleatorios son los bits más altos.Para obtener un número de 0..N-1, multiplica el valor completo por N (32 bits por 32 bits, lo que da 64 bits) y usa los 32 bits superiores.

No deberías usar cualquier número para a (el multiplicador para pasar de un valor completo al siguiente), los números recomendados en Knuth (Tabla 1 sección 3.3.4 TAOCP vol 2 1981) son 1812433253, 1566083941, 69069 y 1664525.

Puedes elegir cualquier número impar para b.(la adicion).

¿Por qué no utilizar una biblioteca externa?Esa rueda se ha inventado cientos de veces, así que ¿por qué volver a inventarla?

Si necesita implementar un RNG usted mismo, ¿necesita producir números a pedido, es decir?¿Está implementando una función rand() o necesita producir secuencias de números aleatorios?para pruebas de memoria?

¿Necesita un RNG que tenga potencia criptográfica?¿Cuánto tiempo tiene que pasar antes de que se repita?¿Es necesario garantizar absoluta y positivamente una distribución uniforme de todos los bits?

Aquí hay un truco simple que utilicé hace varios años.Estaba trabajando en modo integrado y necesitaba probar la RAM al encender y quería un código realmente pequeño y rápido y muy poco estado, e hice esto:

  • Comience con una constante arbitraria de 4 bytes para su semilla.
  • Calcule el CRC de 32 bits de esos 4 bytes.Eso te da los siguientes 4 bytes.
  • Vuelva a introducir esos 4 bytes en el algoritmo CRC32, como si se hubieran añadido.El CRC32 de esos 8 bytes es el siguiente valor.
  • Repite todo el tiempo que quieras.

Esto requiere muy poco código (aunque necesita una tabla para la función crc32) y tiene muy poco estado, pero el flujo de salida pseudoaleatorio tiene un tiempo de ciclo muy largo antes de repetirse.Además, no requiere SSE en el procesador.Y suponiendo que tenga la función CRC32 a mano, es trivial de implementar.

Usando masm615 para compilar:

delay_function macro
    mov cx,0ffffh
.repeat
    push cx
    mov cx,0f00h
    .repeat
        dec  cx
        .until cx==0
    pop cx
    dec cx
    .until cx==0
endm

random_num macro
   mov  cx,64    ;assum we want to get 64 random numbers
   mov  si,0

get_num:    
   push cx
   delay_function    ;since cpu clock is fast,so we use delay_function
   mov  ah,2ch  
   int  21h
   mov  ax,dx     ;get clock 1/100 sec
   div  num       ;assume we want to get a number from 0~num-1
   mov  arry[si],ah   ;save to array you set
   inc  si
   pop  cx
   loop get_num   ;here we finish the get_random number

También es probable que puedas emular el registro de desplazamiento con elementos de suma XOR entre bits separados, lo que te dará una secuencia pseudoaleatoria de números.

Los PRNG lineales congruentes (X = AX+C mod M) podrían ser buenos para asignar a un curso de ensamblador, ya que sus estudiantes tendrán que lidiar con bits de acarreo para resultados intermedios de AX superiores a 2^31 y calcular un módulo.Si usted es el estudiante, son bastante sencillos de implementar en ensamblador y pueden ser lo que el profesor tenía en mente.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top