Fonte original do algoritmo aleatório `(seed * 9301 + 49297)% 233280`?

9

Se você procurar exemplos de criação de um gerador de números aleatórios semeado (pseudo), encontrará coisas como esta (exemplo específico 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);
}

Esses números específicos (9301, 49297, 233280) e o algoritmo são usados ​​repetidamente, mas ninguém parece ter uma referência definitiva para isso. Quem inventou esse algoritmo e testou a distribuição? Existe um papel ou algo para citar?

history random jlarson
fonte
5
é um gerador congruente linear, mas com um período bastante pequeno (apenas 233k enquanto um int de 32 bits permite ter um período de 4 bilhões de dólares)
catraca
11
As pessoas costumam copiar o código diretamente dos livros, então provavelmente é de um livro antigo em algum lugar e foi copiado várias vezes. Também parece ser um caso limitante. Possivelmente útil: heydari.persiangig.com/Ebooks/Applied_Crypto-Ch11-ch20.pdf/… ict.griffith.edu.au/anthony/info/C/RandomNumbers
barrycarter
2
Qualquer que seja a origem, esses são valores terríveis para o cálculo de uma semente.
3
@ jlarson um comentário não é suficientemente longo, mas há dois problemas em mãos. Primeiro, como mencionado na catraca, o módulo é o período máximo : número de números únicos antes que o gerador se repita. O período real pode ser menor. Segundo, os outros dois números (principalmente o multiplicando) devem ser relativamente primos ao número do módulo para garantir um período mais longo. Idealmente, o número do módulo é o maior número primo menor que o número inteiro máximo positivo que se encaixa no tipo de dados, e os outros dois números também são números primos grandes.
11
Essa é a versão curta e resumida de por que esses números são terríveis, uma vez que essa é uma discussão paralela e a adição de uma resposta real não é apropriada para esta pergunta. Eu recomendo dar uma volta pela Wikipedia e talvez Matemática ou Ciência da Computação para obter mais informações, embora algoritmos de números tecnicamente pseudo-aleatórios também estejam no tópico dos programadores.

Respostas:

7

Uma pesquisa rápida do Google Livros mostra que esses números (9301, 49297, 233280) foram usados ​​em várias referências:

  • Receitas numéricas em FORTRAN 77
  • Uma introdução aos métodos numéricos em C ++
  • Recurso do desenvolvedor de CGI: programação da Web em TCL e PERL
  • Fortran 77 eficaz para engenheiros e cientistas
  • Desenvolvimento JavaScript
  • Tudo em C
  • Exemplos Java em poucas palavras
  • Algoritmos seminuméricos
  • Uma Introdução à Mecânica

O mais antigo é o dos métodos computacionais para computação matemática de 1977 de George Elmer Forsythe, Michael A. Malcolm e Cleve B. Moler (Prentice-Hall), embora o Google não mostre onde o texto foi usado no livro para que não possa ser verificado.

A primeira mostra o texto é Numerical Recipes in Pascal (Primeira edição): The Art of Scientific Computing , Volume 1 da Press, Teukolsky, Vetterling e Flannery em uma tabela de página inteira de "Constantes para portadores de números aleatórios portáteis". Esses números particulares são dados com um excesso em 2 ^ 31.

A série de livros de Receitas Numéricas é imensamente popular e está impressa desde 1986.

Hugo
fonte
11
Uau, se a resposta não estiver aqui, não sei onde seria. Obrigado .. // Eu esperava poder apontar para uma pesquisa específica sobre por que esses números são especiais, mas isso é suficiente. 9301 é um produto de dois primos (71x131), 49297 é um primo - instintivamente, sinto que isso deve ser relevante. 233280 não é primo - é igual a 2x2x2x2x2x2x3x3x3x3x3x3x5 (ou 2 ^ 6 * 3 ^ 5 * 5)
jlarson