随机生成器从C到Java的端口?

George Marsaglia写了一个很好的随机数发生器,它的速度非常快,简单,而且比Mersenne Twister的周期要长得多。 这里是描述的代码:

好C随机数发生器

我想将CMWC4096代码移植到Java,但它使用了几个无符号的数据types,所以我不知道如何正确地做到这一点。 这是完整的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); } 

任何人都可以移植到Java? 当您只有可用的签名号码时,这是如何工作的?

编辑:谢谢大家的快速解答! 对于前面的1亿个数字,这个java代码似乎产生了和C代码一样的结果。 它比Java的java.util.Random快3倍。

 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; } } 

任何人都可以移植到Java? 当您只有可用的签名号码时,这是如何工作的?

无压力! a=18782所以最大的t可能不足以导致签名和未签名的问题。 在任何地方使用Q之前,必须将使用Q的结果“升级”到等于32位无符号数的值。 例如,如果Q是一个int (32位有符号),那么在使用t=a*Q[i]+c语句之前,你必须这样做,例如

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

(((long)Q [i])&0xffffffffL)业务将Q [i]推广到64位#并确保其高32位为0。 (编辑:注意:这里你需要0xffffffffL。如果你使用0xffffffff,Java做错误的事情,它似乎是“优化”自己到错误的答案,如果Q [i]的高位是1,你得到一个负数。 )

您应该能够通过在C ++和Java中运行algorithm来比较输出来validation这一点。

编辑:这是一个镜头。 我试着在C ++和Java中运行N = 100000; 他们都匹配。 如果我使用错误的Java成语抱歉,我对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]=rx); } }; 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:(比编译的C ++慢,但匹配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]=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()); } } }; 

大多数情况下,不需要使用较大的数字types来模拟Java中的无符号types。

对于加法,减法,乘法,左移,逻辑运算,相等和转换为更小的数字types,无论操作数是有符号还是无符号都无关紧要,结果将是相同的。

要转移到正确的使用>>为签名,>>>为无符号。

对于签署铸造到一个更大的types只是做到这一点。

对于从较小types到较长types的无符号转换,以及较小types的较长types的转换。 例如,从短到长:s&0xffffL。

对于从较小types到int的无符号转换,使用&带有types为int的掩码。 例如,字节到int:b&0xff。

否则,像在int情况下做一个顶部施放。 例如,字节要短:(short)(b&0xff)。

对于比较运算符<etc.和division,最简单的就是投入一个更大的types并在那里进行操作。 但是也有其他select,例如在添加适当的偏移之后进行比较。

如果你正在用Java实现一个RNG,最好是对java.util.Random类进行子类化,并覆盖protected的next(int)方法(你的RNG就是java.util.Random的一个embedded式替代品)。 下一个(int)方法涉及随机生成的位,而不是这些位可能代表的值。 java.util.Random的其他(public)方法使用这些位来构造不同types的随机值。

为了解决Java缺乏无符号types的问题,你通常将数字存储在一个更大的variablestypes中(所以空格被升级为整数,整数变长)。 既然你在这里使用了很长的variables,你将不得不加速到BigInteger,这可能会破坏你从algorithm中获得的任何速度收益。

就像可能(或不可能)帮助你的一个快速参考点,我find了这个链接:

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

你可以使用带符号的数字,只要值不溢出…例如,在java中,long是一个64位有符号整数。 然而这个algorithm的意图似乎是使用一个64位的无符号值,如果是这样的话,我认为你的基本types会运气不好。

您可以使用java类库( BigInteger )中提供的多精度整数。 或者你可以实现自己的64位无符号types作为包含两个Java long的对象来表示最不重要和最重要的单词(但是你必须在类中自己实现基本的算术运算)。