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 で符号なし型をシミュレートするために、より大きな数値型を使用する必要はありません。

加算、減算、乗算、左シフト、論理演算、等価性、およびより小さい数値型へのキャストについては、オペランドが符号付きか符号なしかに関係なく、結果はビット パターンとして見て同じになります。

右にシフトするには、符号付きの場合は >>、符号なしの場合は >>> を使用します。

より大きな型への署名付きキャストの場合は、それを実行してください。

小さめタイプからロングユースまで無印キャスティング＆小さめタイプにはロングタイプのマスク付き。たとえば、短いものから長いものへ: s & 0xffffL.

小さい型から int への unsigned キャストでは、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 でアルゴリズムを実行して出力を比較することで、これを確認できるはずです。

編集：ここにショットがあります。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-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 の unsigned 型の欠如を回避するには、通常、数値をより大きな変数型に格納します (したがって、short は int に、int は long にアップグレードされます)。ここでは長い変数を使用しているため、BigInteger にステップアップする必要があります。これにより、アルゴリズムから得られる速度の向上が台無しになる可能性があります。

于 2008-12-29T15:16:59.387 に答える
0

値がオーバーフローしない限り、符号付き数値を使用できます...たとえば、Java の long は 64 ビットの符号付き整数です。ただし、このアルゴリズムの意図は 64 ビットの符号なし値を使用することであると思われます。

Java クラス ライブラリ ( BigInteger )で提供される多倍長整数を使用できます。または、独自の 64 ビット符号なし型を、最下位ワードと最上位ワードを表す 2 つの Java long を含むオブジェクトとして実装することもできます (ただし、クラスで基本的な算術演算を自分で実装する必要があります)。

于 2008-12-29T15:16:55.987 に答える