C基礎尋找隨機函數的G點詳解

2020-01-26 14:33:32

字體：大中小

來源：轉載

供稿：網友

引言

隨機函數算法應該是計算機史上最重要的十大算法之一吧. 而C中使用的隨機函數

#include <stdlib.h>_Check_return_ _ACRTIMP int __cdecl rand(void);

本文主要圍繞rand 函數找到G點. 就是偽隨機函數的周期值.

關于rand 源碼, 可以從Linux底層源碼 glibc中找. 看了一下大約4個文件. 算法比較復雜. 感覺很穩定.

這里不探討隨機算法的實現. 只為了找到隨機函數周期.

前言

現在window上測試. 測試代碼 main.c

#include <stdio.h>#include <stdlib.h>#define _INT_R    (128)#define _INT_FZ    (10000000)// 得到rand() 返回值, 并寫入到文件中int getrand(long long *pcut) {  static int _cut = 0;  long long t = *pcut + 1;  int r = rand();    // 每次到萬再提醒一下  if(t % _INT_FZ == 0)    fprintf(stdout, "%d 個數據跑完了[%d, %lld]/n", _INT_FZ, _cut, t);    if(t < 0) { // 數據超標了    ++_cut;    fprintf(stderr, "Now %d T > %lld/n", _cut, t - 1);    *pcut = 0; // 重新開始一輪  }    *pcut = t;  return r;}/* * 驗證 rand 函數的周期 */int main(int argc, char* argv[]) {  int rbase[_INT_R];  int i = -1, r;  long long cut = 0;    // 先產生隨機函數  while(++i < _INT_R)    rbase[i] = getrand(&cut);    // 這里開始隨機了  for(;;) {    r = getrand(&cut);    if (r != rbase[0])      continue;    for(i=1; i<_INT_R; ++i) {      r = getrand(&cut);      if(r != rbase[i])         break;    }        // 找見了數據    if(i == _INT_R) {      printf("Now T = %lld/n", cut);      break;    }  }    system("pause");  return 0;}

主要思路是 _INT_R 128個數重疊那我們就認為. 已經找到這個周期了.

測試結果截圖是

主要采用 Release X64 編譯. 為了檢驗上面結果是可以接受的, 將 _INT_R 改成1024 重新編譯一次.

運行結果如下：

綜合上面我們找見了 window 上 rand 函數的 G點是

2147483776 - 128 = 214748248

2147484672 - 1024 = 2147483648

因而得到 window 上 VS2015 編譯器的 rand G點是 2147483648.

G點在游戲中用的很多. 例如抽獎, 掉裝備, 暴擊等等.

正文

1. 在linux 上試試水

在linux上試試測試代碼基本一樣 rand2.c 如下

#include <stdio.h>#include <stdlib.h>#define _INT_R    (1024)#define _INT_FZ    (100000000)// 得到rand() 返回值, 并寫入到文件中int getrand(long long *pcut) {  static int _cut = 0;  long long t = *pcut + 1;  int r = rand();    // 每次到萬再提醒一下  if(t % _INT_FZ == 0)    fprintf(stdout, "%d個數據又跑完了[%d, %lld]/n", _INT_FZ, _cut, t);    if(t < 0) { // 數據超標了    ++_cut;    fprintf(stderr, "Now %d T > %lld/n", _cut, t - 1);    *pcut = 0; // 重新開始一輪  }    *pcut = t;  return r;}/* * 驗證 rand 函數的周期 */int main(int argc, char* argv[]) {  int rbase[_INT_R];  int i = -1, r;  long long cut = 0;    // 先產生隨機函數  while(++i < _INT_R)    rbase[i] = getrand(&cut);    // 這里開始隨機了  for(;;) {    r = getrand(&cut);    if (r != rbase[0])      continue;    for(i=1; i<_INT_R; ++i) {      r = getrand(&cut);      if(r != rbase[i])         break;    }        // 找見了數據    if(i == _INT_R) {      printf("Now T = %lld/n", cut);      break;    }  }    return 0;}

編譯命令

gcc -03 -o randc2.out rand2.c

最后運行結果, 等了好久還是沒出來.

Linux 上的rand 函數寫的很有水準, 分布的很隨機. 總而言之這個隨機值比較大. 但一定存在的.

有興趣的可以按照上面思路優化跑一跑. 這邊Ubuntu 是虛擬機跑的慢.

2. 繼續擴展, 減小rand 返回 MAX值試試水

修改上面 getrand 函數

// _INT_RMAX 表示隨機數范圍 [0, 100)#define _INT_RMAX  (100)#define _INT_R    (1024)#define _INT_FZ    (10000000)// 得到rand() 返回值, 并寫入到文件中int getrand(long long *pcut) {  static int _cut = 0;  long long t = *pcut + 1;  int r = rand() % _INT_RMAX;  // 每次到萬再提醒一下  if (t % _INT_FZ == 0)    fprintf(stdout, "%d 個數據跑完了[%d, %lld]/n", _INT_FZ, _cut, t);  if (t < 0) { // 數據超標了    ++_cut;    fprintf(stderr, "Now %d T > %lld/n", _cut, t - 1);    *pcut = 0; // 重新開始一輪  }  *pcut = t;  return r;}

添加了取余看是否, 影響G點測試結果

發現G點沒有變化.

可以有推論: rand() 周期不隨著二次 mod取余而改變.

因而可以放心 mod使用偽隨機函數. G點還是那么大.

3. 最后, 贈送一個常用的 [min, max] 之間的隨機函數

/* * 返回 [min, max] 區間的隨機函數 * min  : 起始位置 * max  : 結束位置 *    : 返回[min, max]區間之內的位置 */extern int random(int min, int max);/* * 返回 [min, max] 區間的隨機函數 * min  : 起始位置 * max  : 結束位置 *    : 返回[min, max]區間之內的位置 */int random(int min, int max) {  assert(min < max);  // 正常情況  return rand() % (max - min + 1) + min;}

測試demo 代碼結構如下

#include <stdio.h>#include <stdlib.h>#include <time.h>#include <assert.h>/* * 返回 [min, max] 區間的隨機函數 * min  : 起始位置 * max  : 結束位置 *    : 返回[min, max]區間之內的位置 */extern int random(int min, int max);/* * C 基礎, 使用隨機函數 */int main(int argc, char* argv[]) {  int min = -5, max = 5;  int i = 0;  // 開始統一 初始化種子  srand((unsigned)time(NULL));  while(i < 100) {    printf("%3d ", random(min, max));    if (++i % 10 == 0)      putchar('/n');  }  system("pause");  return 0;}/* * 返回 [min, max] 區間的隨機函數 * min  : 起始位置 * max  : 結束位置 *    : 返回[min, max]區間之內的位置 */int random(int min, int max) {  assert(min < max);  // 正常情況  return rand() % (max - min + 1) + min;}

測試結果是