Phương pháp thích hợp để hạn chế số pseduo-ngẫu nhiên thành một phạm vi nhỏ hơn là gì?

Question

Cách tốt nhất để hạn chế các giá trị của PRNG thành một phạm vi nhỏ hơn là gì? Nếu bạn sử dụng mô-đun và số lượng tối đa cũ không chia hết cho số lượng tối đa mới, bạn thiên vị về phía 0 đến (old_max - new_max - 1). Tôi cho rằng cách tốt nhất sẽ là một cái gì đó như thế này (đây là điểm nổi, không toán số nguyên)

random_num = PRNG()/max_orginal_range * max_smaller_range 

nhưng một cái gì đó trong ruột của tôi làm cho tôi hỏi phương pháp đó (có thể nổi thực hiện điểm và đại diện khác biệt?).

Trình tạo số ngẫu nhiên sẽ tạo ra các kết quả nhất quán trên nền tảng phần cứng và phần mềm, và hạn chế cũng cần phải có.

Tôi có quyền nghi ngờ mã giả ở trên (nhưng không phải vì lý do tôi nghĩ). Của MichaelGG answer khiến tôi suy nghĩ về vấn đề theo một cách khác. Tôi có thể mô hình hóa nó bằng cách sử dụng các số nhỏ hơn và kiểm tra mọi kết quả. Vì vậy, giả sử chúng ta có một PRNG tạo ra một số ngẫu nhiên từ 0 đến 31 và bạn muốn phạm vi nhỏ hơn là 0 đến 9. Nếu bạn sử dụng modulus bạn thiên về 0, 1, 2 và 3. Nếu bạn sử dụng mã giả ở trên bạn thiên về 0, 2, 5, và 7. Tôi không nghĩ rằng có thể có một cách tốt để lập bản đồ một bộ vào khác. Điều tốt nhất mà tôi đã đưa ra cho đến nay là tạo lại các số ngẫu nhiên lớn hơn old_max/new_max, nhưng điều đó cũng có vấn đề sâu sắc (giảm thời gian, thời gian để tạo số mới cho đến khi một số nằm trong phạm vi bên phải, v.v.) .

Tôi nghĩ rằng tôi có thể đã tiếp cận một cách ngây thơ vấn đề này. Nó có thể là thời gian để bắt đầu một số nghiên cứu nghiêm túc vào văn học (ai đó đã phải giải quyết điều này trước đây).

Answer 1

Tôi biết điều này có thể không phải là câu trả lời đặc biệt hữu ích, nhưng tôi nghĩ cách tốt nhất là thụ thai một vài phương pháp khác nhau, sau đó thử chúng ra vài triệu lần và kiểm tra tập kết quả.

Khi nghi ngờ, hãy tự mình thử.

EDIT

Cần lưu ý rằng nhiều ngôn ngữ (như C#) đã xây dựng trong việc hạn chế về chức năng

int maximumvalue = 20; 
Random rand = new Random(); 

rand.Next(maximumvalue); 

Và bất cứ khi nào có thể, bạn nên sử dụng những chứ không phải bất kỳ mã bạn sẽ tự viết. Đừng sáng tạo lại bánh xe.

Answer 2

Nếu PRNG() đang tạo các số ngẫu nhiên được phân phối thống nhất thì điều này có vẻ tốt. Trong thực tế (nếu bạn muốn quy mô trung bình vv) ở trên nên được sử dụng tốt cho tất cả các mục đích. Tôi đoán bạn cần phải hỏi những gì các lỗi liên kết với PRNG gốc() là, và cho dù thao tác thêm sẽ thêm vào đó đáng kể.

Nếu nghi ngờ, tạo ra một bộ mẫu thích hợp kích thước, và nhìn vào kết quả trong Excel hoặc tương tự (để kiểm tra có nghĩa là bạn/std.dev vv cho những gì bạn mong muốn)

Answer 3

Nếu bạn có quyền truy cập để một hàm PRNG (nói, ngẫu nhiên()) mà sẽ tạo ra các số trong phạm vi 0 < = x < 1, có thể bạn không chỉ làm:

random_num = (int) (random() * max_range); 

để cung cấp cho bạn các số trong phạm vi từ 0 đến max_range?

Answer 4

Sau đây là cách lớp ngẫu nhiên của CLR hoạt động khi giới hạn (theo Reflector):

long num = maxValue - minValue; 
if (num <= 0x7fffffffL) { 
    return (((int) (this.Sample() * num)) + minValue); 
} 
return (((int) ((long) (this.GetSampleForLargeRange() * num))) + minValue); 

Thậm chí nếu bạn đang đưa ra một int tích cực, nó không phải là khó khăn để làm cho nó một đôi. Chỉ cần nhân int ngẫu nhiên bởi (1/maxint). Đi từ một int 32-bit đến một đôi nên cung cấp độ chính xác đầy đủ. (Tôi đã không thực sự thử nghiệm một PRNG như thế này, vì vậy tôi có thể thiếu một cái gì đó với phao.)

Answer 5

Máy tạo số ngẫu nhiên Psuedo về cơ bản tạo ra một chuỗi ngẫu nhiên 1 và 0, khi được nối với nhau, là một số lượng vô hạn lớn ở hai cơ sở. mỗi khi bạn tiêu thụ một chút từ bạn đang prng, bạn đang chia số đó cho hai và giữ modulus. Bạn có thể làm điều này mãi mãi mà không lãng phí một chút nào.

Nếu bạn cần một số trong phạm vi [0, N), thì bạn cần giống nhau, nhưng thay vì hai cơ số, bạn cần cơ sở N. Về cơ bản là tầm thường để chuyển đổi cơ số. Tiêu thụ số lượng bit bạn cần, trả lại phần còn lại của các bit đó lại cho prng của bạn để được sử dụng vào lần sau khi cần số.