我需要在C中生成一些隨機數來測試和調試系統。該系統是一個具有有限功能集的自定義硬件(SoC),因此我只能使用基本的數學運算。C隨機數生成(純C代碼,無庫或函數)
不,我不能在stdlib或math.h中使用隨機數生成器。我需要自己寫。那麼是否有某種生成隨機數的算法?
我知道一個簡單的解決方案是在我的工作站上生成數字並將它們嵌入到模塊中,但我不想這樣做。
我需要在C中生成一些隨機數來測試和調試系統。該系統是一個具有有限功能集的自定義硬件(SoC),因此我只能使用基本的數學運算。C隨機數生成(純C代碼,無庫或函數)
不,我不能在stdlib或math.h中使用隨機數生成器。我需要自己寫。那麼是否有某種生成隨機數的算法?
我知道一個簡單的解決方案是在我的工作站上生成數字並將它們嵌入到模塊中,但我不想這樣做。
隨機數生成器基本上是從一個起始種子遞歸地運行一個特殊*散列函數。
我在我的C#代碼中使用了MurmurHash2 algorithm,效果很好。它的實施非常快速且簡單,並且已經通過低衝突率測試,分佈得非常好。該項目用C++編寫幾個不同的開放源代碼的散列功能,這應該很容易轉換爲C.
*通過特殊的我的意思是一個值運行哈希函數應該返回另一個看似隨機的(但確定的)值,以便輸出不會形成模式。而且,返回值的分佈應該具有均勻分佈。
您可以嘗試George Marsaglia的Multiply-with-carry。維基百科
代碼:
#include <stdint.h>
#define PHI 0x9e3779b9
static uint32_t Q[4096], c = 362436;
void init_rand(uint32_t x)
{
int i;
Q[0] = x;
Q[1] = x + PHI;
Q[2] = x + PHI + PHI;
for (i = 3; i < 4096; i++)
Q[i] = Q[i - 3]^Q[i - 2]^PHI^i;
}
uint32_t rand_cmwc(void)
{
uint64_t t, a = 18782LL;
static uint32_t i = 4095;
uint32_t x, r = 0xfffffffe;
i = (i + 1) & 4095;
t = a * Q[i] + c;
c = (t >> 32);
x = t + c;
if (x < c) {
x++;
c++;
}
return (Q[i] = r - x);
}
一個linear congruential generator將很容易實現。純C中的一個很好的實現可用here。
只需挖掘Park and Miller在CACM 10月88期的文章。
他們提出的一般算法是:
a = 16807;
m = 2147483647;
seed = (a * seed) mod m;
random = seed/m;
雖然文章包括幾個改進。
檢查gsl library的源代碼,實現了幾個經過良好測試的算法。
您可能想要尋找Mersenne Twister。有很多更高質量的算法。一篇好文章內容的概述,你在這裏找到:
「..has經過測試是非常完善的密碼學。」當然不! MurmurHash是一種相對較新的哈希算法,它有很多缺陷和很多調整 - 這是一個很好的信號,表明算法很弱。當然,您可以使用它來生成僞隨機數,但是沒有人應該將其用於加密操作。 – adelphus 2012-02-29 11:09:38
@ adelphus-我不是密碼學方面的專家,所以我會刪除這個陳述,但我認爲,從密碼學的角度來看,這隻意味着良好的分佈,低衝突和低偏差。 @彼得O. - 好趕上:我的確的意思是制服。哎呀。 – dlras2 2012-02-29 17:46:36