随机生成器从 C 到 Java 的端口？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/397867/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Port of Random generator from C to Java?
提问by martinus
George Marsaglia has written an excellent random number generator that is extremely fast, simple, and has a much higher period than the Mersenne Twister. Here is the code with a description:
George Marsaglia 编写了一个出色的随机数生成器，它非常快速、简单，并且周期比 Mersenne Twister 高得多。这是带有描述的代码：
good C random number generator
I wanted to port the CMWC4096 code to Java, but it uses several unsigned datatypes so I am not sure how to do this properly. Here is the full C code:
我想将 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);
}
Can anyone port this to Java? How does this work when you only have signed numbers available?
任何人都可以将其移植到 Java 吗？当您只有可用的签名号码时，这是如何工作的？
EDIT:Thanks everybody for the quick answers! For the first 100 million numbers this java code seems to produce the same result as the C code. It is 3 times faster than Java's java.util.Random.
编辑：感谢大家的快速回答！对于前 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;
}
}
采纳答案by Jason S
Can anyone port this to Java? How does this work when you only have signed numbers available?
任何人都可以将其移植到 Java 吗？当您只有可用的签名号码时，这是如何工作的？
No Stress! a=18782so the largest tcould ever be is not large enough to cause signed vs. unsigned problems. You would have to "upgrade" the result of using Q to a value equal to a 32-bit unsigned number before using it anywhere. e.g. if Q is an int(32-bit signed) then you'd have to do this before using it in the t=a*Q[i]+cstatement, e.g.
无压力！a=18782所以最大的t可能不会大到足以导致有符号与无符号问题。在任何地方使用它之前，您必须将使用 Q 的结果“升级”为等于 32 位无符号数的值。例如，如果 Q 是一个int（32 位有符号），那么你必须在t=a*Q[i]+c语句中使用它之前这样做，例如
t=a*(((long)Q[i])&0xffffffffL)+c
where this (((long)Q[i])&0xffffffffL) business promotes Q[i] to a 64-bit # and ensures its high 32 bits are 0's. (edit: NOTE: you need 0xffffffffL here. Java does the wrong thing if you use 0xffffffff, it seems like it "optimizes" itself to the wrong answer & you get a negative number if Q[i]'s high bit is 1.)
其中 (((long)Q[i])&0xffffffffL) 业务将 Q[i] 提升为 64 位#并确保其高 32 位为 0。（编辑：注意：这里你需要 0xffffffffL。如果你使用 0xffffffff，Java 会做错事，它似乎“优化”了错误的答案，如果 Q[i] 的高位是 1，你会得到一个负数。 )
You should be able to verify this by running the algorithms in C++ and Java to compare the outputs.
您应该能够通过运行 C++ 和 Java 中的算法来比较输出来验证这一点。
edit: here's a shot at it. I tried running it in C++ and Java for N=100000; they both match. Apologies if I used bad Java idioms, I'm still fairly new to Java.
编辑：这是一个镜头。我尝试在 C++ 和 Java 中运行它，N=100000；他们都匹配。抱歉，如果我使用了糟糕的 Java 习语，我对 Java 还是很陌生。
C++:
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: (slower than compiled C++ but it matches for N=100000)
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());
}
}
};
回答by Joel Marcey
Just as a quick point of reference that may (or may not) help you, I found this link:
就像一个可能（也可能不会）帮助你的快速参考点，我找到了这个链接：
回答by frankodwyer
You can use signed numbers provided the values don't overflow...for example long in java is a 64 bit signed integer. However the intent in this algorithm seems to be to use a 64 bit unsigned value, and if so I think you would be out of luck with the basic types.
如果值不会溢出，您可以使用有符号数字……例如，java 中的 long 是一个 64 位有符号整数。然而，这个算法的意图似乎是使用 64 位无符号值，如果是这样，我认为你对基本类型会不走运。
You could use the multiprecision integers provided in the java class libraries (BigInteger). Or you could implement your own 64 bit unsigned type as an Object containing two java longs to represent the least significant and most significant words (but you'd have to implement the basic arithmetic operations yourself in the class).
您可以使用 java 类库 ( BigInteger) 中提供的多精度整数。或者，您可以将自己的 64 位无符号类型实现为包含两个 java long 的对象，以表示最不重要和最重要的单词（但您必须自己在类中实现基本的算术运算）。
回答by Bill the Lizard
To get around Java's lack of unsigned types you usually store numbers in a bigger variable type (so shorts get upgraded to ints, ints to long). Since you're using long variables here, you're going to have to step up to BigInteger, which will probably wreck any speed gains that you're getting out of the algorithm.
为了解决 Java 缺少无符号类型的问题，您通常将数字存储在更大的变量类型中（因此 shorts 升级为 ints，ints 升级为 long）。由于您在这里使用长变量，因此您将不得不升级到 BigInteger，这可能会破坏您从算法中获得的任何速度提升。
回答by Dan Dyer
If you are implementing an RNG in Java, it is best to sub-class the java.util.Randomclass and over-ride the protected next(int)method (your RNG is then a drop-in replacement for java.util.Random). The next(int) method is concerned with randomly-generated bits, not what vales those bits might represent. The other (public) methods of java.util.Random use these bits to construct random values of different types.
如果您在 Java 中实现 RNG，最好对java.util.Random类进行子类化并覆盖受保护的next(int)方法（然后您的 RNG 是 java.util.Random 的直接替代品）。next(int) 方法关注随机生成的位，而不是这些位可能代表的值。java.util.Random 的其他（公共）方法使用这些位来构造不同类型的随机值。
回答by starblue
Most of the time there is no need to use larger numeric types for simulating unsigned types in Java.
大多数时候不需要使用更大的数字类型来模拟 Java 中的无符号类型。
For addition, subtraction, multiplication, shift left, the logical operations, equality and casting to a smaller numeric type it doesn't matter whether the operands are signed or unsigned, the result will be the same regardless, viewed as a bit pattern.
对于加法、减法、乘法、左移、逻辑运算、相等和转换为较小的数字类型，无论操作数是有符号还是无符号，结果都是相同的，被视为位模式。
For shifting to the right use >> for signed, >>> for unsigned.
为了转移到正确的位置，使用 >> 表示有符号，>>> 表示未签名。
For signed casting to a larger type just do it.
对于签名转换为更大的类型，只需这样做。
For unsigned casting from a smaller type to a long use & with a mask of type long for the smaller type. E.g., short to long: s & 0xffffL.
对于从较小类型到长类型的无符号转换，使用 & 对较小类型使用 long 类型的掩码。例如，短到长：s & 0xffffL。
For unsigned casting from a smaller type to an int use & with a mask of type int. E.g., byte to int: b & 0xff.
对于从较小类型到 int 的无符号转换，请使用带有 int 类型掩码的 &。例如，字节到整数：b & 0xff。
Otherwise do like in the int case and apply a cast on top. E.g., byte to short: (short) (b & 0xff).
否则，请在 int 情况下使用并在顶部应用强制转换。例如，字节到短：(short) (b & 0xff)。
For the comparison operators < etc. and division the easiest is to cast to a larger type and do the operation there. But there also exist other options, e.g. do comparisons after adding an appropriate offset.
对于比较运算符 < 等和除法，最简单的方法是转换为更大的类型并在那里执行操作。但是也存在其他选项，例如在添加适当的偏移后进行比较。
