Tạo số ngẫu nhiên mục đích chung

Question

C++ 11 đã giới thiệu một thư viện số ngẫu nhiên vượt trội đến C rand(). Trong C, bạn thường thấy đoạn mã sau:

srand(time(0)); 
rand() % MAX + MIN; 

Vì time(0) lợi nhuận thời gian hiện tại trong vài giây, cuộc gọi liên tiếp nhanh chóng đến chương trình sẽ tạo ra cùng một chuỗi các con số. Việc sửa chữa nhanh chóng cho điều này là để cung cấp một hạt giống trong nano giây:

struct timeval time; 
gettimeofday(&time,NULL); 
srand((time.tv_sec * 1000) + (time.tv_usec/1000)); 

Tất nhiên điều này không làm thay đổi thực tế rằng rand() được phổ biến được coi là giải pháp thay thế xấu và vượt trội là một trong hai phi di động (như Linux random()) hoặc dựa vào thư viện của bên thứ ba (như Tăng cường).

Trong C++ 11, chương trình ngắn nhất tôi biết để tạo ra số ngẫu nhiên tốt là:

#include <iostream> 
#include <random> 

int main() 
{ 
    std::random_device rd; 
    std::mt19937 mt(rd()); 
    std::uniform_int_distribution<int> dist(1, 10); 
    std::cout << dist(mt); 
} 

std::random_device là không cầm tay và std::default_random_engine không được khuyến khích vì nó có thể chọn một công cụ nghèo, chẳng hạn là std::rand. Trên thực tế, std::random_shuffle không được dùng nữa và std::shuffle được ưu tiên vì lý do này. Nói chung, tôi thấy mọi người nói sử dụng chrono để cung cấp một hạt giống thay vì:

std::chrono::high_resolution_clock::now().time_since_epoch().count() 

Đây không phải là chỉ khó nhớ, nhưng trông thậm chí còn xấu khi chúng ta muốn sử dụng nano giây thay vì:

using namespace std::chrono; 
std::mt19937 mt(duration_cast<nanoseconds>(high_resolution_clock::now() 
             .time_since_epoch()).count()); 

• Cách tiếp cận C có vẻ mong muốn bởi vì nó không đòi hỏi nhiều bản liệt kê .

• random_device là dễ nhất vì nó không yêu cầu một lớp lót xấu xí mặc dù nó không mang tính di động.

• mt19937 khó nhớ hơn default_random_engine.

Cách tiếp cận nào tốt nhất?

Answer 1

(1) biết máy phát điện có sẵn và chọn một trong những phù hợp nhất cho công việc

(2) nấu entropy giống, vẽ một thước đo tiêu chuẩn (như 256 bit), in nó vào nhật ký

(3) biến khối hạt tiêu chuẩn của bạn thành một seed_seq có kích thước thích hợp cho máy phát điện trong câu hỏi và hạt giống genny

Về (1): các máy phát trong thư viện chuẩn là một chút khó sử dụng bởi vì tất cả chúng có một số đặc thù và tất cả đều không đạt được các kiểm tra PRNG chuẩn như TestU01có hệ thống. Bạn phải biết các khuyết tật cụ thể của họ để đánh giá khả năng ứng dụng của họ. Nếu không, hãy dùng mt19937 hoặc ranlux, hạt giống tốt và hy vọng là tốt nhất. Sử dụng typedef - của riêng bạn - cho phép bạn chuyển đổi và thử nghiệm với các đồng xu khác nhau. typeid(rng_t).name() xem qua ngụy trang và ghi lại tên thật.

Về (2): bạn không thể chuyển giao quyền truy cập thô, thô ráp cho các quy trình gieo hạt; nếu bạn làm vậy thì sự khác biệt về hạt giống nhỏ sẽ chỉ dẫn đến những khác biệt nhỏ về trạng thái. Entropy phải được nấu chín thành một mẩu giấy nhẵn mịn, trong đó mỗi bit phụ thuộc vào xác suất 50% trên mỗi bit của đầu vào ban đầu. Điều này bao gồm đầu vào như 1, 2, 3, ... Lấy một lượng tiêu chuẩn cố định của súp bit làm cho toàn bộ điều có thể quản lý, như in ra màn hình hoặc đăng nhập để đảm bảo khả năng lặp lại nếu cần. Không cần phải nói, nếu bạn sử dụng số lượng hạt giống như 1, 2, 42, ... thay vì hạt giống ngẫu nhiên thì bạn có thể in chúng vào nhật ký chứ không phải trích xuất từ ​​bit. Sử dụng máy xay bit của riêng bạn có nghĩa là bạn không phải lòng thương xót của các chức năng gieo hạt được phân tích một nửa, và thậm chí các hạt 'thiếu' giống như 1, 2, 3 và cứ thế cung cấp cho bạn trạng thái máy phát cực kỳ khác nhau (chuỗi).

Về (3): một số máy phát điện - như mt19937 - có trạng thái nội bộ rất lớn và vì vậy bạn cần phải kéo dài 256-bit (hoặc bất kỳ) tiêu chuẩn hạt giống của bạn khá nhiều. Thật không may, thư viện chuẩn không chứa bất kỳ trình tạo nào phù hợp với nhiệm vụ này, và cũng không có bộ điều hợp để biến một máy phát điện thành một seed_seq.

Tôi muốn sử dụng xorshift*, KISS, chạy (Công thức số) hoặc 4x32 Tausworthe (a.k.a. lfsr113) nhưng không có thư nào trong thư viện. Thư viện không có bất kỳ chức năng trộn phù hợp (bit mài) hoặc.

Tôi đã đăng mã cho bộ trộn âm thanh - một chức năng trộn bit đơn giản và cực kỳ hiệu quả - trong a similar topic; Tôi đang tặng KISS cổ điển và một Tausworthe ở đây vì tôi không thể tìm thấy các tài liệu tham khảo phù hợp, sạch sẽ trên mạng.

struct KISS { uint32_t a, b, c, d; ... }; 

uint32_t KISS::cycle() 
{ 
    a = (a & 0xFFFF) * 36969 + (a >> 16);   // 16-bit MWC, a.k.a. znew() 
    b = (b & 0xFFFF) * 18000 + (b >> 16);   // 16-bit MWC, a.k.a. wnew() 
    c = c * 69069 + 1234567;      // 32-bit LCG, a.k.a. CONG()(
    d ^= d << 13; d ^= d >> 17; d ^= d << 5; // 32-bit XorShift a.k.a. SHR3(), corrected 

    return (((a << 16) | (b & 0xFFFF))^c) + d; // mixing function (combiner) 
} 

Các kết hợp Tausworthe:

struct LFSR113 { uint32_t a, b, c, d; ... }; 

uint32_t LFSR113::cycle() 
{ 
    a = ((a^(a << 6)) >> 13)^((a & ~0x01) << 18); // 31 bits 
    b = ((b^(b << 2)) >> 27)^((b & ~0x07) << 2); // 29 bits 
    c = ((c^(c << 13)) >> 21)^((c & ~0x0F) << 7); // 28 bits 
    d = ((d^(d << 3)) >> 12)^((d & ~0x7F) << 13); // 25 bits 

    return a^b^c^d; 
} 

Để sử dụng như máy phát điện đầu tiên bạn sẽ phải điều chỉnh hạt bị cấm (tiểu bang dính) nhưng đối với hạt kéo dài (thực hiện một seed_seq) này có thể được bỏ qua một cách an toàn. Có rất nhiều lựa chọn thay thế, như sử dụng std :: vector và một trong các trình tạo đơn giản (LCG) để tạo seed_seq phong nha, nhưng tôi thích thử, tin cậy các giải pháp được phân tích kỹ lưỡng với số lượng mã tối thiểu. Hai máy phát 4x32 được hiển thị ở đây có thể được sử dụng Định lý còn lại của Trung Quốc, và ngược lại, bất kỳ trạng thái nào cũng có thể được ánh xạ tới điểm duy nhất của nó trong chuỗi tổng thể (chú ý qua những thứ như quỹ đạo trong thời điểm này). Điều này làm cho chúng và khác, máy phát điện tương tự hấp dẫn như máy phát điện chính để sử dụng chung bất cứ khi nào súng lớn như xorshift1024 * (hoặc mt19937) là không cần thiết.

Trong mọi trường hợp, bạn sẽ cần một chút mã - ví dụ: các mẫu trong tệp tiêu đề - để làm cho máy phát điện chuẩn <random> dễ sử dụng, thoải mái và an toàn để sử dụng. Nhưng nó là 100% giá trị nỗ lực. Các máy phát điện không quá nóng nhưng chúng có thể sử dụng được; phần còn lại của cơ sở hạ tầng là khá phong nha và nó có thể đi một chặng đường dài hướng tới giải quyết vấn đề của bạn.

P.S .: một số triển khai (VC++) cho phép nó truyền bất kỳ trình tạo nào tới hàm seed(), điều này làm cho mọi việc trở nên dễ dàng. Những người khác - gcc - không, có nghĩa là bạn phải làm điều seed_seq nếu bạn muốn mã của bạn được di chuyển. Nếu bạn muốn những thứ siêu dễ dàng, chỉ cần vượt qua hạt giống của bạn được lựa chọn thông qua murmur_mix() trước khi giao cho hạt giống() và di chuyển trên.

The wages of fear: khi bạn đã nhồi nhét phép thuật vào tiêu đề, ứng dụng thực sự rất dễ dàng.

#include "zrbj/rng_wrapper.hpp" 
#include <random> 
#include <typeinfo> 

int main() 
{ 
    zrbj::seeded<std::mt19937> rng(42); 

    std::cout << typeid(rng.wrapped_rng).name() << " -> " << rng(); 
}  

Điều này in máy phát, 42 và hạt giống thực tế vào nhật ký, ngoài việc đập bit thành mảnh vỡ và nhồi chúng vào mt19937. Mã một lần, dựa lưng, thưởng thức.