Port of Zufallsgenerator von C nach Java?
https://stackoverflow.com/questions/397867
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
George Marsaglia hat einen ausgezeichneten Zufallszahlengenerator geschrieben, die extrem schnell, einfach, und hat eine viel höhere Periode als der Mersenne-Twister. Hier ist der Code mit einer Beschreibung:
ich zu portieren wollte den CMWC4096 Code zu Java, aber es nutzt mehrere unsigned Datentypen, so bin ich nicht sicher, wie diese richtig zu tun. Hier ist der vollständige C-Code:
/* 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);
}
Kann jemand Port dies zu Java? Wie funktionierts, wenn Sie nur Zahlen verfügbar unterzeichnet haben?
EDIT: Vielen Dank allen für die schnellen Antworten! Für die ersten 100 Millionen Nummern dieses Java-Code scheint das gleiche Ergebnis wie der C-Code zu erzeugen. Es ist 3-mal schneller als 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 < 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;
}
}
Lösung
Kann jemand Port dies zu Java? Wie funktioniert diese Arbeit, wenn Sie nur unterzeichnet haben verfügbar Zahlen?
No Stress! a=18782 so der größte t immer nicht groß sein könnte genug gegen unsigned Probleme unterzeichnet zu verursachen. Sie müssten „Upgrade“ das Ergebnis von Q auf einen Wert gleich einem 32-Bit-Zahl ohne Vorzeichen verwenden, bevor es überall verwenden. z.B. wenn Q ein int (32-Bit unterzeichnet), dann würden Sie haben, dies zu tun, bevor es in der t=a*Q[i]+c Anweisung, z.B.
t=a*(((long)Q[i])&0xffffffffL)+c
, wo diese (((long) Q [i]) & 0xffffffffL) Unternehmen Q fördert [i] zu einem 64-Bit # und sorgt für ihre hohe 32 Bits 0en. (Edit:. HINWEIS: Sie müssen 0xffffffffL hier Java tut das Falsche, wenn Sie verwenden 0xffffffff, scheint es, wie es „optimiert“ sich auf die falsche Antwort und Sie erhalten eine negative Zahl, wenn Q [i] 's High-Bit 1 ist. )
Sie sollten in der Lage sein, dies zu überprüfen, indem die Algorithmen in C ++ und Java läuft die Ausgaben zu vergleichen.
edit: hier ist ein Schuss auf ihn. Ich habe versucht, es in C ++ und Java für N = 100000 läuft; sie beide übereinstimmen. Entschuldigt, wenn ich schlecht Java Idiome verwendet, ich bin noch ziemlich neu in 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: (langsamer als C ++ kompiliert, aber es passt für 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());
}
}
};
Andere Tipps
Die meiste Zeit gibt es keine Notwendigkeit größere numerische Typen zu verwenden, ist für nicht signierte Typen in Java zu simulieren.
Für Addition, Subtraktion, Multiplikation, nach links verschoben, die logischen Operationen, Gleichheit und Gießen auf einen kleineren numerischen Typ es spielt keine Rolle, ob die Operanden signiert oder unsigniert, das Ergebnis wird das gleiche, unabhängig, betrachtet als Bitmuster sein.
nach rechts Nutzung Verschiebung >> für unterzeichnet, >>> für unsigned.
zu einem größeren Typ signed Gießen es nur tun.
Für unsigned Gießen von einem kleineren Typ auf eine lange Nutzung und mit einer Maske vom Typ long für den kleineren Typen. Z. B. kurz bis lang. S & 0xffffL
Für unsigned Gießen von einem kleineren Typ in einer int Verwendung & mit einer Maske vom Typ int. Z. B. Byte in int. B & 0xff
Ansonsten wie im int Fall tun und eine Besetzung auf Anwendung. Z. B. Byte zu kurz. (Kurz) (b & 0xff)
Für die Vergleichsoperator
Wenn Sie eine RNG in Java implementieren, ist es am besten, um die Unterklasse der java.util.Random Klasse und over-ride die geschützten nächste (int) Methode (Ihre RNG ist dann ein Drop-in-Ersatz für java.util.Random). Der nächste (int) Methode befasst sich mit zufällig erzeugten Bits, nicht das, was diese Bits vales darstellen könnten. Die andere (public) Methoden der java.util.Random diese Bits verwenden, um Zufallswerte verschiedenen Typen zu konstruieren.
Um Java Mangel an unsigned-Typen erhalten Sie in der Regel speichern Zahlen in einem größeren Variablentyp (so erhalten Shorts Ints aufgerüstet, ints zu lang). Da Sie lange Variablen hier verwendet sind, sind Sie gehen zu müssen, um BigInteger zu intensivieren, was wahrscheinlich keine Geschwindigkeitsgewinne zunichte machen wird, dass Sie aus dem Algorithmus zu bekommen.
Wie schnell ein Bezugspunkt, den Sie können (oder auch nicht) helfen, ich diesen Link gefunden:
Sie können die Zahlen mit Vorzeichen verwenden, sofern die Werte nicht überlaufen ... zum Beispiel lange in Java ist eine 64-Bit-Ganzzahl mit Vorzeichen. Doch die Absicht in diesem Algorithmus, um einen 64-Bit-Wert ohne Vorzeichen zu verwenden, zu sein scheint, und wenn ja, ich glaube, Sie kein Glück mit den Grundtypen sein würden.
Sie könnten die ganzen Zahlen in den mehrfach Java-Klassenbibliotheken zur Verfügung gestellt verwenden ( BigInteger ). Oder Sie könnten Ihren eigenen 64-Bit-Typen ohne Vorzeichen implementieren als ein Objekt zwei Java-Long-Positionen enthält, die am wenigsten signifikanten darstellen und bedeutendste Worte (aber Sie würden die grundlegenden arithmetischen Operationen selbst in der Klasse implementieren).
