如何確保模

鑑於這種簡單的隨機數生成器正面的價值觀：如何確保模

int i, r = 0; 
for (i = 0; i < 50; i++) { 
    r = (1234 * r + 101) % (11000000); 
    printf("%d\n", r); 
}

出人意料的是，我得到負值！

不應該是正值嗎？有人可以解釋這個嗎？

來源

2017-07-02 Don

不，它不應該是積極的。如果第一個操作數是負數，結果也將是負數。 –

整數溢出：'1234 * 6553739 + 101'最有可能超過'INT_MAX' – UnholySheep

@Don：'long'可能不夠大，'unsigned long long'保證至少有64個值位，這就足夠了。 – chqrlie

由於你的程序有整數算術溢出，你會得到負值。該行爲實際上對於簽名類型int未定義。你應該使用更大的類型來避免這種情況。類型unsigned long long保證具有至少64個值位，這對於最大中介結果1234 * 10999999 + 101已足夠。

int i; 
unsigned long long r = 0; 
for (i = 0; i < 50; i++) { 
    r = (1234 * r + 101) % 11000000; 
    printf("%llu\n", r); 
}

RICI評論說，因爲它的值是範圍0..10999999r並不需要成爲一個更大的類型。這並非完全正確，因爲int類型可能太小而無法處理這些值。 int的範圍可以小至-32767..32767。

儘管如此，中間計算必須用更大的類型來執行，以避免算術溢出。以下是相應的代碼：

int i, r = 0; // assuming 32-bit ints 
for (i = 0; i < 50; i++) { 
    r = (1234ULL * r + 101) % 11000000; 
    printf("%d\n", r); 
}

來源

2017-07-02 19:29:35 chqrlie

我同意。謝謝 – Don

'unsigned'溢出實際上已經定義了行爲（不像有符號溢出） – UnholySheep

'r'可以是一個int;它是需要更大（並且最好是無符號）的中間值。 'r =（1234ULL * r + 101）％11000000;' – rici

正如您在其他答案中所見，此行爲是由於溢出。

如果您希望能夠在早期檢測到類似情況，請使用gcc或clang的未定義行爲清除程序（UBSan）。

$ /opt/clang+llvm-4.0.0-armv7a-linux-gnueabihf/bin/clang -fsanitize=undefined don.c 

$ ./a.out 
don.c:8:18: runtime error: signed integer overflow: 1234 * 10923091 cannot be represented in type 'int'

don.c，第8行，第18欄是該行的乘法：r = (1234*r +101) % (11000000);。

來源

2017-07-02 19:36:56

你必須小心，因爲你的代碼產生溢出，即使你做了unsigned算術。

可能是你int變量是數2.147.483.647溢出後一個32位整數，如果你認爲你計算的最壞的情況下，你必須1.234*10.999.999 + 101 ==> 13.573.998.867，計算模操作之前，而這將導致你錯誤。

你能做的最好的事情就是用64位數字的這種計算不溢出，與此示例代碼（你會看到不同的結果，即使你的正常積極的）

$ cat pru.c 
#include <stdio.h> 
#include <stdint.h> 

int main() 
{ 
    uint64_t i, r=0; 
    for (i = 0; i < 50; i++) { 
      r = (1234*r +101) % (11000000); 
       printf("%llu\n", r); 
    } 
}

這會導致：

這是正確的，因爲1.234*10.999.999 + 101 ==> 13.573.998.867永遠不會溢出uint64_t號（這是你可以有最大的結果），並會產生正確的結果。

來源

2017-07-03 05:40:38

回答

相關問題