المزيف مولد في لغة التجميع

Question

أحتاج المزيف مولد رقم خوارزمية عن المجمع البرنامج المخصصة في الحال ، أنا أفضل خوارزمية بسيطة.بيد أنني لا أستطيع استخدام خارجي المكتبة.

ما هو جيد ، بسيطة المزيف مولد رقم خوارزمية التجميع ؟

Answer 1

من السهل واحد هو مجرد اختيار اثنين كبيرة النسبية الأعداد a و b ثم نضع بضرب رقم عشوائي من قبل وإضافة ب.استخدام المشغل نمطية للحفاظ على انخفاض بت ك رقم عشوائي والحفاظ على القيمة الكاملة عن التكرار التالي.

هذه الخوارزمية كما هو معروف الخطية congruential مولد.

Answer 2

المجلد 2 من فن برمجة الكمبيوتر لديه الكثير من المعلومات حول المزيف عدد جيل.الخوارزميات هي أظهر في المجمع, حيث يمكنك أن ترى نفسك التي هي أبسط في المجمع.

إذا كنت يمكن أن تصل إلى خارجي المكتبة أو كائن الملف ، على الرغم من أنه سيكون أفضل رهان.ثم يمكنك الربط ، على سبيل المثال ، ميرسين الاعصار.

علما أن معظم المزيف عدد المولدات لا آمنة التشفير, حتى إذا كنت بحاجة إلى تأمين توليد رقم عشوائي, كنت بحاجة إلى أن ننظر إلى أبعد من الخوارزميات الأساسية (وربما ينبغي الاستفادة من نظام التشغيل الخاصة تشفير Api).

Answer 3

كود بسيط اختبار, لا تستخدم مع التشفير

من اختبار برامج الكمبيوتر, صفحة 138

مع 32 بت الرياضيات لا تحتاج العملية MOD 2^32

RNG = (69069*RNG + 69069) MOD 2^32

Answer 4

جيدا منذ أن كنت لم أر إشارة إلى حسن البالغ من العمر الخطية ردود الفعل التحول السجل أنشر بعض SSE الجوهرية على أساس C-رمز.فقط completenes.لقد كتبت هذا الشيء بضعة أشهر إلى شحذ لي SSE-المهارات مرة أخرى.

#include <emmintrin.h>

static __m128i LFSR;

void InitRandom (int Seed)
{
  LFSR = _mm_cvtsi32_si128 (Seed);
}

int GetRandom (int NumBits)
{
  __m128i seed = LFSR;
  __m128i one  = _mm_cvtsi32_si128(1);
  __m128i mask; 
  int i;

  for (i=0; i<NumBits; i++)
  {

    // generate xor of adjecting bits
    __m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));

    // generate xor of feedback bits 5,6 and 62,61
    __m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
                                    _mm_srli_epi64(temp,61));

    // Mask out single bit: 
    NewBit = _mm_and_si128 (NewBit, one);

    // Shift & insert new result bit:
    seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
  }

  // Write back seed...
  LFSR = seed;

  // generate mask of NumBit ones.
  mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);

  // return random number:
  return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}

ترجمة هذه التعليمة البرمجية إلى المجمع تافهة.مجرد استبدال إينترينسيكس مع تعليمات SSE و إضافة حلقة من حوله.

راجع للشغل - تسلسل هذا الرمز genreates يكرر بعد 4.61169 E+18 الأرقام.وهذا هو الكثير أكثر مما ستحصل عليه عن طريق رئيس الوزراء الأسلوب و 32 بت الحساب.إذا بسطه انها أسرع أيضا.

Answer 5

@jjrv
ما تصفه هو في الواقع الخطية congrential مولد.الأكثر عشوائية بت أعلى بت.للحصول على رقم من 0..N-1 تتضاعف قيمة N (32 بت 32 بت إعطاء 64 بت) واستخدام عالية 32 بت.

يجب أن لا مجرد استخدام أي عدد a (مضاعف تتقدم من القيمة الكاملة المقبل) ، أرقام الموصى بها في كانوث (الجدول 1 القسم 3.3.4 TAOCP المجلد 2 1981) هي 1812433253, 1566083941, 69069 و 1664525.

يمكنك فقط اختيار أي عدد فردي من أجل ب.(إضافة).

Answer 6

لماذا لا تستخدم خارجي المكتبة???أن عجلة القيادة قد اخترع بضع مئات المرات ، فلماذا نفعل ذلك مرة أخرى ؟

إذا كنت بحاجة إلى تنفيذ RNG نفسك هل تحتاج إلى إنتاج الأرقام على الطلب-أيهل تنفيذ راند (وظيفة) - أو هل تحتاج إلى إنتاج جداول الأرقام العشوائية-على سبيل المثالالذاكرة الاختبار ؟

هل تحتاج إلى RNG هذا هو التشفير القوة ؟ كم من الوقت يجب أن أذهب قبل أن يكرر?هل لديك على الاطلاق, إيجابي ضمان توزيع موحد من جميع بت ؟

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

• تبدأ مع التعسفي 4 بايت المستمر على البذور الخاصة بك.
• حوسبة 32-بت لجنة حقوق الطفل من تلك 4 بايت.يعطيك المقبل 4 بايت
• تغذية راجعة تلك 4 بايت في CRC32 الخوارزمية ، كما لو كانوا المرفقة.على CRC32 من 8 بايت القيمة التالية.
• كرر طالما تريد.

هذا يأخذ القليل جدا من التعليمات البرمجية (على الرغم من أنك تحتاج إلى طاولة crc32 وظيفة) و لديه القليل جدا من الدولة ، ولكن psuedorandom دفق إخراج جدا دورة طويلة من الوقت قبل أن يكرر.كما أنها لا تتطلب SSE على المعالج.وعلى افتراض لديك CRC32 وظيفة يدوية ، تافهة لتنفيذ.

Answer 7

باستخدام masm615 إلى مترجم:

delay_function macro
    mov cx,0ffffh
.repeat
    push cx
    mov cx,0f00h
    .repeat
        dec  cx
        .until cx==0
    pop cx
    dec cx
    .until cx==0
endm

random_num macro
   mov  cx,64    ;assum we want to get 64 random numbers
   mov  si,0

get_num:    
   push cx
   delay_function    ;since cpu clock is fast,so we use delay_function
   mov  ah,2ch  
   int  21h
   mov  ax,dx     ;get clock 1/100 sec
   div  num       ;assume we want to get a number from 0~num-1
   mov  arry[si],ah   ;save to array you set
   inc  si
   pop  cx
   loop get_num   ;here we finish the get_random number 

Answer 8

كما كنت ربما يمكن أن تحاكي تحويل تسجيل مع XOR مجموع العناصر بين منفصلة بت ، والتي سوف تعطيك شبه عشوائي تسلسل الأرقام.

Answer 9

الخطية congruential (X = AX+C mod M) PRNG قد يكون فكرة جيدة لتعيين عن المجمع الحال كما والطلاب سوف تضطر إلى التعامل مع تحمل بت المتوسطة الفأس نتائج أكثر من 2^31 و حساب معامل.إذا كنت طالب فهي إلى حد ما واضحة لتنفيذها في المجمع و قد يكون ما المحاضر في الاعتبار.