Mỗi ngôn ngữ có một hàm ngẫu nhiên() hoặc một cái gì đó tương tự để tạo ra một số giả ngẫu nhiên. Tôi tự hỏi điều gì xảy ra bên dưới để tạo ra những con số này? Tôi không lập trình bất cứ điều gì mà làm cho kiến thức này cần thiết, chỉ cần cố gắng để đáp ứng sự tò mò của riêng tôi.ngẫu nhiên() thực sự hoạt động như thế nào?
Toàn bộ chương đầu tiên của công việc của Donald Knuth làm việc Seminumerical Algorithms được thực hiện với chủ đề tạo số ngẫu nhiên. Tôi thực sự không nghĩ rằng một câu trả lời SO sẽ đến gần với mô tả các vấn đề liên quan. Đọc sách.
Anh ấy đã cập nhật cuốn sách này trong vài thập kỷ qua chưa? Nó có thể không phải là nguồn tốt nhất nữa. –
Và giải pháp thay thế của bạn là ... cái gì? –
Tôi không nghĩ nhiều đã thay đổi trong các nguyên tắc cơ bản của các số ngẫu nhiên trong những thập kỷ qua, ít nhất là không phải trong dòng chính. Người ta luôn có thể xem xét các bài nghiên cứu lý thuyết về việc tạo ngẫu nhiên, nhưng tôi vẫn khuyên bạn nên chọn Knuth như một bàn đạp. – Kena
Wikipedia page là một tham chiếu tốt.
Thuật toán thực tế được sử dụng sẽ phụ thuộc vào ngôn ngữ và việc triển khai ngôn ngữ.
Để trả lời chính xác câu trả lời của bạn, chức năng ngẫu nhiên được cung cấp bởi hệ điều hành (thường).
Nhưng cách hệ điều hành tạo số ngẫu nhiên này là một lĩnh vực chuyên môn trong khoa học máy tính. Xem ví dụ trang wiki được đăng trong các câu trả lời ở trên.
Không, fonction ngẫu nhiên luôn được cung cấp bởi hệ thống ngôn ngữ. Nó có thể sử dụng hệ điều hành để có được một số entropy, nhưng hàm c rand() (thường) thì không. –
Tôi phải đồng ý với Neil, nhiều hệ điều hành cung cấp các API số ngẫu nhiên và giả ngẫu nhiên, nhưng nhiều thư viện chuẩn đã chứng minh * triển khai riêng biệt *. Trong bất kỳ trường hợp nào, cho đến khi bạn đọc tài liệu, bạn phải giả định rằng chúng là tất cả các công việc tuyến tính crappy tuyến tính không an toàn cho khoa học, bí mật hoặc bất kỳ thứ gì liên quan đến tiền. Các tài liệu sẽ xác nhận điều này về một số, sau đó bạn kiểm tra bất kỳ khiếu nại được thực hiện bởi những người khác. – dmckee
random() là một trình tạo số giả ngẫu nhiên (PRNG). random() chủ yếu được thực hiện như một bộ tạo đồng tuyến tuyến tính. Đây là hàm của dạng X (n + 1) (aXn + c) modulo m. Xn là chuỗi các số giả ngẫu nhiên được tạo ra. Chuỗi số được di truyền dễ đoán. Thuật toán này không thể được sử dụng như một PRNG an toàn mã hóa.
Wikipedia:Linear congruential generator
Và hãy nhìn vào các bài kiểm tra cực đoan cho PRNG PRNG Diehard Tests
Bạn quên đề cập đến những con số ngẫu nhiên được sản xuất bởi một LCG là một nơi nào đó giữa tầm thường và khủng khiếp. – starblue
Có bạn đúng nhưng đối với một số thế hệ số ngẫu nhiên nhanh chóng và bẩn nó là ok. Bạn có biết các bài kiểm tra thống kê DIEHARD về PRNG không? Phần lớn PRNG thất bại một cách nào đó trong các thử nghiệm này. –
TestU01 của L'Ecuyer cũng là một khuôn khổ thử nghiệm tốt đẹp hiện nay. Nhược điểm duy nhất là nó được thiết kế để tìm lỗ hổng trong gần như tất cả các máy phát điện :-) – Joey
Hóa ra là đáng ngạc nhiên dễ dàng để có được con số giả ngẫu nhiên một nửa chiều-phong nha. Trong nhiều thập kỷ, tiêu chuẩn vàng là một thuật toán đơn giản: giữ trạng thái x, nhân với hằng số A (32x32 => 64 bit) rồi thêm hằng số B, sau đó trả về 32 bit thấp x. Nếu A và B được chọn cẩn thận, điều này thực sự hoạt động khá tốt.
Số giả ngẫu nhiên cũng cần lặp lại để tái tạo lại hành vi trong quá trình gỡ lỗi. Vì vậy, việc tạo hạt giống máy phát (khởi tạo x với, nói, thời gian trong ngày) thường tránh trong khi gỡ lỗi.
Trong những năm gần đây và với nhiều chu kỳ tính toán sẵn có để ghi, các thuật toán phức tạp hơn có sẵn, một số thuật toán được phát minh kể từ khi xuất bản Thuật toán Seminumerical khác. Các hệ điều hành cũng bắt đầu cung cấp các bit entropy có nguồn gốc từ mạng và phần cứng cho các mục đích mã hóa chuyên dụng.
(a) LCG có * không * tạo ra số pseudorandom nửa chừng, thực tế kết quả khá khủng khiếp đối với tai họa, tùy thuộc vào cách bạn chọn yếu tố, bổ sung và modulus.(b) Máy phát điện tốt hơn không phải lúc nào cũng có nghĩa là chúng chậm hơn. Ví dụ, MT19937 là một máy phát điện tuyệt vời (mặc dù được thay thế ngay bây giờ) chạy nhanh hơn hầu hết các triển khai LCG. (c) Trong khi nó có thể giúp gỡ lỗi khi một PRNG tạo ra đầu ra có thể lặp lại, nó hoàn toàn bắt buộc trong các mô phỏng. – Joey
Vui lòng đọc lại câu hỏi. Anh ta không yêu cầu thuật toán tốt nhất, câu hỏi là: chúng hoạt động như thế nào? Có, misterenne twister là một thuật toán tốt hơn. Đó là những gì Ruby sử dụng, và nếu câu hỏi là "những gì tốt nhất" chúng tôi có thể đã thảo luận về nó. Thật thú vị khi lưu ý rằng một số triển khai MT sử dụng LCRNG để khởi tạo. – DigitalRoss
Chắc chắn, câu hỏi hỏi về cách nó được thực hiện nhưng bạn đang nói rằng nó dễ dàng để gett số ngẫu nhiên phong nha với một LCG, mà chỉ là sai. Đối với khởi tạo MT, nếu được thực hiện đúng, điều này là đủ. Điều quan trọng là (a) nếu bạn sử dụng nhiều RNG mà hạt * của bạn * không có phụ thuộc tuyến tính và (b) máy phát điện của bạn không giới thiệu một. MT19937 đã được hình thành theo cách mà phương pháp khởi tạo được đề xuất không ảnh hưởng đến chất lượng của đầu ra. – Joey
Một điều bạn có thể muốn kiểm tra là họ thiết bị ngẫu nhiên có sẵn trên một số hệ điều hành giống như Unix như Linux và Mac OSX. Ví dụ, trên Linux, hạt nhân tập hợp entropy từ nhiều nguồn khác nhau vào một nhóm mà sau đó nó sử dụng để tạo hạt giống cho trình tạo số giả ngẫu nhiên của nó. Entropy có thể đến từ nhiều nguồn khác nhau, đáng chú ý nhất là trình điều khiển thiết bị jitter từ các phím bấm, sự kiện mạng, hoạt động đĩa cứng và (hầu hết tất cả) chuyển động của chuột. Ngoài ra, còn có các kỹ thuật khác để thu thập entropy, một số trong số chúng thậm chí còn được thực hiện hoàn toàn bằng phần cứng.Có hai thiết bị ký tự mà bạn có thể nhận các byte ngẫu nhiên từ và trên Linux, chúng hoạt động theo cách sau:
Lưu ý rằng mặc dù Mac OSX sử dụng một phương pháp khác cho PRNG và do đó không chặn, điểm chuẩn cá nhân của tôi (thực hiện ở trường đại học) cho thấy nó ít ngẫu nhiên hơn hạt nhân Linux. Chắc chắn đủ tốt, mặc dù.
Vì vậy, trong các dự án của mình, khi tôi cần ngẫu nhiên, tôi thường đọc từ một trong các thiết bị ngẫu nhiên, ít nhất là cho hạt giống cho một thuật toán trong chương trình của tôi.
'/ dev/urandom' vẫn là một PRNG bảo mật mã hóa. Chúng được thiết kế sao cho trạng thái của máy phát không thể dễ dàng đoán được (trái ngược với các RNG thực sự tồn tại vì trạng thái của chúng không thể đoán được). Trong mọi trường hợp, ngay cả đối với phần lớn các ứng dụng cần bảo mật, '/ dev/urandom' là một lựa chọn lành mạnh. Bạn chắc chắn sẽ vui vẻ khi cố gắng sử dụng '/ dev/random' (và sau đó chờ cho ứng dụng của bạn kết thúc), đặc biệt là với nhiều quá trình hoặc người dùng trên cùng một hệ thống :-) – Joey
Sau khi bạn đọc bài viết wikipedia, bạn đã có những câu hỏi cụ thể nào? http://en.wikipedia.org/wiki/Random_number_generation –
Một số trình tạo số ngẫu nhiên đọc Bộ đệm ẩn của Internet Explorer và thư mục temp Windows trung tâm trong hồ sơ người dùng của bạn. Bằng cách đọc 1KB dữ liệu từ mỗi tệp mà nó gặp phải, một số ngẫu nhiên đáng kể được tạo ra. –
+1 cho câu hỏi đúng ngữ pháp. -2 cho không có nghiên cứu rõ ràng nào. –