Pseudo random generator, Assembler

Question

Which "random" numbers generator algorithm is the best for an assembler program? Something easy, not a long piece of code.

Not external library allowed, just trying to keep it simple.

@Bill Barksdale: I'm looking for an easy algorithm to use in a assembler program assigned in a course.

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

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

Answer 3

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 4

Can you explain what this is for? Crypto, games, and randomized algorithms really have different requirements and tradeoffs.

Answer 5

Simple code for testing, dont use with Crypto

From Testing Computer Software, page 138

With is 32 bit maths, you dont need MOD 2^32

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

Answer 6

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.

Answer 7

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 8

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.