Pseudorandom generator in Assembly Language

Question

I need a pseudorandom number generator algorithm for a assembler program assigned in a course, and I would prefer a simple algorithm. However, I cannot use an external library.

What is a good, simple pseudorandom number generator algorithm for assembly?

Answer 1

Easy one is to just choose two big relative primes a and b, then keep multiplying your random number by a and adding b. Use the modulo operator to keep the low bits as your random number and keep the full value for the next iteration.

This algorithm is known as the linear congruential generator.

Answer 2

Volume 2 of The Art of Computer Programming has a lot of information about pseudorandom number generation. The algorithms are demonstrated in assembler, so you can see for yourself which are simplest in assembler.

If you can link to an external library or object file, though, that would be your best bet. Then you could link to, e.g., Mersenne Twister.

Note that most pseudorandom number generators are not safe for cryptography, so if you need secure random number generation, you need to look beyond the basic algorithms (and probably should tap into OS-specific crypto APIs).

Answer 3

Simple code for testing, don't use with Crypto

From Testing Computer Software, page 138

With is 32 bit maths, you don't need the operation MOD 2^32

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

Answer 4

Well - Since I haven't seen a reference to the good old Linear Feedback Shift Register I post some SSE intrinsic based C-Code. Just for completenes. I wrote that thing a couple of month ago to sharpen my SSE-skills again.

#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));
}

Translating this code to assembler is trivial. Just replace the intrinsics with the real SSE instructions and add a loop around it.

Btw - the sequence this code genreates repeats after 4.61169E+18 numbers. That's a lot more than you'll get via the prime method and 32 bit arithmetic. If unrolled it's faster as well.

Answer 5

@jjrv
What you're describing is actually a linear congrential generator. The most random bits are the highest bits. To get a number from 0..N-1 you multiply the full value by N (32 bits by 32 bits giving 64 bits) and use the high 32 bits.

You shouldn't just use any number for a (the multiplier for progressing from one full value to the next), the numbers recommended in Knuth (Table 1 section 3.3.4 TAOCP vol 2 1981) are 1812433253, 1566083941, 69069 and 1664525.

You can just pick any odd number for b. (the addition).

Answer 6

Why not use an external library??? That wheel has been invented a few hundred times, so why do it again?

If you need to implement an RNG yourself, do you need to produce numbers on demand -- i.e. are you implementing a rand() function -- or do you need to produce streams of random numbers -- e.g. for memory testing?

Do you need an RNG that is crypto-strength? How long does it have to go before it repeats? Do you have to absolutely, positively guarantee uniform distribution of all bits?

Here's simple hack I used several years ago. I was working in embedded and I needed to test RAM on power-up and I wanted really small, fast code and very little state, and I did this:

• Start with an arbitrary 4-byte constant for your seed.
• Compute the 32-bit CRC of those 4 bytes. That gives you the next 4 bytes
• Feed back those 4 bytes into the CRC32 algorithm, as if they had been appended. The CRC32 of those 8 bytes is the next value.
• Repeat as long as you want.

This takes very little code (although you need a table for the crc32 function) and has very little state, but the psuedorandom output stream has a very long cycle time before it repeats. Also, it doesn't require SSE on the processor. And assuming you have the CRC32 function handy, it's trivial to implement.

Answer 7

Using masm615 to compiler:

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 

Answer 8

also you probably can emulate shifting register with XOR sum elements between separate bits, which will give you pseudo-random sequence of numbers.

Answer 9

Linear congruential (X = AX+C mod M) PRNG's might be a good one to assign for an assembler course as your students will have to deal with carry bits for intermediate AX results over 2^31 and computing a modulus. If you are the student they are fairly straightforward to implement in assembler and may be what the lecturer had in mind.