C基礎(chǔ) 尋找隨機函數(shù)的G點詳解

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C語言|點擊：次

引言

隨機函數(shù)算法應(yīng)該是計算機史上最重要的十大算法之一吧. 而C中使用的隨機函數(shù)

#include <stdlib.h>

_Check_return_ _ACRTIMP int __cdecl rand(void);

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

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

這里不探討隨機算法的實現(xiàn). 只為了找到隨機函數(shù)周期.

前言

現(xiàn)在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 個數(shù)據(jù)跑完了[%d, %lld]\n", _INT_FZ, _cut, t);
  
  if(t < 0) { // 數(shù)據(jù)超標(biāo)了
    ++_cut;
    fprintf(stderr, "Now %d T > %lld\n", _cut, t - 1);
    *pcut = 0; // 重新開始一輪
  }
  
  *pcut = t;
  return r;
}

/*
 * 驗證 rand 函數(shù)的周期
 */
int main(int argc, char* argv[]) {
  int rbase[_INT_R];
  int i = -1, r;
  long long cut = 0;

  
  // 先產(chǎn)生隨機函數(shù)
  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;
    }
    
    // 找見了數(shù)據(jù)
    if(i == _INT_R) {
      printf("Now T = %lld\n", cut);
      break;
    }
  }
  
  system("pause");
  return 0;
}

主要思路是 _INT_R 128個數(shù)重疊那我們就認為. 已經(jīng)找到這個周期了.

測試結(jié)果截圖是

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

運行結(jié)果如下：

綜合上面我們找見了 window 上 rand 函數(shù)的 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個數(shù)據(jù)又跑完了[%d, %lld]\n", _INT_FZ, _cut, t);
  
  if(t < 0) { // 數(shù)據(jù)超標(biāo)了
    ++_cut;
    fprintf(stderr, "Now %d T > %lld\n", _cut, t - 1);
    *pcut = 0; // 重新開始一輪
  }
  
  *pcut = t;
  return r;
}

/*
 * 驗證 rand 函數(shù)的周期
 */
int main(int argc, char* argv[]) {
  int rbase[_INT_R];
  int i = -1, r;
  long long cut = 0;

  
  // 先產(chǎn)生隨機函數(shù)
  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;
    }
    
    // 找見了數(shù)據(jù)
    if(i == _INT_R) {
      printf("Now T = %lld\n", cut);
      break;
    }
  }
  
  return 0;
}

編譯命令

gcc -03 -o randc2.out rand2.c

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

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

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

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

修改上面 getrand 函數(shù)

// _INT_RMAX 表示隨機數(shù)范圍 [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 個數(shù)據(jù)跑完了[%d, %lld]\n", _INT_FZ, _cut, t);

  if (t < 0) { // 數(shù)據(jù)超標(biāo)了
    ++_cut;
    fprintf(stderr, "Now %d T > %lld\n", _cut, t - 1);
    *pcut = 0; // 重新開始一輪
  }

  *pcut = t;
  return r;
}

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

發(fā)現(xiàn)G點沒有變化.

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

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

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

/*
 * 返回 [min, max] 區(qū)間的隨機函數(shù)
 * min  : 起始位置
 * max  : 結(jié)束位置
 *    : 返回[min, max]區(qū)間之內(nèi)的位置
 */
extern int random(int min, int max);

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

測試demo 代碼結(jié)構(gòu)如下

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

/*
 * 返回 [min, max] 區(qū)間的隨機函數(shù)
 * min  : 起始位置
 * max  : 結(jié)束位置
 *    : 返回[min, max]區(qū)間之內(nèi)的位置
 */
extern int random(int min, int max);

/*
 * C 基礎(chǔ), 使用隨機函數(shù)
 */
int main(int argc, char* argv[]) {

  int min = -5, max = 5;
  int i = 0;

  // 開始統(tǒng)一 初始化種子
  srand((unsigned)time(NULL));

  while(i < 100) {
    printf("%3d ", random(min, max));
    if (++i % 10 == 0)
      putchar('\n');
  }

  system("pause");
  return 0;
}

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

測試結(jié)果是

基本比較穩(wěn)定. 一切都在預(yù)料之中.

總結(jié) 本文得出兩個推論

　　a. rand()偽隨機函數(shù), 存在G點. 并且可以找到

　　b. G點不隨著二次 mod 取余改變.

后記

錯誤是難免的, 預(yù)祝明天愉快~~

以上這篇C基礎(chǔ) 尋找隨機函數(shù)的G點詳解就是小編分享給大家的全部內(nèi)容了，希望能給大家一個參考，也希望大家多多支持我們。

上一篇：浮點數(shù)在計算機中存儲方式是怎樣的

欄目：C語言

下一篇：簡單掌握Linux系統(tǒng)中fork()函數(shù)創(chuàng)建子進程的用法

本文標(biāo)題：C基礎(chǔ) 尋找隨機函數(shù)的G點詳解