Tại sao 1103515245 được sử dụng trong rand?

Question

Tôi đang nói về this thực hiện đáng ngạc nhiên đơn giản của rand() từ tiêu chuẩn C:

static unsigned long int next = 1; 

int rand(void) /* RAND_MAX assumed to be 32767. */ 
{ 
    next = next * 1103515245 + 12345; 
    return (unsigned)(next/65536) % 32768; 
} 

Từ this Wikipedia article chúng ta biết rằng nhân a (trong mã trên a = 1103515245) nên thực hiện chỉ có 2 điều kiện:

1. a - 1 có thể chia hết cho tất cả các yếu tố chính của m.
   (Trong trường hợp của chúng tôi m = 2^32, kích thước của int, vì vậy m chỉ có một thừa số nguyên tố = 2)
2. a - 1 là bội số của 4 nếu m là bội số của 4.
   (32768 là bội số của 4 và 1103515244 too)

Tại sao họ đã chọn một điều lạ, khó nhớ ", tôi bị chán với những con số ngẫu nhiên này, viết bất kỳ số nào", như 1103515245?

Có thể có một số lý do khôn ngoan, rằng con số này bằng cách nào đó tốt hơn cái kia?

Ví dụ: tại sao không đặt a = 20000000001? Nó to hơn, đẹp hơn và dễ nhớ hơn.

Answer 1

Nếu bạn sử dụng một LCG để vẽ điểm trên không gian chiều d, họ sẽ nằm trên tối đa là (d m!) ^{/ _d} siêu phẳng. Đây là lỗi của LCG.

Nếu bạn không cẩn thận chọn một và m (ngoài điều kiện cho chu kỳ đầy đủ), chúng có thể nằm trên ít máy bay hơn thế. Những con số này đã được chọn bởi cái được gọi là kiểm tra phổ .

"Kiểm tra phổ" (tên đến từ lý thuyết số) là khoảng cách tối đa giữa các siêu liên tiếp mà trên đó các bản phân phối chung d chiều nằm. Bạn muốn nó càng nhỏ càng tốt cho càng nhiều d như bạn có thể kiểm tra.

Xem this paper để xem xét lịch sử về chủ đề. Lưu ý rằng máy phát điện bạn trích dẫn được đề cập trong bài báo (như ANSIC) và được xác định là không tốt. Tuy nhiên, 16 bit có thể chấp nhận được, nhưng nhiều ứng dụng sẽ cần nhiều hơn 32768 giá trị riêng biệt (như bạn chỉ ra trong phần bình luận, thời gian thực sự là 2^31).).

Mã nguồn gốc trong tài liệu ANSI không mất trật tự cao 16 bit, năng suất một máy phát điện rất kém đó là dễ dàng để lạm dụng (rand() % n là những gì những người đầu tiên nghĩ ra để vẽ một con số nằm giữa 0 và n, và điều này mang lại một cái gì đó rất không ngẫu nhiên trong trường hợp này).

Xem thêm phần thảo luận về LCG trong Bí quyết số. Trích dẫn:

Thậm chí tệ hơn, nhiều máy phát điện sớm đã xảy ra đặc biệt là sự lựa chọn số xấu cho m và a. Một thói quen khét tiếng như vậy, RANDU, với một = 65539 và m = 231, đã được phổ biến rộng rãi trên các máy tính lớn của IBM trong nhiều năm, và được sao chép rộng rãi vào các hệ thống khác. Một trong số chúng tôi nhớ lại là một sinh viên tốt nghiệp sản xuất một âm mưu "ngẫu nhiên" chỉ với 11 máy bay và được tư vấn lập trình của trung tâm máy tính của mình nói rằng ông đã lạm dụng máy phát số ngẫu nhiên : "Chúng tôi đảm bảo rằng mỗi số là ngẫu nhiên riêng lẻ, nhưng chúng tôi không đảm bảo rằng nhiều hơn một trong số họ là ngẫu nhiên. ”Điều đó đã thiết lập lại nền giáo dục sau đại học của chúng tôi ít nhất một năm!

Answer 2

Hãy nhớ rằng rand() là xấp xỉ uniform distribution. Những con số này được sử dụng bởi vì chúng đã được thử nghiệm để cho thấy rằng chúng tạo ra một phân bố đồng đều hơn.

Cho vô số các cặp số nguyên không dấu trong phạm vi biểu diễn, tôi nghi ngờ bất kỳ ai đã thử tất cả chúng với tất cả các hạt hợp lệ. Nếu bạn nghĩ rằng bạn có một sự lựa chọn tốt hơn các thông số, chỉ cần thử nó ra! Bạn có mã, chỉ cần đưa ra các tham số của LCG và chạy thử nghiệm. Tạo ra một loạt các con số (nói 10 triệu), tính toán một biểu đồ của các số được tạo ra và âm mưu để xem xét sự phân bố.

chỉnh sửa Nếu bạn quan tâm đến việc phát triển trình tạo số giả ngẫu nhiên để sử dụng trong các ứng dụng thực, tôi khuyên bạn nên đọc các tài liệu đáng kể về chủ đề này. "Lời khuyên" được đưa ra ở trên chỉ được đề xuất để giúp cho thấy rằng việc chọn các tham số LCG tùy ý "lớn hơn, mát mẻ hơn và dễ nhớ hơn" sẽ phân phối rất kém. /chỉnh sửa

Bên cạnh đó, nó là một chức năng thư viện và tôi chưa bao giờ thấy một chương trình sử dụng phiên bản thư viện chuẩn của rand() nhớ thông số LCG của hãng.

Answer 3

Con số đó có vẻ đặc biệt, nó chỉ giữa hai số nguyên tố: P.

Bây giờ nói chuyện nghiêm túc, để xem đó có phải là lựa chọn tốt hay không, chỉ cần nhìn vào đầu ra. Bạn sẽ thấy kết quả rất khác nhau ngay cả khi lật một chút.

Ngoài ra, hãy cân nhắc mức độ dự đoán bạn mong đợi ... việc triển khai đó thật khủng khiếp, bạn có thể xem xét một giải pháp thay thế mạnh mẽ nhưng đơn giản hơn, chẳng hạn như FNV-1a.

Answer 4

tính toán sớm có xu hướng liên quan đến bản thân với bit và byte và thủ thuật chơi với các thanh ghi để giảm thiểu byte mã (trước dòng có byte)

Tôi đã chỉ tìm thấy một đầu mối hợp lý dưới đây:

Đầu ra của máy phát điện này không phải là rất ngẫu nhiên. Nếu chúng ta sử dụng trình tạo mẫu được liệt kê ở trên, thì trình tự của 16 byte khóa sẽ rất cao không ngẫu nhiên. Ví dụ, nó chỉ ra rằng bit thấp của mỗi đầu ra liên tiếp của rand() sẽ thay thế (ví dụ: 0,1,0,1,0,1, ...). Bạn có thấy tại sao không? Các bit thấp của x * 1103515245 là giống như bit thấp của x, và sau đó thêm 12345 chỉ flips bit thấp. Vì vậy, bit thấp thay thế. Điều này thu hẹp bộ khóa có thể chỉ còn 2113 khả năng, ít hơn nhiều so với giá trị mong muốn của 2128.

http://inst.eecs.berkeley.edu/~cs161/fa08/Notes/random.pdf

Và hai câu trả lời hợp lý:

Cải thiện một nghèo bởi Bays, Durham Bays, Carter, SD Durham

http://en.wikipedia.org/wiki/TRNG