Porto de gerador aleatório de C para Java?
https://stackoverflow.com/questions/397867
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
George Marsaglia escreveu um excelente gerador de números aleatórios que é extremamente rápido, simples, e tem um período muito maior do que o Mersenne Twister. Aqui está o código com uma descrição:
boa C gerador de números aleatórios
Eu queria portar o código CMWC4096 para Java, mas ele usa vários tipos de dados não assinados por isso não estou certo de como fazer isso corretamente. Aqui está o 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);
}
Can isso para Java? Como isso funciona quando você só assinaram números disponíveis?
EDIT: Obrigado a todos pelas respostas rápidas! Durante os primeiros 100 milhões de números este código Java parece produzir o mesmo resultado que o código C. É 3 vezes mais rápido do 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;
}
}
Solução
porta de qualquer umCan isso para Java? como funciona este trabalho quando você só assinaram números disponíveis?
No Stress! a=18782 assim o maior t poderia ser não é grande o suficiente para causar assinado vs. problemas não assinados. Você teria que "upgrade" o resultado de usar Q para um valor igual a um número não assinado de 32 bits antes de usá-lo em qualquer lugar. por exemplo. Se Q é um int (32-bit assinado), então você teria que fazer isso antes de usá-lo na declaração t=a*Q[i]+c, por exemplo,
t=a*(((long)Q[i])&0xffffffffL)+c
onde esta (((long) Q [i]) & 0xffffffffL) business promove Q [i] para um de 64 bits # e garante seus altos 32 bits são 0s. (Edit: NOTA:. Você precisa 0xffffffffL aqui Java faz a coisa errada, se você usar 0xffffffff, parece que "otimiza" próprio para a resposta errada e você recebe um número negativo se Q [i] 's alta bit é 1. )
Você deve ser capaz de verificar isso executando os algoritmos em C ++ e Java para comparar as saídas.
Edit: Aqui está um tiro nele. Tentei executá-lo em C ++ e Java para N = 100000; ambos jogo. Desculpas se eu usei maus idiomas Java, eu ainda sou bastante novo para 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: (mais lento do que C ++ compilado, mas corresponde 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());
}
}
};
Outras dicas
Na maioria das vezes, não há necessidade de usar tipos numéricos maiores para simular tipos não assinados em Java.
Para adição, subtração, multiplicação, desvio à esquerda, as operações lógicas, igualdade e lançando a um tipo numérico menor não importa se os operandos são assinados ou não assinados, o resultado será o mesmo, independentemente, visto como um padrão de bits.
Para mudar para o uso correto >> para assinado, >>> for assinado.
Para assinado lançando a um tipo maior apenas fazê-lo.
Para fundição sem sinal de um tipo menor para um uso prolongado e com uma máscara do tipo long para o tipo menor. Por exemplo, a curto e longo:. S & 0xffffL
Para fundição sem sinal de um tipo menor para um uso int & com uma máscara do tipo int. Por exemplo, byte para int:. B & 0xff
Caso contrário, fazer como no caso int e aplicar um elenco em cima. Por exemplo, byte a curto:. (Short) (b & 0xff)
Para os operadores de comparação
Se você estiver implementando um RNG em Java, o melhor é sub-classe do java.util.Random classe e sobrepor-se a protegida próxima (int) método (o RNG é então um substituto para java.util.Random). O método next (int) está preocupado com pedaços gerado aleatoriamente, não o que vales esses bits pode representar. Os outros (públicos) métodos de java.util.Random usar estes bits para a construção de valores aleatórios de diferentes tipos.
Para contornar a falta de tipos sem sinal de Java você costuma armazenar números em um tipo de variável maior (assim calções se atualizado para ints, ints e longo). Desde que você está usando variáveis ??longas aqui, você vai ter que intensificar a BigInteger, o que provavelmente irá destruir todos os ganhos de velocidade que você está ficando fora do algoritmo.
Assim como um rápido ponto de referência que pode (ou não) ajudá-lo, eu encontrei este link:
Você pode usar assinados desde que os valores não estouro ... por exemplo longo em Java é um inteiro assinado de 64 bits. No entanto, a intenção neste algoritmo parece ser a de usar um 64 valor sem sinal mordeu, e se assim eu acho que você estaria fora de sorte com os tipos básicos.
Você pode usar os números inteiros multiprecision fornecidos nas bibliotecas de classe java ( BigInteger ). Ou você pode implementar seu próprio 64 bits tipo não assinado como um objeto contendo dois longs java para representar as palavras menos significativos e mais significativos (mas você teria que implementar as operações aritméticas básicas-se na classe).
