Hiểu thuật toán hàm rand() của Visual C++

Question

Trong C/C++, rand() và srand() thường được chúng ta sử dụng khi chúng ta muốn lấy một số nguyên ngẫu nhiên. Nhưng khi tôi cố tự viết lại, tôi thấy khó hiểu thuật toán. Hàm này rất dễ viết chỉ bằng một vài dòng, nhưng công thức là sự hiểu lầm.

Công thức chính:

ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L; 

Mã gốc tham gia:

void __cdecl srand (unsigned int seed) 
{ 
    _getptd()->_holdrand = (unsigned long)seed; 
} 

int __cdecl rand (void) 
{ 
    _ptiddata ptd = _getptd(); 
    return (((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff); 
} 

Answer 1

Nó chỉ là mô-đun số học. Bạn đang nhân và thêm vào một số được lấy modulo 2^32 (ví dụ), và trả về 16 bit trên làm số "ngẫu nhiên" của bạn. Bởi vì bạn đang nhân và thêm các số là coprime vào modulus, điều này tạo ra các loại phân phối thống nhất.

Lựa chọn cẩn thận của hai số là rất quan trọng. Ví dụ: nếu bạn đã sử dụng "* 4" và "+ 8", có thể bạn sẽ không gặp phải nhiều sự ngẫu nhiên.

Sơ đồ này được gọi là linear congruential.

Answer 2

Trình tạo số giả ngẫu nhiên đó là Linear Congruential Generator.

Answer 3

Bạn có thể tìm giải thích về Máy tạo đồng phân tuyến tính (LCG) và các bộ tương tự khác hoặc bộ tạo giả ngẫu nhiên khác, và về việc chọn các hằng số cụ thể này trong một bài báo xuất sắc trong tháng này (7-2011). Tạp chí (DDJ): Fast, High-Quality, Parallel Random-Number Generators: Comparing Implementations.

Tôi nghĩ rằng bạn sẽ cần phải đăng ký tại trang web DDJ (miễn phí) để đọc phần đầu của bài viết này (link), nhưng nếu bạn đang vào C++ và toán học, bạn nên làm điều đó anyway ...

Answer 4

Trước khi gọi rand, vì trang man cho srand chỉ ra rằng "Nếu không có giá trị hạt giống nào được cung cấp, hàm rand() được tự động gieo với giá trị 1", thì cách tiếp cận tốt hơn để gọi rand là trước tiên gọi srand sẽ "đặt đối số của nó làm hạt giống cho một chuỗi các số nguyên giả ngẫu nhiên mới được trả về bởi rand()".

Như một ví dụ, hãy xem xét awk sau, nawk, trố mắt đang được sử dụng trong một kịch bản bash shell để tạo ra một mới (ngẫu nhiên) địa chỉ mac - tức là .genmacaddr tham chiếu trong đoạn mã:

enter code here 
BEGIN { 
    n0 = "00" 
    srand() 
    n1 = sprintf("%02x", int(255 * rand())) 
    n2 = sprintf("%02x", int(255 * rand())) 
    n3 = sprintf("%02x", int(255 * rand())) 
    n4 = sprintf("%02x", int(255 * rand())) 
    n5 = sprintf("%02x", int(255 * rand())) 
    print n0":"n1":"n2":"n3":"n4":"n5 
} 

trong đó đoạn mã trong tập lệnh bash shell là:

enter code here 
ifconfig eth0 down 
newmacaddr=`nawk -f .genmacaddr -` 
ifconfig eth0 hw ether $newmacaddr 
ifconfig eth0 up 

Nếu tôi không nhầm, giá trị hạt giống cho srand bắt nguồn từ đồng hồ hệ thống.

Tôi hy vọng điều này sẽ giúp bạn hiểu cách tiếp cận giải pháp mã hóa của bạn sẽ hoạt động.

Answer 5

Như đã nói đó là một congruential tuyến tính, (bạn có thể nhìn mà lên nếu bạn muốn trong bài bình luận sâu sắc về cách những tạo giả ngẫu nhiên giá trị)

hạt giống được lưu trữ trong _getptd() -> _ holdrand (sau đây gọi là holdrand)

Mã này "hoạt động" bằng cách thực hiện phép nhân thông thường và thêm bước nhưng sau đó tràn giữ thương mại thành lấy "mô đun" ngụ ý 0x100000000.

Tôi đề cập đến điều này vì nó không rõ ràng ngay lập tức và thường không được coi là phong cách tốt.

Kỹ thuật tràn biến số nguyên sẽ hủy bỏ hành vi không xác định, nhưng trên hầu hết các nền tảng, nó có thể dự đoán được rất tốt để các kỹ sư của Microsoft bỏ qua vấn đề đó.