2012-11-09 9 views
8

Dobra, więc robię badania nad tym, jak generowane są losowe liczby za pomocą metody Math.random. Do tej pory dowiedziałem się, że zaczyna się od "losowego" nasienia, a to ziarno jest podłączone do jakiegoś skomplikowanego równania, aby utworzyć losową liczbę. Jeśli materiał siewny jest zawsze taki sam, czy wynik będzie zawsze taki sam?Przewidzieć nasienie skryptu Javascript Math.random

Słyszałem, że nasiona Math.random są generowane przez bieżący czas, czy to prawda? Muszą korzystać z aktualnego czasu aż do mili-sekund lub czegoś, ponieważ gdybyś nie zrobił, dostałeś taki sam wynik.

Czym dokładnie jest nasiono? Czy jest to czas taki jak "10:45" czy data ORAZ data "10:45 11/8/12" czy jakaś kombinacja?

Jak znaleźć ziarno, aby można było przewidzieć wynik?

Chcę, aby móc podłączyć następująco:

alert(Math.floor((Math.random()*10)+1)); 

w moim pasku adresu, i być w stanie przewidzieć wynik. Czy to jest możliwe?

+0

Cały punkt 'Math.random()' jest taki, że nie można tego przewidzieć (przynajmniej nie bez większych trudności). –

+1

Czy jest ktoś, kto czyta źródło "V8", aby dać nam jednoznaczną odpowiedź? – TiansHUo

+0

@TiansHUo - Przeczytałem kod źródłowy Rhino i odpowiedziałem na pytanie na podstawie tego, co przeczytałem: http://stackoverflow.com/a/13303029/783743 –

Odpowiedz

14

Przejrzałem Rhino source code, aby dowiedzieć się, z której funkcji pseudolosowej korzystają. Najwyraźniej są one fall back dla funkcji Math.random zdefiniowanej w .

Dokumentacja Math.random mówi:

Zwraca podwójną wartość ze znakiem dodatnim, większej lub równej 0,0 i mniej niż 1,0. Zwracane wartości są wybierane pseudolosowo z (w przybliżeniu) jednolitym rozkładem z tego zakresu.

Kiedy ta metoda jest pierwszy nazywa, to tworzy jeden nowy generator pseudolosowych-numeryczny, dokładnie tak, jakby przez wyrażenie

new java.util.Random 

Ten nowy generator pseudolosowych Numer służy następnie do wszystkich połączeń do tej metody i nie jest używany nigdzie indziej.

Ta metoda jest poprawnie zsynchronizowana, aby umożliwić poprawne użycie przez więcej niż jeden wątek. Jeśli jednak wiele wątków wymaga generowania liczby pseudolosowej z dużą szybkością, może to zmniejszyć rywalizację dla każdego wątku o własny generator liczb pseudolosowych.

Więc sprawdziłem dokumentację java.util.Random i znalazł this (dla domyślnego konstruktora):

tworzy nowy generator liczb losowych. Jego nasiona są inicjowane wartości w oparciu o aktualny czas:

public Random() { this(System.currentTimeMillis()); } 

dwa losowe obiekty utworzone w tym samym milisekundy będzie miał taką samą sekwencję liczb losowych.

Teraz wiemy na pewno, że materiał siewny jest bieżącym czasem w milisekundach. Ponadto, dokumentacja dla second constructor mówi:

Tworzy nowy generator liczb losowych za pomocą jednego długiego materiału siewnego:

public Random(long seed) { setSeed(seed); } 

Używane metodą najbliższego utrzymać ten stan liczby pseudolosowy generator.

documentation dla metody setSeed mówi:

Ustawia nasionko tego generatora liczb losowych za pomocą jednego długiego nasienie. Ogólną umową setSeed jest to, że zmienia stan tego obiektu generatora liczb losowych tak, aby był dokładnie w tym samym stanie, jak gdyby został właśnie utworzony z nasionami argumentów jako nasionami. Metoda setSeed jest realizowany przez klasy Dowolnie w następujący sposób:

synchronized public void setSeed(long seed) { 
    this.seed = (seed^0x5DEECE66DL) & ((1L << 48) - 1); 
    haveNextNextGaussian = false; 
} 

Realizacja setSeed do klasy Dowolnie się stanie wykorzystać tylko 48 bitów danego materiału siewnego. Zasadniczo jednak metoda nadrzędna może wykorzystywać wszystkie 64 bity długiego argumentu jako wartość początkową.Uwaga: Chociaż wartość początkowa to AtomicLong, ta metoda musi być nadal zsynchronizowana, aby zapewnić poprawną semantykę hasNextNextGaussian.

actual method wykorzystywane do generowania liczby losowej jest nextDouble:

Zwraca obok pseudolosowych równomiernie rozmieszczone podwójną wartość pomiędzy 0,0 i 1,0 z sekwencji tego generatora liczb losowych.

Realizacja funkcji nextDouble jest następujący:

public double nextDouble() { 
    return (((long)next(26) << 27) + next(27)) 
     /(double)(1L << 53); 
} 

Wyraźnie to depends na next funkcję:

Generuje następny numer pseudolosowego. Podklasa powinna to zmienić, ponieważ jest używana przez wszystkie inne metody.

Realizacja funkcji next jest następujący:

synchronized protected int next(int bits) { 
    seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); 
    return (int)(seed >>> (48 - bits)); 
} 

to funkcja pseudolosowych szukasz. Jak to się mówi w dokumentach:

to liniowy przystający generator liczb pseudolosowych, określone przez DH Lehmer i opisane Donald E. Knutha Sztuka programowania, tom 2: Seminumerical algorytmów, rozdział 3.2. 1.

Należy jednak pamiętać, że jest to tylko generator liczb losowych używany przez Rhino. Inne implementacje, takie jak Spidermonkey i V8, mogą mieć własne generatory liczb pseudolosowych.

+0

+1, Wspaniała odpowiedź, więc oznacza to, że mogę przynajmniej wyliczyć zakres możliwych czasów w zależności od dokładności czasu, a przynajmniej mogę uzyskać listę możliwych liczb losowych (co jest zdecydowanie niebezpieczne ze względów bezpieczeństwa). Ale jeśli chodzi o pierwotne pytanie, prawdopodobnie nie, chyba że można uzyskać dokładnie milisekundę. – TiansHUo

+0

@Aitit masz rację, że to zależy od realizacji, jeśli piszesz webapp przy użyciu javascript, różne przeglądarki używają różnych generatorów liczb pseudolosowych. W przypadku konkretnych zastosowań może to spowodować spustoszenie. Liniowe metody kongruencji są notorycznie złe przy posiadaniu wszystkich pożądanych "losowych" właściwości - silnych korelacji szeregowych. Zobacz http://stackoverflow.com/questions/19507469/math-random-and-web-programming-in-javascript. Świetna odpowiedź BTW. – MHH

0

Nasienie jest wartością liczbową, więc domyślam się, że otrzymasz to, jeśli zadzwonisz pod numer Date.now() (lub new Date().getTime() dla starszych przeglądarek).

Jednak nie jestem pewien, kiedy jest brane ziarno, lub jeśli nasiona są odizolowane od bieżącej strony lub wspólne dla całego procesu przeglądarki. Przewidywanie liczb losowych powinno być bardzo trudne lub niemożliwe, to cały ich przypadek.

6

Prawdopodobnie jest więcej nasion niż liczba milisekund, ponieważ możesz wywołać Math.random() wiele razy w tej samej milisekundy, a za każdym razem zwraca inną wartość.

for (var i = 0; i < 3; i++) { 
    console.log(Math.random(), (new Date()).getTime()); 
}; 

Moja wyjściowa:

0.0617244818713516 1352433709108 
0.8024995378218591 1352433709108 
0.2409922298975289 1352433709108 

Gdybym jej realizacji może dokonać wstępnej materiału siewnego na podstawie liczby milisekund, a następnie dodać 1 za każdym razem, to się nazywa, tak, że nie dostanie tę samą wartość początkową dwa razy.

Oto 100% dokładny sposób przewidywania wyjście z Math.random():

Math.random = function() { return .5; }; 

Teraz Math.random() zawsze zwróci .5.

+0

@ 43.52.4D. Jest jeden sposób, aby się tego dowiedzieć. zacznij to robić, za dziesięć lat otrzymamy odpowiedź, jeśli to możliwe, czy nie ... Jesteś prawdziwy ?! – gdoron

+0

Oto kod Chrome Math.random(): http://code.google.com/p/v8/source/browse/trunk/src/v8.cc#170 Wygląda na to, że zasadniczo używasz systemu generator liczb losowych, więc jak dobrze to ostatecznie zależy od RNG twojego systemu operacyjnego. – evan

0

Nie, nie można przewidzieć nasion, ale można wstępnie wytworzyć wystarczającą liczbę, aby dokładnie brutalnie wymusić dopasowanie.

W każdym razie, zacznij od przeczytania strony wiki o RNG - http://en.wikipedia.org/wiki/Random_number_generation, przyjrzyj się praktycznym implementacjom PRNG.

Powiązane problemy