George Marsaglia写了一个非常优秀的随机数生成器,它非常快、简单,并且周期比Mersenne Twister高得多。下面是代码和描述:
good C random number generator
我想将CMWC4096代码移植到Java,但它使用了几个无符号的数据类型,所以我不确定如何正确地做到这一点。下面是完整的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吗?当你只有带符号的数字时,这是如何工作的?
编辑:感谢大家的快速回答!对于前一亿个数字,这段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;
}
}
发布于 2008-12-29 15:48:54
任何人都可以把它移植到
上吗?当你只有带符号的数字时,这是如何工作的?
没有压力!a=18782
所以最大的t
可能还不够大,不会导致签名和未签名的问题。您必须将使用q的结果“升级”为等于32位无符号数的值,然后才能在任何地方使用它。例如,如果q是一个int
(32位有符号),那么在t=a*Q[i]+c
语句中使用它之前必须这样做,例如
t=a*(((long)Q[i])&0xffffffffL)+c
其中这个(Long) Qi )&0xffffffL)业务将Qi提升为64位#,并确保其高32位为0。(编辑:注意:这里需要0xffffffffL。Java做了错误的事情如果你使用0xffffffff,它似乎会将自己“优化”成错误的答案&如果Qi的高位是1,你会得到一个负数。)
您应该能够通过运行C++和Java中的算法来比较输出来验证这一点。
编辑:这里是它的一个镜头。我尝试在N=100000的C++和Java中运行它;它们都匹配。如果我使用了糟糕的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]=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:(比编译的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]=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());
}
}
};
发布于 2008-12-29 16:05:53
大多数情况下,不需要使用更大的数字类型来模拟Java中的无符号类型。
对于加法、减法、乘法、左移、逻辑运算、相等和转换为较小的数值类型,无论操作数是有符号的还是无符号的,结果都是一样的,被视为位模式。
若要向右移动,请使用>>表示已签名,使用>>>表示未签名。
对于签名类型转换为更大的类型,只需这样做即可。
用于从较小类型到长类型的无符号强制转换&较小类型的掩码为long。例如,短到长:s& 0xffffL。
对于从较小类型到int类型的无符号转换,使用&带有int类型的掩码。例如,byte to int: B& 0xff。
否则,就像int的情况一样,在顶部应用一个强制转换。例如,字节到短:(短) (b & 0xff)。
对于比较运算符< etc.和除法,最简单的方法是强制转换为更大的类型并在那里执行操作。但也存在其他选项,例如,在添加适当的偏移量之后进行比较。
发布于 2008-12-29 15:42:04
如果您正在用Java语言实现RNG,最好是将java.util.Random类划分为子类并覆盖受保护的next(int)方法(您的RNG就是java.util.Random的临时替代品)。下一个(Int)方法关注的是随机生成的位,而不是这些位可能代表的值。java.util.Random的其他(公共)方法使用这些位来构造不同类型的随机值。
https://stackoverflow.com/questions/397867
复制相似问题