从C语言转换到Java的随机数生成器端口？

Question

乔治·马萨利亚编写了一款非常快速、简单且具有比 Mersenne Twister 更高周期的优秀随机数生成器。以下是带有说明的代码：

好的 C 随机数生成器

我想将 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吗？当你只有有符号数可用时，这个怎么工作呢？

编辑：感谢大家的快速回答！对于前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;
    }
}

- martinus

Answer 1

大多数情况下，在Java中模拟无符号类型时不需要使用较大的数字类型。

对于加法、减法、乘法、左移、逻辑操作、相等性和向较小的数字类型转换，无论操作数是有符号还是无符号，结果都将是相同的，以位模式表示。

对于向右移位，请使用“>>”表示有符号，“>>>”表示无符号。

对于从有符号类型向较大类型的转换只需进行即可。

对于从较小类型到长整型的无符号转换，请使用较小类型的long型掩码与“&”。 例如，short to long: s & 0xffffL。

对于从较小类型到int的无符号转换，请使用int型掩码与“&”。 例如，byte to int: b & 0xff。

否则像int一样，再应用转换。 例如，byte to short: (short) (b & 0xff)。

对于比较运算符“<”等和除法，最简单的方法是将其转换为更大的类型并在那里执行操作。 但也存在其他选项，例如在添加适当的偏移量后进行比较。

- starblue

---

好的总结。虽然你忘记了一个关键操作：将类型转换为更大的类型。（例如，将32位转换为64位#）。你需要使用掩码对结果进行与运算，以便将原始值解释为“无符号”。 - Jason S

我当时没有看到这个问题，但你是对的。没有掩码时，强制转换是有符号的，有掩码时则为无符号。通常情况下，您甚至不需要显式地进行强制转换，因为使用适当值的&运算符可以实现扩展。 - starblue

Answer 2

有没有人能将其移植到 Java？当只有带符号的数字可用时，这是如何工作的？

无压力！a=18782 因此，最大的 t 可能不足以引起带符号 vs. 无符号问题。在任何地方使用 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中运行算法来验证此内容以比较输出结果。

编辑：这是一份尝试。我尝试了 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());
        }
    }
};

- Jason S

Answer 3

如果您正在Java中实现RNG，最好是继承java.util.Random类并重写受保护的next(int)方法（然后您的RNG就是java.util.Random的替代品）。 next（int）方法与随机生成的位有关，而不是这些位可能表示的值。 java.util.Random的其他（公共）方法使用这些位来构造不同类型的随机值。

- Dan Dyer

Answer 4

为了解决Java没有无符号类型的问题，通常会将数字存储在更大的变量类型中（因此short会升级为int，int会升级为long）。由于这里使用的是long变量，你需要升级到BigInteger，这可能会破坏你从算法中获得的任何速度优势。

- Bill the Lizard

---

另一方面，使用RNG的类当然也会使用Java的有符号类型，因此如果需要完整的无符号长范围，则RNG可能不是唯一具有速度问题的地方。 - Henning

您对原始C代码中long的解释是不正确的。它指的是32位整数类型，对应于Java中的int。 - Nayuki

Answer 5

注意：在你的 C 代码中，我推断 long 是 32 位宽度，long long 是 64 位宽度。

以下是我将该代码移植到 Java 的最小更改方式：

/* choose random initial 0<=c<809430660 and */
/* 4096 random 32-bit integers for Q[]      */
int[] Q = new int[4096];
int c = 362436;
int i = 4095;

int CMWC4096() {
    long a = 18782;
    int r = 0xfffffffe;
    i = (i + 1) & 4095;
    long t = a * Q[i] + c;
    c = (int)(t >>> 32);
    int x = (int)(t + c);
    if (0 <= x && x < c) {
        x++;
        c++;
    }
    return (Q[i] = r - x);
}

- Nayuki

Answer 6

如果值不会溢出，您可以使用带符号的数字...例如，在Java中，long是一个64位的有符号整数。然而，在这个算法中的意图似乎是使用一个64位的无符号值，如果是这样的话，我认为你会在基本类型上运气不佳。

您可以使用Java类库中提供的多精度整数（BigInteger）。或者，您可以实现自己的64位无符号类型作为一个对象，其中包含两个Java longs来表示最低有效字和最高有效字（但您必须自己在类中实现基本算术运算）。

- frankodwyer

---

令人印象深刻的老链接。我认为在 Java 1.1 正式发布之前，java.lang.Bignum 类不存在，它变成了 java.math.BigInteger。 - Dan Dyer

哎呀 - 你说得对！这说明我已经很久没有使用MP ints了。我现在会修复它。 - frankodwyer

你对原始的C代码中long的解释是错误的。它指的是32位整数类型，对应于Java中的int。 - Nayuki

有趣的是，java.math.Bignum 的旧链接显示它是 BigInteger 和 BigDecimal 的融合。我很感激最终的设计，因为它更清晰易懂。此外，我经常使用 BigInteger，但很少使用 BigDecimal，所以当使用 BigInteger 时不需要关注 BigDecimal 方法，这很好。 - Nayuki