Oryginalne źródło losowego algorytmu `(seed * 9301 + 49297)% 233280`?

9

Jeśli szukasz przykładów tworzenia rozstawionego (pseudo) generatora liczb losowych, napotkasz takie rzeczy (ten konkretny przykład http://indiegamr.com/generate-repeatable-random-numbers-in-js/ ):

// the initial seed
Math.seed = 6;

// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
    max = max || 1;
    min = min || 0;

    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;

    return min + rnd * (max - min);
}

Te konkretne liczby (9301, 49297, 233280) i algorytm są używane w kółko, ale wydaje się, że nikt nie ma na to definitywnego odniesienia. Kto wynalazł ten algorytm i przetestował dystrybucję? Czy jest papier lub coś do cytowania?

Jarsars
źródło
5
jest to liniowy przystający generator, ale z dość krótkim okresem (tylko 233 tys., podczas gdy 32-bitowy int pozwala mieć okres 4 miliardów
maniak zapadkowy
1
Ludzie często kopiują kod bezpośrednio z książek, więc prawdopodobnie pochodzi on gdzieś ze starej książki i został kilkakrotnie skopiowany. Wydaje się również, że jest to przypadek ograniczający. Być może pomocny: heydari.persiangig.com/Ebooks/Applied_Crypto-Ch11-ch20.pdf/… ict.griffith.edu.au/anthony/info/C/RandomNumbers
barrycarter
2
Bez względu na pochodzenie, są to okropne wartości do obliczenia zarodka.
3
@jlarson komentarz nie jest wystarczająco długi, ale istnieją dwa problemy. Po pierwsze, jak wspominał maniak zapadkowy, modulo to maksymalny okres: liczba unikalnych liczb, zanim generator się powtórzy. Rzeczywisty okres może być mniejszy. Po drugie, pozostałe dwie liczby (głównie wielokrotność) powinny być względnie pierwsze w stosunku do liczby modulo, aby zapewnić dłuższy okres. Idealnie liczba modulo jest największą liczbą pierwszą mniejszą niż maksymalna dodatnia liczba całkowita, która mieści się w typie danych, a pozostałe dwie liczby są również dużymi liczbami pierwszymi.
1
To jest krótka, krótka wersja tego, dlaczego te liczby są okropne, biorąc pod uwagę, że jest to dyskusja poboczna i dodanie rzeczywistej odpowiedzi nie jest odpowiednie dla tego pytania. Polecam skakanie po Wikipedii i może Matematyki lub Informatyki, aby uzyskać więcej informacji, chociaż technicznie algorytmy liczb pseudolosowych są również na temat u Programistów.

Odpowiedzi:

7

Szybkie wyszukiwanie w Książkach Google pokazuje, że te numery (9301, 49297, 233280) zostały użyte w wielu odnośnikach:

  • Przepisy numeryczne w FORTRAN 77
  • Wprowadzenie do metod numerycznych w C ++
  • CGI Developer's Resource: Programowanie sieciowe w TCL i PERL
  • Skuteczny Fortran 77 dla inżynierów i naukowców
  • Tworzenie skryptów JavaScript
  • Wszystko na C
  • Przykłady Java w pigułce
  • Algorytmy seminumeryczne
  • Wprowadzenie do mechaniki

Najstarsze to komputerowe metody obliczeń matematycznych z 1977 r. George Elmer Forsythe, Michael A. Malcolm, Cleve B. Moler (Prentice-Hall), chociaż Google nie pokazuje, gdzie tekst został użyty w książce, więc nie można go zweryfikować.

Najwcześniej pokazano tekst w Recepturach numerycznych w Pascal (pierwsze wydanie): The Art of Scientific Computing , Tom 1 , Press, Teukolsky, Vetterling and Flannery, na pełnej stronie tabeli „Stałe przenośnych generatorów liczb losowych”. Te konkretne liczby podano z przepełnieniem 2 ^ 31.

W Numerical Recipes seria książek są niezwykle popularne, a były w druku od 1986 roku.

Hugo
źródło
1
Wow, jeśli nie ma tu odpowiedzi, nie wiem, gdzie by była. Dzięki .. // Miałem nadzieję, że uda mi się wskazać na pewne szczegółowe badania, dlaczego te liczby są wyjątkowe, ale to wystarczy. 9301 jest iloczynem dwóch liczb pierwszych (71x131), 49297 jest liczbą pierwszą - instynktownie wydaje mi się, że to musi być istotne. 233280 nie jest liczbą pierwszą - równa się 2x2x2x2x2x2x3x3x3x3x3x3x5 (lub 2 ^ 6 * 3 ^ 5 * 5)
jlarson