Puerto de generador aleatorio de C a Java?
https://stackoverflow.com/questions/397867
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
George Marsaglia ha escrito un excelente generador de números aleatorios que es extremadamente rápido, sencillo, 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 aportar el código CMWC4096 a Java, sino que utiliza varios tipos de datos sin signo así que no estoy seguro de cómo hacer esto correctamente. Aquí está el código completo C:
/* 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);
}
Can puerto de esto a nadie a Java? ¿Cómo funciona esto cuando sólo haya firmado números disponibles?
EDIT: Gracias a todos por las respuestas rápidas! Durante los primeros 100 millones de números de este código java parece producir el mismo resultado que el código C. Es 3 veces más rápido que java.util.Random de Java.
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;
}
}
Solución
Can puerto de esto a nadie a Java? Cómo este trabajo cuando sólo haya firmado números disponibles?
No Stress! a=18782 por lo que el más grande t podría nunca ser no es lo suficientemente grande como para causar problemas firmado vs sin firmar. Usted tendría que "actualizar" el resultado de la utilización de Q a un valor igual a un número sin signo de 32 bits antes de utilizarlo en cualquier lugar. p.ej. si Q es un int (32 bits con signo) entonces lo que tiene que hacer esto antes de utilizarlo en la declaración t=a*Q[i]+c, por ejemplo,
t=a*(((long)Q[i])&0xffffffffL)+c
donde esta (((largo) Q [i]) y 0xffffffffL) negocio promueve Q [i] a un 64-bit # y asegura su alto 32 bits son 0 de. (Edit: NOTA:. Necesita 0xffffffffL aquí Java no hace lo que si se utiliza 0xffffffff, parece que "optimiza" sí a la respuesta equivocada y se obtiene un número negativo si Q [i] 's alta bit es 1. )
Usted debe ser capaz de verificar esto mediante la ejecución de los algoritmos en C ++ y Java para comparar las salidas.
Edit: aquí hay un tiro en él. Probé ejecutarlo en C ++ y Java para N = 100.000; que ambos coincidan. Disculpas si he usado malas expresiones Java, sigo siendo 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 compilado C ++, pero que coincide para N = 100.000)
// 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());
}
}
};
Otros consejos
La mayoría de las veces no hay necesidad de utilizar grandes tipos numéricos para la simulación de los tipos sin signo en Java.
En suma, resta, multiplicación, desplazamiento a la izquierda, las operaciones lógicas, la igualdad y la fundición a un tipo numérico menor no importa si los operandos son firmados o sin firmar, el resultado será el mismo, independientemente, visto como un patrón de bits.
Para cambiará al uso correcto de >> firmado, >>> para firmar.
Para firmado fundición a un tipo más grande acaba de hacerlo.
Para colar sin signo de un tipo más pequeño para un uso prolongado y con una máscara de tipo long para el tipo más pequeño. Por ejemplo, corto a largo:. S y 0xffffL
Para colada sin signo de un tipo más pequeño para un uso int & con una máscara de tipo int. Por ejemplo, byte a int:. B & 0xff
En caso contrario hacer como en el caso int y aplicar un yeso en la parte superior. Por ejemplo, byte a corto:. (Corto) (b & 0xff)
Para los operadores de comparación
Si va a implementar un generador de números aleatorios en Java, lo mejor es la subclase java.util.Random clase y pasar por encima de la protegido siguiente int) método ((su generador de números aleatorios es entonces una gota en el reemplazo para java.util.Random). El método siguiente (int) se ocupa de bits generados de forma aleatoria, no lo Vales esos bits pueden representar. Los otros (públicos) métodos de java.util.Random utilizan estos bits para construir valores aleatorios de diferentes tipos.
Para evitar la falta de tipos sin signo se almacenan por lo general los números en un tipo de variable más grande de Java (por lo cortos se actualizan a enteros, enteros o largo). Dado que está utilizando variables de tipo long aquí, vas a tener que intensificar a BigInteger, que probablemente destruir cualquier ganancia de velocidad que usted está saliendo del algoritmo.
Así como un punto de referencia temporal de referencia que puede (o no) le ayudará, me encontré con este enlace:
Puede utilizar firmados siempre que los valores no se desborden ... por ejemplo larga en Java es un entero de 64 bits. Sin embargo, la intención de este algoritmo parece ser el uso de un valor sin signo de 64 bits, y si es así creo que estaría fuera de suerte con los tipos básicos.
Se puede usar los números enteros multiprecision proporcionados en las bibliotecas de clases de Java ( BigInteger ). O se podría implementar su propio 64 bits tipo sin signo como un objeto que contiene dos largos de Java para representar las palabras menos significativos y más significativos (pero usted tendría que poner en práctica las operaciones aritméticas básicas a sí mismo en la clase).
