generuje dowolną losową liczbę całkowitą
Z góry przepraszam, ponieważ nie mam dużego doświadczenia z jakimkolwiek formalnym pojęciem losowości.
Tytuł mówi o tym większość: chcę wygenerować losową liczbę całkowitą w rozsądnym czasie, w którym może pojawić się każda liczba całkowita, niezależnie od tego, czy z równą częstotliwością, czy nie, nie jest ważna. Ponadto pamięć komputera nie stanowi problemu, ponieważ nawet przy nieskończonej przestrzeni pamięci do przechowywania tych wygenerowanych liczb nie jest oczywiste, jak można to zrobić. Nie poczyniłem żadnych postępów w znalezieniu właściwego algorytmu, ale oto moje obserwacje.
Jeśli możesz wygenerować dowolną liczbę rzeczywistą losowo, możesz użyć funkcji takich jak funkcja floor do wygenerowania dowolnej liczby całkowitej. Gdybyś mógł losowo wygenerować dowolną liczbę rzeczywistą między dowolnym interwałem$[a,b]$, możesz użyć funkcji asymptotycznych, takich jak $\tan$ wygenerować dowolną liczbę rzeczywistą.
Ogólnie rzecz biorąc, jeśli mam zestaw S, który ma większą lub równą liczność liczb całkowitych i mogę losowo wygenerować element w S, wtedy mogę losowo wygenerować dowolną liczbę całkowitą, odwzorowując członków S na liczby całkowite.
Wiem, że istnieją sekwencje, takie jak pierwsza sekwencja przerw, które są losowe i zawierają dowolnie duże liczby całkowite, ale nie można ich łatwo obliczyć.
Jednak to wszystko w odniesieniu do tego, o czym mogę pomyśleć. Nie zdziwiłbym się, gdyby nie było łatwego rozwiązania problemu, ale jeśli ktoś ma powód, dla którego nie jest to możliwe, to również chciałbym usłyszeć.
Odpowiedzi
Dowolny rozmiar nie ma znaczenia, ponieważ obliczenia nie mogą się zatrzymać!
Weź pod uwagę, że rzucasz monetą za każdy bit losowej liczby całkowitej, a wtedy zobaczysz, że rzucanie monetą nigdy się nie kończy.
Należy być ostrożnym grając z dowolnym rozmiarem. Matematycznie można powiedzieć, że niech$x$ być losową liczbą całkowitą, tj $x \stackrel{R}{\leftarrow} \mathbb Z$jednakże, kiedy spróbujesz znaleźć wartość tego, staniesz w obliczu jego generacji. Jeśli chcesz mieć jednolitą losową liczbę całkowitą, to oczywiście się nie powiedzie!
Teraz załóżmy, że masz limit, taki jak $0\color{red}{<} x \leq 2^L$wtedy możesz użyć LFSR do wygenerowania liczb losowych w zakresie. Jeśli LFSR z rozmiarem$L$ jest maksymalna to jest okresowa i ma okres $2^L-1$. W tym okresie odwiedza wszystkie możliwe$L$-bitowe liczby z wyjątkiem stanu zerowego. Możesz zdobyć ziarno od czasu i zacząć go używać.
Zauważ, że LFSR jest daleki od bycia kryptograficznie bezpiecznym losowym pseudo generatorem (CSPRNG). Mając tylko$2L$ wyjście bitowe z LFSR jest wystarczające do określenia kolejnych bitów dzięki algorytmowi Berlakamp-Massay - i właściwie eliminacja Gaussa jest wystarczająca, jednak BM jest dużo szybszy.