positivos - numeros aleatorios en java netbeans

Primer número aleatorio después de setSeed en Java siempre similar

Question

Para dar un poco de contexto, he estado escribiendo una implementación básica de ruido Perlin en Java, y cuando se trataba de implementar siembra, me encontré con un error que no pude explicar.

Para generar los mismos vectores de peso aleatorio cada vez para la misma semilla, sin importar qué conjunto de coordenadas se consulte el nivel de ruido y en qué orden, newSeed una nueva semilla (nueva Semilla), basada en una combinación de la semilla original y la semilla original. coordenadas del vector de peso, y lo usó como la semilla para la aleatorización del vector de peso ejecutando:

rnd.setSeed(newSeed);
weight = new NVector(2);
weight.setElement(0, rnd.nextDouble() * 2 - 1);
weight.setElement(1, rnd.nextDouble() * 2 - 1);
weight.normalize()

Donde NVector es una clase hecha a sí mismo para matemáticas vectoriales.

Sin embargo, cuando se ejecuta, el programa generó muy mal ruido:

Después de algunas excavaciones, encontré que el primer elemento de cada vector era muy similar (y por lo tanto, la primera llamada nextDouble() después de cada llamada a setSeed() ) resultaba en que el primer elemento de cada vector en la grilla vectorial era similar.

Esto se puede probar ejecutando:

long seed = Long.valueOf(args[0]);
int loops = Integer.valueOf(args[1]);
double avgFirst = 0.0, avgSecond = 0.0, avgThird = 0.0;
double lastfirst = 0.0, lastSecond = 0.0, lastThird = 0.0;
for(int i = 0; i<loops; i++)
{
    ran.setSeed(seed + i);
    double first = ran.nextDouble();
    double second = ran.nextDouble();
    double third = ran.nextDouble();
    avgFirst += Math.abs(first - lastfirst);
    avgSecond += Math.abs(second - lastSecond);
    avgThird += Math.abs(third - lastThird);
    lastfirst = first;
    lastSecond = second;
    lastThird = third;
}
System.out.println("Average first difference.: " + avgFirst/loops);
System.out.println("Average second Difference: " + avgSecond/loops);
System.out.println("Average third Difference.: " + avgSecond/loops);

Que encuentra la diferencia promedio entre el primer, segundo y tercer números aleatorios generados después de que se haya llamado un método setSeed() sobre un rango de semillas como se especifica en los argumentos del programa; que para mí devolvió estos resultados:

C:/java Test 462454356345 10000
Average first difference.: 7.44638117976783E-4
Average second Difference: 0.34131692827329957
Average third Difference.: 0.34131692827329957

C:/java Test 46245445 10000
Average first difference.: 0.0017196011123287126
Average second Difference: 0.3416750057190849
Average third Difference.: 0.3416750057190849

C:/java Test 1 10000
Average first difference.: 0.0021601598225344998
Average second Difference: 0.3409914232342002
Average third Difference.: 0.3409914232342002

Aquí puede ver que la primera diferencia promedio es significativamente más pequeña que el resto, y aparentemente disminuye con semillas más altas.

Como tal, al agregar una simple llamada ficticia a nextDouble() antes de configurar el vector de ponderación, pude arreglar mi implementación de ruido perlin:

rnd.setSeed(newSeed);
rnd.nextDouble();
weight.setElement(0, rnd.nextDouble() * 2 - 1);
weight.setElement(1, rnd.nextDouble() * 2 - 1);

Resultando en:

Me gustaría saber por qué ocurre esta mala variación en la primera llamada a nextDouble() (no he verificado otros tipos de aleatoriedad) y / o alertar a las personas sobre este problema.

Por supuesto, podría ser un error de implementación en mi nombre, lo que agradecería si me lo indicaran.

Answer 1

Este es un problema conocido. Una semilla similar generará unos pocos primeros valores similares. Random no fue diseñado para usarse de esta manera. Se supone que debes crear una instancia con una buena semilla y luego generar una secuencia de números "aleatorios" de tamaño moderado.

Su solución actual está bien, siempre que se vea bien y sea lo suficientemente rápida. También puede considerar usar funciones de mezcla / hash que fueron diseñadas para resolver su problema (y luego, opcionalmente, usar la salida como semilla). Por ejemplo, vea: Función aleatoria paramétrica para la generación de ruido en 2D

Answer 2

La clase Random está diseñada para ser una fuente aérea baja de números pseudoaleatorios. Pero la consecuencia de la implementación "baja sobrecarga" es que la secuencia numérica tiene propiedades que están lejos de ser perfectas ... desde una perspectiva estadística. Has encontrado una de las imperfecciones. Random está documentado como un generador de congruencia lineal, y las propiedades de dichos generadores son bien conocidas.

Hay una variedad de formas de lidiar con esto. Por ejemplo, si tiene cuidado, puede ocultar algunas de las características "pobres" más obvias. (Pero se le aconsejaría que realice algunas pruebas estadísticas. No puede ver la no aleatoriedad en el ruido agregado a su segunda imagen, pero aún podría estar allí).

Alternativamente, si quiere números pseudoaleatorios que tengan buenas propiedades estadísticas garantizadas, entonces debe usar SecureRandom lugar de Random . Tiene gastos indirectos significativamente más altos, pero puede estar seguro de que muchas "personas inteligentes" habrán dedicado mucho tiempo al diseño, prueba y análisis de los algoritmos.

Finalmente, es relativamente simple crear una subclase de Random que use un algoritmo alternativo para generar los números; ver link . El problema es que debe seleccionar (o diseñar) e implementar un algoritmo apropiado.

Llamar a esto un " problema " es discutible. Es una propiedad bien conocida y comprendida de LCGs, y el uso de LCGs fue una opción de ingeniería conciente. La gente quiere PRNG de bajo costo, pero los PRNG de bajo costo tienen propiedades pobres. TANSTAAFL.

Ciertamente, esto no es algo que Oracle consideraría cambiar en Random . De hecho, las razones para no cambiar se establecen claramente en el javadoc para la clase Random .

"Para garantizar esta propiedad, se especifican algoritmos particulares para la clase Random . Las implementaciones Java deben usar todos los algoritmos que se muestran aquí para la clase Random , en aras de la portabilidad absoluta del código Java".

Answer 3

Mueva su setSeed fuera del bucle. El PRNG de Java es un generador congruente lineal, por lo que se garantiza que se sembrará con valores secuenciales para dar resultados correlacionados en las iteraciones del ciclo.

APÉNDICE

Me deshice de eso antes de correr por la puerta de una reunión, y ahora tengo tiempo para ilustrar lo que estaba diciendo arriba.

Escribí un pequeño guión de Ruby que implementa el generador congruente lineal multiplicativo de módulo principal de Schrage. Instanciado dos copias de la LCG, ambos sembrados con un valor de 1. Sin embargo, en cada iteración del bucle de salida replanteé el segundo basado en el índice de bucle. Aquí está el código:

# Implementation of a Linear Congruential Generator (LCG)
class LCG
  attr_reader :state
  M = (1 << 31) - 1    # Modulus = 2**31 - 1, which is prime

  # constructor requires setting a seed value to use as initial state
  def initialize(seed)
    reseed(seed)
  end

  # users can explicitly reset the seed.
  def reseed(seed)
    @state = seed.to_i
  end

  # Schrage''s portable prime modulus multiplicative LCG
  def value
    @state = 16807 * @state % M
    # return the generated integer value AND its U(0,1) mapping as an array
    [@state, @state.to_f / M]
  end
end

if __FILE__ == $0
  # create two instances of LCG, both initially seeded with 1
  mylcg1 = LCG.new(1)
  mylcg2 = LCG.new(1)
  puts "   default progression     manual reseeding"
  10.times do |n|
    mylcg2.reseed(1 + n)  # explicitly reseed 2nd LCG based on loop index
    printf "%d %11d %f %11d %f/n", n, *mylcg1.value, *mylcg2.value
  end
end

y aquí está la salida que produce:

   default progression     manual reseeding
0       16807 0.000008       16807 0.000008
1   282475249 0.131538       33614 0.000016
2  1622650073 0.755605       50421 0.000023
3   984943658 0.458650       67228 0.000031
4  1144108930 0.532767       84035 0.000039
5   470211272 0.218959      100842 0.000047
6   101027544 0.047045      117649 0.000055
7  1457850878 0.678865      134456 0.000063
8  1458777923 0.679296      151263 0.000070
9  2007237709 0.934693      168070 0.000078

Las columnas son el número de iteración seguido del entero subyacente generado por el LCG y el resultado cuando se escala al rango (0,1). El conjunto de columnas de la izquierda muestra la progresión natural del LCG cuando se permite que avance por sí solo, mientras que el conjunto de la derecha muestra lo que sucede cuando replacas en cada iteración.