###### tags: `math` `rng` `Public`
# Fast RNG 的數學原理

取代模數運算(Mod)的快速替代方案

## 目的
我們有生成隨機 32 位整數$[0,2^{32}-1]$的亂數產生器，
如何取得N元素中隨機選取一個整數？

graph LR;
a["x(0,1,2,...,4294967295)"]--"映射方式A(取餘數)"-->b["N(0,1,2...N)"]
a--"映射方式B(擴容後相乘後再移位)"-->b

## N屬於2的冪次(N=2,4,8,16,...)
可以藉由位元位移快速取得精確的解

## Mod模數減少$Xmod(N)$

uint32_t reduce(uint32_t x, uint32_t N) {
  return x % N;
}

將亂數產生器產生的隨機量RNG對我們所求的N取餘數。
在範圍內，可視為一個公平的映射。

### 特點
* 當N不是2的冪次時，會有偏誤(Bias)
* N與$2^{32}-1$的數量級越接近，偏誤(Bias)越大
* 使用方法為除法，除法是很昂貴的的算法，比乘法貴很多

## 快速替代方案 擴容乘積法 $(X\times N)/2^{32}$

uint32_t reduce(uint32_t x, uint32_t N) {
  return ((uint64_t) x * (uint64_t) N) >> 32 ;
}

假設x和N是 32 位整數，請考慮 64 位乘積x * N。你有$(X\times N)/2^{32}$。
與模數減少法一樣在範圍內，可視為一個公平的映射。

### 特點
* 當N不是2的冪次時，會有偏誤(Bias)
* N與$2^{32}-1$的數量級越接近，偏誤(Bias)越大
* 使用方法為乘法與位元運算

## 效能比較

### CPU 週期數
模數減少法|擴容乘積法
---|---
modulo reduction|fast range
8.1|2.2

兩者相比，擴容乘積法快了四倍！

## 參考
1. github.com/valyala/fastrand
2. https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/