⤴️ 🍩 🌞 Random Algorithms 👲🏿 🎹 👩‍❤️‍👩

In this article, you will see the most diverse ~~bike~~ algorithms for generating random numbers.

About what article

About algorithms generating pseudorandom numbers that differ in quality of result and speed of execution. The article will be useful to those who want to get high-performance number generation in their programs or developers of software for microcontrollers and old platforms like ZX Spectrum or MSX.

C ++ rand

The first thing a novice C ++ programmer learns about getting a random house is the rand function, which generates a random number between 0 and RAND_MAX. The RAND_MAX constant is described in the stdlib.h file and is 32'767, but this may not be the case, for example, on Linux ( see comment ). If rand () in your compiler generates numbers within 32'767 (0x7FFF) and you want to get a random number of large size, then the code below can be considered as a solution to this problem:

int64_t A = rand();
A <<= 15; //   15,   7FFF  15 
A |= rand();
A <<= 15;
A |= rand();
A <<= 15;
A |= rand();
A <<= 3;
A |= rand() & 0b111; //  3

The implementation of the rand function in old C was simple and looked like this:

static unsigned long int next = 1;

int rand()
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next / 65536) % 32768;
}

This implementation did not have a very good distribution of numbers and is now improved in C ++. Also, the standard C ++ library offers additional ways to get a random number, which are discussed below.

C ++ 11 STL random

This variety of randomness appeared in C ++ 11 and consists of the following set of classes: minstd_rand, mt19937, ranlux, knuth_b and their various variations.

To prevent the sequence of random numbers from repeating each time the program is started, the “grain” of the pseudo-random generator is specified in the form of the current time or, in the case of some retro (and not only) games, the intervals between keystrokes from the keyboard / joystick. The random library suggests using std :: random_device to get grain better than time (NULL), however, in the case of the MinGW compiler on Windows, the function practically does not work as it should. Still…

// ,   :
#include <random>
#include <ctime>

std::mt19937 engine; // mt19937    
engine.seed(std::time(nullptr));
/*
 ,    UNIX--    MinGW
std::random_device device;
engine.seed(device());
*/
int val = engine(); //

Some of the algorithms in STL random may work faster than rand (), but give a lower-quality sequence of random numbers.

PRNG - Pseudo-random Numbers Generator

You can consider this name a synonym for the linear congruent method. PRNG algorithms are similar to the rand implementation in C and differ only in constants.

unsigned PRNG()
{
  static unsigned seed = 1; //     0
  seed = (seed * 73129 + 95121) % 100000;
  return seed;
}

PRNG algorithms are fast and easy to implement in many languages, but do not have a large period.

Xorshift

The algorithm has many variations, differing from each other by the period and the registers used. Details and varieties of XorShift can be viewed on Wikipedia or Habré. I will give one of the options with a sequence of 2 in the 128th degree.

struct seed_t
{
  unsigned x = 1; //     
  unsigned y = 123;
  unsigned z = 456;
  unsigned w = 768;
};

unsigned XorShift128()
{
  static seed_t s;
  unsigned t = s.x^(s.x<<11);
  s.x = s.y;
  s.y = s.z;
  s.z = s.w;
  s.w = (s.w^(s.w>>19)) ^ (t^(t>>8));
  return s.w;
}

This generator is very good in that it does not have division and multiplication operations at all - this can be useful on processors and microcontrollers in which there are no assembler division / multiplication instructions (PIC16, Z80, 6502).

8-bit random in z26 emulator

Z26 is an emulator of an old Atari2600 prefix, in the code of which you can find a random one oriented to work with 1-byte registers.

// P2_sreg - static uint8_t
void P2_Read_Random()
{
  P2_sreg =
    (((((P2_sreg & 0x80) >> 7) ^
       ((P2_sreg & 0x20) >> 5)) ^
      (((P2_sreg & 0x10) >> 4) ^
       ((P2_sreg & 0x08) >> 3))) ^ 1) |
        (P2_sreg << 1);
  DataBus = P2_sreg;
}

Once I had to make an implementation of this algorithm for z80:

Assembly code

;    z26
; a - output
; rdseed - 1  
randz26:
    exx

    ld a,(rdseed)
    and 20h
    sra a
    sra a
    sra a
    sra a
    sra a
    ld h, a

    ld a,(rdseed)
    and 80h
    sra a
    sra a
    sra a
    sra a
    sra a
    sra a
    sra a
    xor h
    ld l, h
    
    ld a,(rdseed)
    and 08h
    sra a
    sra a
    sra a
    ld h, a

    ld a,(rdseed)
    and 10h
    sra a
    sra a
    sra a
    sra a
    xor h
    ld h, a
    ld a, l
    xor h
    xor 1

    ld h, a
    ld a,(rdseed)
    sla a
    or h
    ld (rdseed),a

    exx
    ret

Compact random for Z80 from Joe Wingbermuehle

If you are interested in writing programs for cars with zilog, then I present to your attention an algorithm from Joe Wingbermuehle (works only on zilog):

; By Joe Wingbermuehle
; a res 1 byte - out val
; rdseed res 1 byte - need for rand. != 0
rand8:
        exx
        ld      hl,(rdseed)
        ld      a,r
        ld      d,a
        ld      e,(hl)
        add     hl,de
        add     a,l
        xor     h
        ld      (rdseed),hl
        exx
        ret

Random House Generator in DOOM

In the source code of the game Doom there is such an interesting file called m_random.c (see code) , which describes the function of the “table” randomness, that is, there are no formulas and magic with bit shifts at all.

I’ll give a more compact code that clearly shows the operation of this function.

const uint8_t random_map[] =
{
  4,  1,   63, 3,
  64, 22,  54, 2,
  0,  52,  75, 34,
  89, 100, 23, 84
};

uint8_t get_random()
{
  static uint8_t index = 0;
  index = (index + 1) & 0xF; // 0xF,      random_map
  return random_map[index];
}

Varik for z80

;   (  DOOM)
; rand_table -    .  
;                        256    .
; a - output num
randtab:
    exx
    ; index
    ld a, (rdseed)
    inc a
    ;and filter ; for crop array index
    ld (rdseed), a
    ; calc array address
    ld hl, rand_table
    ld d, 0
    ld e, a
    add hl, de
    ld a, (hl) ; get num from arr
    exx
    ret

Of course, this is not random and the sequence of random numbers is easy to predict even at the level of intuition during the game, but it all works extremely quickly. If cryptographic strength is not particularly important to you and you want something that quickly generates “type-random”, then this function is for you. By the way, in Quake3, random looks simple - rand () & 0x7FFF.

RDRAND

Some modern processors are capable of generating random numbers with a single assembler instruction - RDRAND. To use this function in C ++, you can manually write the necessary instructions with assembler inserts or connect the immintrin.h file in GCC and select any of the variations of the _rdrandXX_step function, where XX means the number of bits in the register and can be 16, 32 or 64.

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

If you see a compilation error, it means that you did not enable the -mrdrnd flag or your compiler / processor does not support this tool. It may be the fastest random number generator, but there are questions about its cryptographic strength, so think about it.

Ending

The std :: minstd_rand class from the STL random library works faster than ordinary rand () and can become an alternative replacement if you are not particularly concerned about the length of the period in minstd. There may be differences in how these functions work on Windows and Unix.

Infa on the topic

An article about C ++ 11 random and some features of working with it: Random Number Generation in Modern C ++
What are the generators in STL random? exile
Wiki article about XorShift with different implementations: tyk
Git emulator z26. Random code in file c_pitfall2.c: git
Dumchik random generator: git

PS My first article. Write what is superfluous, what to add / reduce

Random Algorithms