Czy generator liczb losowych może wygenerować inną moc wyjściową przy identycznych nasionach?

10

Tytuł podsumowuje. Chciałbym wiedzieć, czy istnieje algorytm zdolny do generowania zmiennych danych wyjściowych przy identycznych danych wejściowych bez polegania na innych źródłach losowości, takich jak DateTime.Now lub liczba wygenerowana z czujnika światła itp. Ponadto algorytmu nie można uruchomić po kolei tylko dwa odrębne, niepowiązane ze sobą przebiegi, które dają różne wyniki.

random

— ConditionRacer
źródło

Mówisz o generatorze pseudolosowych liczb, a konkretnie.

— Marcel

Większość języków pozwala na tworzenie instancji generatora liczb losowych bez konieczności określania zarodka, tak aby ziarno również było „losowe”. Istnieje powód, dla którego stosuje się nasiona.

— Neil

1

@ Neil: w takich przypadkach nadal istnieje ziarno, to tylko domniemanie, zwykle czas systemowy.

— Michael Borgwardt,

@MichaelBorgwardt, powiedziałem po prostu, że nasiona również będą losowe. Oczywiście nic nie jest naprawdę przypadkowe, ale zwykle czas systemowy zapewnia przyzwoite ziarno, o ile często nie tworzysz generatora liczb losowych bez podania ziarna, w którym to przypadku możesz uzyskać dwa razy to samo „losowe” ziarno.

— Neil

Istnieje ciekawy obszar badań nad niedokładnym sprzętem, który ma statystycznie dobrze niedokładną dokładność. Potencjalną korzyścią jest niższe zużycie energii. Samo obliczenie 2.0 + 2.0takiego systemu nie dałoby identycznych wyników. Nie potrzebuje innego źródła losowości.

— MSalters

15

Chciałbym wiedzieć, czy istnieje algorytm zdolny do generowania zmiennych danych wyjściowych przy identycznych danych wejściowych bez polegania na innych źródłach losowości, takich jak DateTime.Now lub liczba wygenerowana z czujnika światła itp.

Nie, jest to zasadniczo niemożliwe, ponieważ sama definicja algorytmu polega na tym, że jest on dobrze zdefiniowany i deterministyczny, tzn. Przy takim samym wejściu zawsze będzie generował ten sam wynik. Istnieją algorytmy randomizowane, ale wymagają one losowości jako danych wejściowych.

Ponadto, determinizm jest Najważniejszym celem projektu sprzętu komputerowego. Procesor, który nie wytwarza tego samego wyjścia przy takim samym wejściu, byłby całkowicie bezużyteczny dla większości celów.

— Michael Borgwardt
źródło

14

Nie, algorytm generowania liczb pseudolosowych zawsze będzie generował to samo wyjście przy tym samym ziarnie (stąd pseudolosowy ).

Interesujące jest dla mnie użycie terminu „algorytm” zamiast „program”. Wyklucza to pewną klasę odpowiedzi typu tak (miękkie błędy w pamięci RAM, różne przeplatanie wątków w wielowątkowym RNG itp.). Jeśli przyjmujesz za pewnik, że każde uruchomienie algorytmu pobiera takie same dane wejściowe przy każdej iteracji, jest dobrze określone bez losowości, wygeneruje to samo wyjście przy każdym uruchomieniu.

To powiedziawszy, nawet podstawowe rzeczy, takie jak temperatura procesora, są wystarczająco nieprzewidywalne, aby działać jako źródło entropii, jeśli są odpowiednio znormalizowane. Więc nie sądzę, że oznacza to, że można przewidzieć „bezpieczny kryptograficznie” generator liczb losowych, jeśli wiesz, o której godzinie został uruchomiony; wiele z nich korzysta z generowanego przez system feeda entropijnego.

— Brian
źródło

Algorytm był właściwym słowem :) W szczególności staram się wyeliminować zewnętrzne źródła entropii, błędy pamięci, kolejność wątków, nieprzewidywalne dane wejściowe, takie jak źródło światła itp. Myślę, że moje pytanie wynika z niezrozumienia losowych algorytmów i być może Mógłbym uczynić pytanie bardziej ogólnym. Naprawdę zastanawiam się, czy można stworzyć jakąkolwiek funkcję, która zwraca różne wyniki przy identycznych danych wejściowych (w tym wszystkie źródła entropii). Wydaje się, że odpowiedź brzmi „nie”

— ConditionRacer,

7

Czy wiesz, że ludzie bardzo ciężko pracują, aby zapewnić, że przy tym samym nasieniu za każdym razem tworzona jest ta sama sekwencja liczb losowych? Jest to pożądana właściwość w przypadku symulacji Monte Carlo, ponieważ oznacza to, że wyniki są w pełni odtwarzalne. Jeśli nie określisz nasion, użyjesz czegoś takiego jak czas, ale taka dokładność jest naprawdę pożądana.

Jedynymi RNG, w których jest to naprawdę niepożądane, są te wykorzystywane w kryptografii, i te zwykle osiągają to, używając własnego źródła liczb losowych systemu operacyjnego (które nie jest możliwe do przewinięcia w normalnych okolicznościach i które może używać fantazyjnego sprzętu), aby zapewnić swoje źródło .

— Donal Fellows
źródło

Tak, rozumiem co mówisz. Nie próbuję wdrażać niczego nowego, to była tylko późna nocna ciekawość.

— ConditionRacer

1

Podejrzewam, że jeśli zaimplementowałeś algorytm na różnych platformach sprzętowych i używał on technik takich jak pobieranie środkowych N bitów z liczby całkowitej, można by uzyskać różne odpowiedzi, gdyby kodowanie liczb całkowitych było inne (duża / mała / średnia). Możesz również mieć problemy z uruchomieniem na komputerach z układami FPU w porównaniu do tych, które nie występują, jeśli manipulujesz liczbami zmiennoprzecinkowymi. Prawdopodobnie nie jest to problem na komputerach klasy stacjonarnej, ale może być problem na telefonach.

— TMN
źródło