幾個副程式，把一個學生輔導送進 期交所寫程式

sjgau

這個 說來話長，跟底下的程式設計有關。

系統所提供的產生亂數的副程式，
問題很多

請看 底下的程式設計

如果有人能夠知道 問題在哪裡，
如何改進
送 30元

// for fast random number generator

#include "inc-01.h"
// ----------------------------------------------

int main(int argc, char *argv[])
{
   int i, a;
   srand(time(NULL));

   for (i=1;i<=20;i++) {
      a= rand();
      printf("i= %5d, a= %10d \n", i, a);
   }
   pause();

   return EXIT_SUCCESS;
}// end of main()

無無明

for (i=1;i<=20;i++) {
      a= rand();
      printf("i= %5d, a= %10d \n", i, a);
   }

問題在於
每一次呼叫，又是從新開始
在一個模糊的記憶片段裡，有一絲絲的映象
曾經處理 RAND（）函數
採用 連續 或 延續 取值的方式
不讓他 RESET 從新來過

sjgau

無無明 發表於 12-4-11 18:27
for (i=1;i

我把期交所的問題 描述一下，

期交所需要 利用盤後的時間，做模擬壓力測試。

模擬 盤中 發生 兩顆子彈的事件，
民眾恐慌丟單，期交所的電腦和網路 是否能夠負荷的問題

模擬的基礎是亂數，
系統所提供的亂數的範圍，只有 0 - 32767

所以 需要重新寫作 速度快，範圍廣的 亂數產生器

sjgau

http://en.wikipedia.org/wiki/Linear_congruential_generator

這裡有詳細的介紹 產生虛擬亂數的 數學方法
我比較習慣使用

Apple CarbonLib 所介紹的方法

R(n)= (R(n-1)*a + b) mod c

a= 7^5
b= 0
c= (2^31) - 1

sjgau

下面這個程式設計，可以證明 系統所提供的
亂數的範圍

只有 0 - 32767

產生 十億個亂數，需要 24.796秒



// for fast random number generator

#include "inc-01.h"
// ----------------------------------------------

int main(int argc, char *argv[])
{
   int no, min, max, i, a, t1, t2;
   double dt;
   
   no= 10;
   while (no > 0) {
      delay_ms((int) (1.1*1000));// for srand()
      
      time1(&t1);
      srand(time(NULL));
      
      min= max= rand();
      for (i=1;i<=no;i++) {
         a= rand();
         if (min > a) min= a;
         if (max < a) max= a;
      }
      time2(t1, &dt);
      
      printf("no= %12ld, min= %10ld, max= %10ld, dt= %10.3lf \n",
      no, min, max, dt);
      
      no*= 10;
   }  
   
   pause();
   return EXIT_SUCCESS;
}// end of main()

stock1586

sjgau 發表於 12-4-11 19:29
下面這個程式設計，可以證明 系統所提供的
亂數的範圍

請問你這問題是期交所要的?

還是你解決這問題就可以進期交所ㄋ?

sjgau

stock1586 發表於 12-4-11 19:47
請問你這問題是期交所要的?

還是你解決這問題就可以進期交所ㄋ?

麻煩您 看一下 前後文，

是學生去 interview , 對方所出的 作業題。

sjgau

好啦

自問 自答

關鍵就是
要速度快，又要範圍 加大，
所以，底下的副程式

big_rand() 符合要求。

大概 47.288秒，可以產生 十億個亂數，
範圍從 0 到 1,073,741,824

但是，他並沒有符合 正確的亂數產生器的標準要求，
學術界要求

一 盡可能的把範圍 加大

二 盡可能的產生均勻的分布

三 在產生相同的亂數之前，要把每一個 亂數都
產生過 一遍



// for fast random number generator

#include "inc-01.h"
// ----------------------------------------------

//  big_rand();
int big_rand(void)
{
   int a1, a2;
   a1= rand();
   a2= rand();
   
   return((a1<<15) + a2);   
}// end of big_rand()
// ----------------------------------------------

int main(int argc, char *argv[])
{
   int no, t1, t2, min, max, a, i;
   double dt;
   
   no= 10;
   while (no > 0) {
      delay_ms((int) (1.1*1000));
      srand(time(NULL));
      
      time1(&t1);
      min= max= big_rand();
      for (i=1;i<=no;i++) {
         a= big_rand();
         if (min > a) min= a;
         if (max < a) max= a;
      }
      time2(t1, &dt);
      
      printf("no= %12ld, min= %12ld, max= %12ld, dt= %10.3lf \n",
      no, min, max, dt);
      
      no*= 10;
   }// end of while
         
   pause();
   return EXIT_SUCCESS;
}// end of main()

綠茶妹

看到程式我就很興奮的跑進來看，真是職業病。哈。
只記得RAND一定要有種子，不能每次都一樣，不然很容易被破解。

sjgau

所謂的 種子數，有啊

srand(time(NULL));

就是 拿現在的時間的秒數，
從 1970/01/01 00:00:00 到現在的 一共的秒數
當作 亂數的種子數

綠茶妹

sjgau 發表於 12-4-11 21:09
所謂的 種子數，有啊

srand(time(NULL));

嗯嗯...是啊..

上次有人問我，在IC裡怎麼做亂數出來，
真是考倒我了。
IC裡不一定會有計時器這種東東，
可行的方法還是要找個會變的東西當種子，如雜訊。

sjgau

我的建議是
搞一個 counter, 紀錄啟動以後的 一些使用者有關的動作的
時間間隔

你覺得如何？

meimeichen

if (min > a) min= a;
if (max < a) max= a;
壓力測試裏頭　代表著　每一個　Tick 都要　減省起來
這個寫法會部會 無謂的浪費CPU 週期!
如果判斷出 min > a 就不需要　再判斷　max < a
試試看　應該會省下一些時間吧

三 在產生相同的亂數之前，要把每一個 亂數都
產生過 一遍　這個說法應該是錯誤的
亂數的追求　在於　統計學裡的常態分配　，不該全部跑一遍才重能複呦
如果亂數產生器　要全部跑一遍才重複　那就是作弊方程式而不是亂數產生器了

既然亂數產生器是 主角
何不 用 ASM 寫一個 套進去用呢
保證你的速度會是最快的

sjgau

if 的部分，是在 研究發展的階段，
不是 最後的使用 階段

第三項，是書上說的

sjgau

我比較喜歡 下面的產生亂數的演算法
是按照 Apple CarbonLab 的方法實作的

範圍是
1 - 2147483646

產生十億個亂數，需要時間比較久，
大概需要 54.658秒




// for fast random number generator

#include "inc-01.h"
// ----------------------------------------------

void rnd1(int *s1)
{
   // double x1, x2, x3;
   
   /* 130.078 seconds for 21E8
   x1= (double) (*s1);
   x2= x1*16807.0;
   x3= fmod(x2, 2147483647.0);
   (*s1)= (int) (x3 + 0.5);
   */
   
   // 116.423 seconds
   (*s1)= (int) ((fmod((((double) (*s1))*16807.0), 2147483647.0)) + 0.5);
}
// ----------------------------------------------

int main(int argc, char *argv[])
{
   // for rnd1(), rnd2(), irnd(), ...
   int t1, t2, s1, s2, no, min, max, i;
   double ct= 0.0, dt;
   
   no= 10;
   while (no > 0) {
      delay_ms((int) (1.1*1000));
      
      time1(&t1);
      s1= t1;
      
      rnd1(&s1);
      min= max= s1;

      time1(&t1);
      for (i=1;i<=no;i++) {
         rnd1(&s1);
         if (min > s1) min= s1;
         if (max < s1) max= s1;
      }
      time2(t1, &dt);
      
      printf(" no= %12ld, min= %12ld, max= %12ld, dt= %10.3lf \n", no, min, max, dt);
      no*= 10;
   }
         
   pause();
   return EXIT_SUCCESS;
}// end of main()