19

George Marsaglia 编写了一个出色的随机数生成器，它非常快速、简单，并且比 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;
    }
}
4

5 回答 5

46

大多数时候不需要使用更大的数字类型来模拟 Java 中的无符号类型。

对于加法、减法、乘法、左移、逻辑运算、相等和强制转换为较小的数字类型，无论操作数是有符号还是无符号，结果都是相同的，被视为位模式。

为了转移到正确的使用 >> 有符号， >>> 无符号。

对于将签名转换为更大的类型，只需执行此操作。

用于从较小类型到长期使用的无符号转换，并且对于较小类型使用 long 类型的掩码。例如，从短到长：s & 0xffffL。

对于从较小类型到 int 的无符号转换，使用 & 带有 int 类型的掩码。例如，字节到 int：b & 0xff。

否则，请在 int 案例中使用并在顶部应用强制转换。例如，字节到短：（短）（b & 0xff）。

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

于 2008-12-29T16:05:53.483 回答
14

任何人都可以将它移植到Java吗？当您只有可用的签名号码时，这是如何工作的？

无压力！a=18782所以最大t的可能不够大，不会导致有符号和无符号的问题。您必须将使用 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 中运行算法来比较输出来验证这一点。

编辑：这是一个镜头。我尝试在 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]=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-29T15:48:54.067 回答
5

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

于 2008-12-29T15:42:04.360 回答
2

为了解决 Java 缺乏无符号类型的问题，您通常将数字存储在更大的变量类型中（因此shorts 升级为int，int 升级为long）。由于您在这里使用长变量，因此您将不得不升级到 BigInteger，这可能会破坏您从算法中获得的任何速度增益。

于 2008-12-29T15:16:59.387 回答
0

只要值不会溢出，您就可以使用带符号的数字……例如，java 中的 long 是一个 64 位有符号整数。但是，此算法的意图似乎是使用 64 位无符号值，如果是这样，我认为您对基本类型会不走运。

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

于 2008-12-29T15:16:55.987 回答