Get best of the week

随机算法

在本文中，您将看到用于生成随机数的最多样化的自行车算法。

关于什么文章


关于生成伪随机数的算法，这些伪随机数的结果质量和执行速度不同。对于那些希望在其程序中获得高性能数字生成能力或希望为微控制器和旧平台（例如ZX Spectrum或MSX）开发软件的人来说，本文将非常有用。

C ++兰德


新手C ++程序员了解到的有关获得随机房屋的第一件事是rand函数，该函数生成介于0和RAND_MAX之间的随机数。RAND_MAX常量在stdlib.h文件中进行了描述，为32'767，但是，例如在Linux上，情况可能并非如此（请参见注释）。如果编译器中的rand（）生成32'767（0x7FFF）之内的数字，并且您希望获得一个大尺寸的随机数，则可以将以下代码视为此问题的解决方案：

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


在旧的C语言中，rand函数的实现很简单，如下所示：

static unsigned long int next = 1;

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

此实现没有很好的数字分布，现在在C ++中得到了改进。同样，标准C ++库提供了获取随机数的其他方法，下面将对此进行讨论。

C ++ 11 STL随机


这种随机性出现在C ++ 11中，由以下几类组成：minstd_rand，mt19937，ranlux，knuth_b及其各种变体。

为了防止每次启动程序时重复重复随机数序列，伪随机数发生器的“粒度”设置为当前时间，或者在某些复古游戏（且不仅限于游戏）的情况下，设置键盘/操纵杆两次击键之间的间隔。随机库建议使用std :: random_device来获得比时间（NULL）更好的粒度，但是，对于Windows上的MinGW编译器，该函数实际上无法正常工作。仍然…

// ,   :
#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(); //

STL random中的某些算法可能比rand（）更快，但是给出的随机数序列质量较低。

PRNG-伪随机数生成器


您可以将此名称视为线性一致方法的同义词。PRNG算法与C语言中的rand实现类似，仅在常量上有所不同。

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

PRNG算法快速且易于在多种语言中实现，但是周期不长。

Xorshift


该算法有很多变化，它们之间的区别在于周期和所使用的寄存器。XorShift的详细信息和品种可以在Wikipedia或Habré上查看。我将在128度中给出一个序列为2的选项之一。

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

该生成器非常好，因为它根本没有除法和乘法运算-这在没有汇编器除法/乘法指令（PIC16，Z80、6502）的处理器和微控制器中很有用。

z26仿真器中的8位随机


Z26是旧Atari2600前缀的仿真器，您可以在其代码中找到一个随机数，用于处理1字节寄存器。

// 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;
}

一旦我必须为z80实现此算法：

汇编代码
;    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


Joe Wingbermuehle的Z80紧凑型随机


如果您有兴趣编写带有zilog的汽车程序，那么请注意Joe Wingbermuehle的算法（仅适用于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

DOOM中的随机数生成器


在《毁灭战士》游戏的源代码中，有一个有趣的文件，称为m_random.c （请参见代码），该文件描述了“表格”随机性的功能，也就是说，根本没有公式和具有移位功能的魔术。

我将提供更紧凑的代码，以清楚地显示此功能的操作。

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


当然，这不是随机的，即使在游戏过程中凭直觉水平也很容易预测随机数的序列，但这一切都非常快。如果加密强度对您不是特别重要，并且您想要快速生成“类型随机”的东西，那么此功能适合您。顺便说一句，在Quake3中，随机看起来很简单-rand（）＆0x7FFF。

罗格朗德


一些现代处理器能够使用单个汇编程序指令RDRAND生成随机数。要在C ++中使用此功能，您可以在汇编器中手动编写必要的指令或在GCC中连接immintrin.h文件，然后选择_rdrandXX_step函数的任何变体，其中XX表示寄存器中的位数，可以为16、32或64。

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

如果看到编译错误，则表明您未启用-mrdrnd标志，或者您的编译器/处理器不支持此工具。它可能是最快的随机数生成器，但是对其加密强度存在疑问，因此请考虑一下。

结尾


STL随机库中的std :: minstd_rand类的运行速度比普通rand（）快，如果您不特别担心minstd中的时间长度，则可以替代该类。这些功能在Windows和Unix上的工作方式可能有所不同。

关于该主题的Infa


  • 有关C ++ 11 random以及使用它的一些功能的文章：现代C ++中的随机数生成
  • STL random中的生成器是什么？流亡
  • 有关XorShift具有不同实现的Wiki文章：tyk
  • Git模拟器z26。文件c_pitfall2.c中的随机代码：git
  • Dumchik随机生成器：git

PS我的第一篇文章。写出多余的东西，增加/减少什么

More articles:


All Articles