Midsquare method(中間平方法 / 平方取中法)

這部份主要參考 The Art Of Computer Programming.

這方法於 1946 年前後,John Von Neumann 建議用這方法生成亂數。辦法是取前面亂數的平方後,再取中間的數字。如生成 10 位數,先前之值為 1234567890,其平方為 1524157875019052100,於是下個亂數便為 1578750190。

此種技術異議性非常大,扣除掉「夠不夠亂」問題,危險在於若取出來的結果為 0 ,那麼接下來就一路都是 0 ,不斷地重覆本身下去。

於 20 世紀 50 年代左右,另一位 G.E. Forsythe 以 4 位數代替 10 位數,試了 16 個不同初值,結果發現,其中 12 個導致了以循環 6100, 2100, 4100, 8100,6100... 為結局之數列,另外二個退化成 0,另 N. Metropolis 也對此法進行試驗,過程中乃以二進制系統為主,用20位數進行工作時,證明了序列退化成 13 個不同循環最長週期為 142

若以整數位數為 10 位數,取中間五位數,C 語言程式碼約如下所述

#include <stdio.h>
#include <time.h>
unsigned long long seed;

/* 設亂數初值 / 亂數種子 */
void Midsquare_srand(unsigned s)
{
    seed = (unsigned long long)s;
}

unsigned int Midsquare_rand()
{
    seed = seed * seed % 100000ULL;
    return seed;
}

int main()
{
    int i;
    Midsquare_srand((unsigned)time(NULL));
    for(i=0; i!=10; ++i) 
	   printf("%u ", Midsquare_rand());
    return 0;
}

切記,這方法很容易退化,只要結尾是 5 ,最後必會循環:5 25 625 90625 90625;結果為 0,最後也是退化。如上所述,這種方法之週期並不長。

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()