ميناء مولد عشوائي من ج إلى جافا؟

Question

كتب جورج مارساجليا مولد رقمي عشوائي ممتاز سريع للغاية وبسيط ولديه فترة أعلى بكثير من الإعصار Mersenne. هنا هو الكود مع وصف:

جيد جيم مولد رقم عشوائي

أردت أن نفذ رمز 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);
}

يمكن لأي شخص ميناء هذا إلى جافا؟ كيف يعمل هذا عندما تكون لديك فقط أرقام توقيع فقط؟

تعديل: شكرا للجميع عن الإجابات السريعة! بالنسبة لأول 100 مليون أرقام، يبدو أن هذا رمز Java ينتج عن نفس النتيجة مثل رمز C. هو 3 مرات أسرع من Java.util.random.

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;
    }
}

Answer 1

يمكن لأي شخص ميناء هذا إلى جافا؟ كيف يعمل هذا عندما تكون لديك فقط أرقام توقيع فقط؟

لا ضغوط! a=18782 لذلك أكبر t يمكن أن يكون أبدا ليست كبيرة بما يكفي للتسبب في مشاكل موقعة مقابل غير موقعة. يجب عليك "ترقية" نتيجة استخدام Q إلى قيمة تساوي رقم غير موقعي 32 بت قبل استخدامه في أي مكان. على سبيل المثال إذا ف هو int (موقعة 32 بت) ثم عليك القيام بذلك قبل استخدامه في t=a*Q[i]+c بيان، على سبيل المثال

t=a*(((long)Q[i])&0xffffffffL)+c

حيث يكون هذا ((طالبا (طويل) س [I]) & 0xFFFFFFFL) يعزز العمل Q [i] إلى # 64 بت ويضمن أن 32 بت العالي هي 0. (تحرير: ملاحظة: لاحظ: هل تحتاج 0xFFFFFFFFL هنا. تقوم Java بالشيء الخطأ إذا كنت تستخدم 0xFFFFFFFFF، يبدو أنه "يحسن" نفسه إلى الإجابة الخاطئة وأنت تحصل على رقم سالب إذا كان Q [i] بت 1. في

يجب أن تكون قادرا على التحقق من ذلك عن طريق تشغيل الخوارزميات في C ++ و Java لمقارنة المخرجات.

تحرير: إليك تسديدة في ذلك. حاولت تشغيله في C ++ و Java for 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;
}

جافا: (أبطأ من c + 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());
        }
    }
};

Answer 2

معظم الوقت ليست هناك حاجة لاستخدام أنواع رقيقة أكبر لمحاكاة أنواع غير موقعة في جافا.

وبالإضافة إلى ذلك، فإن الطرح والضرب والانتقال إلى اليسار والعمليات المنطقية والمساواة والاستيلاء إلى نوع أصغر رقمي لا يهم ما إذا كانت المعاملات توقيعها أو غير موقعة، ستكون النتيجة هي نفسها بصرف النظر، ينظر إليها على أنها نمط قليلا.

للتحول إلى الاستخدام الصحيح >> للتوقيع، >>> لعملية غير موقعة.

للتوقيع الصب إلى نوع أكبر فقط تفعل ذلك.

من أجل الصب غير الموقعة من نوع أصغر إلى استخدام طويل ومع قناع من النوع الطويل للنوع الأصغر. على سبيل المثال، قصيرة إلى طويلة: S & 0xFFFFL.

من أجل الصب غير الموقعة من نوع أصغر إلى الاستخدام الدولي ومع قناع من النوع الدولي. على سبيل المثال، بايت إلى INT: B & 0xFF.

وإلا مثل مثل في حالة INT وقم بتطبيق المصبوب في الأعلى. على سبيل المثال، بايت إلى قصيرة: (قصير) (B & 0xFF).

بالنسبة لمشغلي المقارنة <وما إلى ذلك، فإن الأسهل هو أن يلقي إلى نوع أكبر والقيام بالعملية هناك. ولكن هناك خيارات أخرى أيضا، على سبيل المثال، قم بمقارنات بعد إضافة إزاحة مناسبة.

Answer 3

إذا كنت تقوم بتنفيذ RNG في جافا، فمن الأفضل للفئة الفرعية java.util.random. الطبقة والإفراط في ركوب المحمية التالي (int) الطريقة (RNG هي ثم استبدال في java.util.random). تشعر الطريقة التالية (INT) بالقلق بتنسيق البتات المولدة بشكل عشوائي، وليس ما يمكن أن يمثل هذه البتات. الطريقة الأخرى (العامة) java.util.random استخدم هذه البتات لبناء قيم عشوائية لأنواع مختلفة.

Answer 4

للالتفاف على افتقار Java إلى أنواع غير موقعة، تقوم عادة بتخزين الأرقام في نوع متغير أكبر (حتى يتم ترقيت السراويل القصيرة إلى Ints، Ints Long). نظرا لأنك تستخدم متغيرات طويلة هنا، فسيتعين عليك تصعيد إلى Biginteger، والتي من المحتمل أن تحطيم أي مكاسب السرعة التي تخرجها من الخوارزمية.

Answer 5

تماما كنقطة مرجعية سريعة قد تساعدك (أو لا)، وجدت هذا الرابط:

http://darksleep.com/player/javaandunsignedtypes.html.

Answer 6

يمكنك استخدام أرقام موقعة شريطة عدم تجاوز القيم ... على سبيل المثال طويل في Java هو عدد صحيح موقعة 64 بت. ومع ذلك، يبدو أن النية في الخوارزمية في هذه الخوارزمية هي استخدام قيمة غير موقعة 64 بت، وإذا كان الأمر كذلك أعتقد أنك ستستغرق الحظ مع الأنواع الأساسية.

يمكنك استخدام الأعداد الصحيحة متعددة الاستخدامات المقدمة في مكتبات Java Class (biginteger.). أو يمكنك تنفيذ نوع ما لديك 64 بت غير الموقعة ككائن يحتوي على اثنين من Java يتوق إلى كل الكلمات الأقل أهمية والأهمية (ولكن عليك تنفيذ العمليات الحسابية الأساسية بنفسك في الفصل).