repetir - Puerto de generador aleatorio de C a Java?
metodo random java (6)
George Marsaglia ha escrito un excelente generador de números aleatorios que es extremadamente rápido, simple y tiene un período mucho más alto que el Mersenne Twister. Aquí está el código con una descripción:
buen generador de números aleatorios C
Quería portar el código CMWC4096 a Java, pero usa varios tipos de datos sin firmar, así que no estoy seguro de cómo hacerlo correctamente. Aquí está el código C completo:
/* choose random initial c<809430660 and */
/* 4096 random 32-bit integers for Q[] */
static unsigned long Q[4096],c=362436;
unsigned long CMWC4096(void) {
unsigned long long t, a=18782LL;
static unsigned long i=4095;
unsigned long x,r=0xfffffffe;
i = (i+1) & 4095;
t = a*Q[i] + c;
c = (t>>32);
x = t + c;
if (x < c) {
x++;
c++;
}
return (Q[i] = r - x);
}
¿Alguien puede portar esto a Java? ¿Cómo funciona esto cuando solo tienes números firmados disponibles?
EDIT: ¡ Gracias a todos por las respuestas rápidas! Para los primeros 100 millones de números, este código Java parece producir el mismo resultado que el código C. Es 3 veces más rápido que Java''s Java.util.Random.
public class ComplimentaryMultiplyWithCarryRandom {
/**
* Choose 4096 random 32-bit integers
*/
private long[] Q;
/**
* choose random initial c<809430660
*/
private long c = 362436;
private int i;
public ComplimentaryMultiplyWithCarryRandom() {
Random r = new Random(1);
Q = new long[4096];
// TODO initialize with real random 32bit values
for (int i = 0; i < 4096; ++i) {
long v = r.nextInt();
v -= Integer.MIN_VALUE;
Q[i] = v;
}
i = 4095;
}
int next() {
i = (i + 1) & 4095;
long t = 18782 * Q[i] + c;
c = t >>> 32;
long x = (t + c) & 0xffffffffL;
if (x < c) {
++x;
++c;
}
long v = 0xfffffffeL - x;
Q[i] = v;
return (int) v;
}
}
¿Alguien puede portar esto a Java? ¿Cómo funciona esto cuando solo tienes números firmados disponibles?
¡Sin estrés! a=18782 por lo que la t más grande que alguna vez podría ser no es lo suficientemente grande como para causar problemas con signo o sin signo. Tendría que "actualizar" el resultado de usar Q a un valor igual a un número sin signo de 32 bits antes de usarlo en cualquier lugar. por ejemplo, si Q es una int (firma de 32 bits), entonces tendría que hacer esto antes de usarlo en la sentencia t=a*Q[i]+c , por ejemplo
t=a*(((long)Q[i])&0xffffffffL)+c
donde este negocio (((largo) Q [i]) & 0xffffffffL) promueve Q [i] a un # de 64 bits y asegura que sus 32 bits altos son 0. (edite: NOTA: necesita 0xffffffffL aquí. Java hace lo incorrecto si usa 0xffffffff, parece que se "optimiza" a la respuesta incorrecta y obtiene un número negativo si Q [i] tiene un bit alto 1. )
Debería poder verificar esto ejecutando los algoritmos en C ++ y Java para comparar las salidas.
editar: aquí hay una oportunidad. Intenté ejecutarlo en C ++ y Java para N = 100000; ambos coinciden. Disculpas si utilicé malas expresiones idiomáticas en Java, todavía soy bastante nuevo en Java.
C ++:
// marsaglia2003.cpp
#include <stdio.h>
#include <stdlib.h> // for atoi
class m2003
{
enum {c0=362436, sz=4096, mask=4095};
unsigned long Q[sz];
unsigned long c;
short i;
public:
m2003()
{
// a real program would seed this with a good random seed
// i''m just putting in something that makes the output interesting
for (int j = 0; j < sz; ++j)
Q[j] = j + (j << 16);
i = 4095;
c = c0;
}
unsigned long next()
{
unsigned long long t, a=18782LL;
unsigned long x;
unsigned long r=0xfffffffe;
i = (i+1)&mask;
t=a*Q[i]+c;
c=(unsigned long)(t>>32);
x=(unsigned long)t + c;
if (x<c)
{
x++;
c++;
}
return (Q[i]=r-x);
}
};
int main(int argc, char *argv[])
{
m2003 generator;
int n = 100;
if (argc > 1)
n = atoi(argv[1]);
for (int i = 0; i < n; ++i)
{
printf("%08x/n", generator.next());
}
return 0;
}
java: (más lento que C ++ compilado pero coincide para N = 100000)
// Marsaglia2003.java
import java.util.*;
class Marsaglia2003
{
final static private int sz=4096;
final static private int mask=4095;
final private int[] Q = new int[sz];
private int c=362436;
private int i=sz-1;
public Marsaglia2003()
{
// a real program would seed this with a good random seed
// i''m just putting in something that makes the output interesting
for (int j = 0; j < sz; ++j)
Q[j] = j + (j << 16);
}
public int next()
// note: returns a SIGNED 32-bit number.
// if you want to use as unsigned, cast to a (long),
// then AND it with 0xffffffffL
{
long t, a=18782;
int x;
int r=0xfffffffe;
i = (i+1)&mask;
long Qi = ((long)Q[i]) & 0xffffffffL; // treat as unsigned 32-bit
t=a*Qi+c;
c=(int)(t>>32);
// because "a" is relatively small this result is also small
x=((int)t) + c;
if (x<c && x>=0) // tweak to treat x as unsigned
{
x++;
c++;
}
return (Q[i]=r-x);
}
public static void main(String args[])
{
Marsaglia2003 m2003 = new Marsaglia2003();
int n = 100;
if (args.length > 0)
n = Integer.parseInt(args[0]);
for (int i = 0; i < n; ++i)
{
System.out.printf("%08x/n", m2003.next());
}
}
};
Para evitar la falta de tipos sin firmar de Java, generalmente almacena los números en un tipo de variable más grande (por lo que los cortos se actualizan a ints, ints a long). Dado que está utilizando variables largas aquí, tendrá que intensificar a BigInteger, lo que probablemente arruine cualquier ganancia de velocidad que esté obteniendo del algoritmo.
Puede usar números con signo siempre que los valores no se desborden ... por ejemplo, long in java es un entero con signo de 64 bits. Sin embargo, la intención de este algoritmo parece ser utilizar un valor sin signo de 64 bits, y si es así, creo que no tendrías suerte con los tipos básicos.
Puede usar los enteros de multiprecision proporcionados en las bibliotecas de la clase java ( BigInteger ). O bien, podría implementar su propio tipo sin signo de 64 bits como un Objeto que contenga dos largos de Java para representar las palabras menos significativas y más significativas (pero usted mismo tendría que implementar las operaciones aritméticas básicas en la clase).
Si está implementando un RNG en Java, es mejor subclasificar la clase java.util.Random y anular el método next (int) protegido (su RNG es entonces un reemplazo directo para java.util.Random ) El siguiente (int) método se refiere a los bits generados aleatoriamente, no a los valores que esos bits puedan representar. Los otros métodos (públicos) de java.util.Random usan estos bits para construir valores aleatorios de diferentes tipos.
Solo como un punto de referencia rápido que puede (o no) ayudarlo, encontré este enlace:
La mayoría de las veces no es necesario utilizar tipos numéricos más grandes para simular tipos sin firmar en Java.
Para suma, resta, multiplicación, desplazamiento a la izquierda, operaciones lógicas, igualdad y conversión a un tipo numérico más pequeño, no importa si los operandos están firmados o no, el resultado será el mismo independientemente, visto como un patrón de bits.
Para cambiar al uso correcto >> para firmado, >>> para sin firmar.
Para un casting firmado a un tipo más grande solo hazlo.
Para el envío sin signo de un tipo más pequeño a un uso prolongado y con una máscara de tipo largo para el tipo más pequeño. Por ejemplo, corto a largo: s & 0xffffL.
Para el envío sin firmar de un tipo más pequeño a un uso int y con una máscara de tipo int. Por ejemplo, byte a int: b y 0xff.
De lo contrario, haga clic en Me gusta en el caso int y aplique un molde en la parte superior. Ej., Byte a corto: (corto) (b & 0xff).
Para los operadores de comparación <etc. y división, lo más fácil es convertir a un tipo más grande y hacer la operación allí. Pero también existen otras opciones, por ejemplo hacer comparaciones después de agregar una compensación adecuada.