Porta del generatore casuale da C a Java?

George Marsaglia ha scritto un eccellente generatore di numeri casuali estremamente veloce, semplice e con un periodo molto più alto rispetto al Mersenne Twister. Ecco il codice con una descrizione:

buon generatore di numeri casuali C

Volevo portare il codice CMWC4096 su Java, ma utilizza diversi tipi di dati non firmati quindi non sono sicuro di come farlo correttamente. Ecco il codice C completo:

/* choose random initial c>32); x = t + c; if (x < c) { x++; c++; } return (Q[i] = r - x); } 

Qualcuno può portarlo su Java? Come funziona quando hai solo numeri firmati disponibili?

EDIT: Grazie a tutti per le risposte rapide! Per i primi 100 milioni di numeri questo codice java sembra produrre lo stesso risultato del codice C. È 3 volte più veloce di Java 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 >> 32; long x = (t + c) & 0xffffffffL; if (x < c) { ++x; ++c; } long v = 0xfffffffeL - x; Q[i] = v; return (int) v; } } 

    Qualcuno può portarlo su Java? Come funziona quando hai solo numeri firmati disponibili?

    Niente stress! a=18782 quindi la t più grande mai essere non è abbastanza grande da causare problemi con segno e senza segno. Dovresti “aggiornare” il risultato dell’utilizzo di Q ad un valore uguale a un numero senza segno a 32 bit prima di utilizzarlo ovunque. per esempio se Q è un int (firmato a 32 bit), allora dovresti farlo prima di usarlo nell’istruzione t=a*Q[i]+c , ad es.

     t=a*(((long)Q[i])&0xffffffffL)+c 

    dove questo business (((lungo) Q [i]) & 0xffffffffL) promuove Q [i] in un # 64-bit e garantisce che i suoi 32 bit alti siano 0. (modifica: NOTA: hai bisogno di 0xffffffffL qui. Java fa la cosa sbagliata se usi 0xffffffff, sembra che “si ottimizzi” sulla risposta sbagliata e tu ottenga un numero negativo se il bit più alto di Q [i] è 1. )

    Dovresti essere in grado di verificarlo eseguendo gli algoritmi in C ++ e Java per confrontare gli output.

    modifica: ecco un colpo. Ho provato a farlo funzionare in C ++ e Java per N = 100000; entrambi corrispondono Mi scuso se ho usato cattivi idiomi Java, sono ancora abbastanza nuovo per Java.

    C ++:

     // marsaglia2003.cpp #include  #include  // 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 1) n = atoi(argv[1]); for (int i = 0; i < n; ++i) { printf("%08x\n", generator.next()); } return 0; } 

    java: (più lento del C ++ compilato ma corrisponde a 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=0) // tweak to treat x as unsigned { x++; c++; } return (Q[i]=rx); } 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()); } } }; 

    La maggior parte delle volte non è necessario utilizzare tipi numerici più grandi per simulare i tipi non firmati in Java.

    Per addizione, sottrazione, moltiplicazione, spostamento a sinistra, operazioni logiche, uguaglianza e cast ad un tipo numerico più piccolo non importa se gli operandi sono firmati o non firmati, il risultato sarà lo stesso indipendentemente, visto come un pattern di bit.

    Per spostarsi a destra usare >> per firma, >>> per non firmato.

    Per il casting firmato con un tipo più grande, fallo e basta.

    Per la trasmissione senza segno da un tipo più piccolo a un uso prolungato e con una maschera di tipo lungo per il tipo più piccolo. Ad esempio, da breve a lungo: s & 0xffffL.

    Per casting senza segno da un tipo più piccolo ad un uso int e con una maschera di tipo int. Ad esempio, da byte a int: b & 0xff.

    Altrimenti fai come nel caso int e applica un cast sopra. Ad esempio, byte to short: (short) (b & 0xff).

    Per gli operatori di confronto

    Se stai implementando un RNG in Java, è meglio sottoclassare la class java.util.Random e scavalcare il metodo protetto successivo (int) (il tuo RNG è quindi una sostituzione drop-in per java.util.Random ). Il prossimo metodo (int) riguarda i bit generati casualmente, non ciò che vales questi bit potrebbero rappresentare. Gli altri metodi (pubblici) di java.util.Random usano questi bit per build valori casuali di tipi diversi.

    Per aggirare la mancanza di tipi non firmati di Java, di solito si memorizzano i numeri in un tipo di variabile più grande (in modo che i cortometraggi vengano aggiornati a inte, interi a lungo). Dato che stai usando le variabili lunghe qui, dovrai passare a BigInteger, che probabilmente distruggerà qualsiasi guadagno di velocità che stai ottenendo dall’algoritmo.

    Proprio come un rapido punto di riferimento che può (o non può) aiutarti, ho trovato questo link:

    http://darksleep.com/player/JavaAndUnsignedTypes.html

    È ansible utilizzare numeri firmati purché i valori non siano eccessivi … ad esempio long in java è un intero con segno a 64 bit. Tuttavia, l’intento in questo algoritmo sembra essere quello di utilizzare un valore senza segno a 64 bit, e in tal caso penso che si sarebbe sfortunati con i tipi di base.

    È ansible utilizzare gli interi multiprecision forniti nelle librerie di classi java ( BigInteger ). Oppure potresti implementare il tuo tipo di unsigned a 64 bit come Object contenente due java long per rappresentare le parole meno significative e più significative (ma dovresti implementare le operazioni aritmetiche di base nella class).