tạo bất kỳ số nguyên ngẫu nhiên nào
Tôi xin lỗi trước vì tôi không có nhiều kinh nghiệm với bất kỳ khái niệm chính thức nào về sự ngẫu nhiên.
Tiêu đề nói lên phần lớn điều đó: Tôi muốn tạo một số nguyên ngẫu nhiên trong một khoảng thời gian hợp lý, nơi mọi số nguyên có thể xuất hiện, cho dù với tần suất bằng nhau hay không đều không quan trọng. Như một phần bổ sung, bộ nhớ máy tính không phải là một vấn đề, vì ngay cả với không gian bộ nhớ vô hạn để lưu trữ những con số được tạo này, không rõ bằng cách nào người ta có thể làm điều này. Tôi đã không đạt được bất kỳ tiến bộ nào trong việc thực sự tìm ra một thuật toán thích hợp nhưng đây là những quan sát của tôi.
Nếu bạn có thể tạo bất kỳ số thực nào một cách ngẫu nhiên thì bạn có thể sử dụng các hàm như hàm sàn để tạo bất kỳ số nguyên nào. Nếu bạn có thể tạo ngẫu nhiên bất kỳ số thực nào trong khoảng thời gian bất kỳ$[a,b]$, thì bạn có thể sử dụng các hàm tiệm cận như $\tan$ để tạo ra bất kỳ số thực nào.
Nói chung, nếu tôi có một tập hợp S có số nguyên lớn hơn hoặc bằng và tôi có thể tạo ngẫu nhiên một phần tử trong S, thì tôi có thể tạo ngẫu nhiên bất kỳ số nguyên nào bằng cách ánh xạ các phần tử của S với các số nguyên.
Tôi biết rằng có những chuỗi, chẳng hạn như chuỗi khoảng trống nguyên tố, là ngẫu nhiên và chứa các số nguyên lớn tùy ý, nhưng không thể tính toán dễ dàng.
Tuy nhiên đó là về nó liên quan đến những gì tôi có thể nghĩ đến. Tôi sẽ không ngạc nhiên nếu không có giải pháp dễ dàng cho vấn đề, nhưng nếu ai đó có lý do tại sao điều này là không thể, tôi cũng muốn nghe.
Trả lời
Kích thước tùy ý không có ý nghĩa vì không thể tạm dừng tính toán!
Hãy xem xét rằng bạn tung một đồng xu cho mỗi bit của số nguyên ngẫu nhiên, thì bạn có thể thấy rằng việc tung đồng xu là không bao giờ kết thúc.
Nên cẩn thận khi chơi với kích thước tùy ý. Về mặt toán học, bạn có thể nói rằng hãy$x$ là một số nguyên ngẫu nhiên, tức là $x \stackrel{R}{\leftarrow} \mathbb Z$tuy nhiên, khi bạn cố gắng tìm ra giá trị của điều này, bạn sẽ phải đối mặt với thế hệ của nó. Nếu bạn muốn một số nguyên ngẫu nhiên thống nhất thì rõ ràng là nó sẽ thất bại!
Bây giờ giả sử rằng bạn có một giới hạn như $0\color{red}{<} x \leq 2^L$thì bạn có thể sử dụng LFSR để tạo các số ngẫu nhiên trong phạm vi. Nếu một LFSR với kích thước$L$ là cực đại thì nó là chu kỳ và nó có chu kỳ là $2^L-1$. Trong giai đoạn này, nó truy cập tất cả có thể$L$-bit số ngoại trừ trạng thái hoàn toàn bằng không. Bạn có thể nhận được một hạt giống từ thời điểm đó và bắt đầu sử dụng nó.
Lưu ý rằng LFSR còn xa mới trở thành một Trình tạo giả ngẫu nhiên bảo mật về mặt mật mã (CSPRNG). Có chỉ$2L$ đầu ra bit từ LFSR đủ để xác định các bit tiếp theo do thuật toán Berlakamp-Massay - và trên thực tế, việc loại bỏ Gaussian là đủ, tuy nhiên, BM nhanh hơn nhiều-.