ما هي أفضل طريقة لإنتاج مزدوج عشوائي على POSIX؟

Question

أود الحصول على توزيع موحد في النطاق [0.0، 1.0)

إذا كان ذلك ممكنًا، فيرجى السماح للتنفيذ بالاستفادة من البايتات العشوائية من /dev/urandom.

سيكون من الجميل أيضًا أن يكون الحل الخاص بك آمن للخيط.إذا لم تكن متأكدا، يرجى الإشارة إلى ذلك.

يرى بعض الحلول فكرت بعد قراءة الإجابات الأخرى.

Answer 1

يبدو أن هذه طريقة جيدة جدًا:

unsigned short int r1, r2, r3;
// let r1, r2 and r3 hold random values
double result = ldexp(r1, -48) + ldexp(r2, -32) + ldexp(r3, -16);

يعتمد هذا على تطبيق drand48 الخاص بـ NetBSD.

Answer 2

بسيط:يحتوي المزدوج على 52 بت من الدقة بافتراض IEEE.لذا قم بإنشاء عدد صحيح عشوائي غير موقّع بحجم 52 بت (أو أكبر) (على سبيل المثال عن طريق قراءة البايتات من dev/urandom)، وقم بتحويله إلى عدد مزدوج وتقسيمه على 2^(عدد البتات التي كان عليها).

وهذا يعطي توزيعًا موحدًا عدديًا (حيث أن احتمال وجود قيمة في نطاق معين يتناسب مع النطاق) وصولاً إلى الرقم الثنائي الثاني والخمسين.

معقد:ومع ذلك، هناك الكثير من القيم المزدوجة في النطاق [0،1) والتي لا يمكن لما سبق توليدها.على وجه التحديد، لا يمكن أن تحدث نصف القيم الموجودة في النطاق [0,0.5) (تلك التي تحتوي على مجموعة البتات الأقل أهمية).لا يمكن أن تحدث ثلاثة أرباع القيم الموجودة في النطاق [0,0.25) (تلك التي تحتوي على مجموعة من 2 بتات على الأقل)، وما إلى ذلك، وصولًا إلى قيمة موجبة واحدة فقط أقل من 2^-51 ممكنة، على الرغم من كونه مزدوجًا قادرًا على تمثيل سكيليونات من هذه القيم.لذلك لا يمكن القول أنها موحدة حقًا عبر النطاق المحدد بدقة كاملة.

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

أنا يفكر الأعمال التالية.لم أدرس هذه الخوارزمية أو أختبرها بشكل خاص (كما يمكنك أن ترى من بالمناسبة أنه لا يوجد كود برمجي)، وشخصيًا لن أستخدمها دون العثور على مراجع مناسبة تشير إلى صحتها.ولكن هنا يذهب:

• ابدأ الأس عند 52 واختر عددًا صحيحًا عشوائيًا غير موقّع 52 بت (بافتراض 52 بت من الجزء العشري).
• إذا كانت البتة الأكثر أهمية في العدد الصحيح هي 0، فقم بزيادة الأس بمقدار واحد، وقم بإزاحة العدد الصحيح الأيسر بمقدار واحد، واملأ البتة الأقل أهمية ببت عشوائي جديد.
• كرر ذلك حتى تصل إلى الرقم 1 في المكان الأكثر أهمية، وإلا يصبح الأس كبيرًا جدًا بالنسبة للضعف (1023.أو ربما 1022).
• إذا وجدت 1، قم بتقسيم القيمة على 2^أس.إذا حصلت على كل الأصفار، قم بإرجاع 0 (أعلم أن هذه ليست في الواقع حالة خاصة، ولكن من المهم التأكيد على مدى احتمالية إرجاع 0 [تحرير:في الواقع قد تكون حالة خاصة - يعتمد الأمر على ما إذا كنت تريد توليد التشوهات أم لا.إذا لم يكن الأمر كذلك، فبمجرد أن يكون لديك ما يكفي من الأصفار على التوالي، فإنك تتجاهل أي شيء متبقي وتعيد 0.لكن من الناحية العملية، من غير المرجح أن يكون هذا الأمر ضئيلًا، إلا إذا كان المصدر العشوائي ليس عشوائيًا).

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

Answer 3

القراءة من الملفات هي AFAIK آمنة لمؤشر الترابط، لذا فإن استخدام fopen() للقراءة من /dev/urandom سيؤدي إلى بايتات "عشوائية حقًا".

على الرغم من احتمال وجود صعوبات محتملة، أعتقد أن أي مجموعة من هذه البايتات التي يتم الوصول إليها كعدد صحيح، مقسومة على الحد الأقصى لعدد صحيح لهذا الحجم، سوف تسفر عن قيمة الفاصلة العائمة بين 0 و 1 مع هذا التوزيع تقريبًا.

على سبيل المثال:

FILE* f = fopen("/dev/urandom", "r");
int32_t int;
fread(&int, sizeof(int32_t), 1, f);
fclose(f);
double theRandomValue = int / (double) (2 ** 32 - 1);

Answer 4

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

Answer 5

#include <stdlib.h>
printf("%f\n", drand48());

/ديف/عشوائي:

double c;
fd = open("/dev/random", O_RDONLY);
unsigned int a, b;
read(fd, &a, sizeof(a));
read(fd, &b, sizeof(b));
if (a > b)
   c = fabs((double)b / (double)a);
else
    c = fabs((double)a / (double)b);

ج هي القيمة العشوائية الخاصة بك

Answer 6

/dev/urandom ليس POSIX، وهو غير متاح بشكل عام.

الطريقة القياسية لتوليد مزدوج بشكل موحد في [0,1) هي توليد عدد صحيح في النطاق [0,2^N) وتقسيمه على 2^N.لذا اختر مولد الأرقام العشوائية المفضل لديك واستخدمه.بالنسبة لعمليات المحاكاة، فإن الخاص بي هو ميرسين الاعصار, ، لأنه سريع للغاية، لكنه لا يزال غير مرتبط بشكل جيد.في الواقع، يمكنه القيام بذلك نيابةً عنك، كما أنه يحتوي على إصدار يوفر دقة أكبر للأرقام الأصغر.عادةً ما تعطيه بذرة للبدء بها، مما يساعد على إمكانية التكرار لتصحيح الأخطاء أو إظهار نتائجك للآخرين.بالطبع، يمكنك جعل الكود الخاص بك يحصل على رقم عشوائي من /dev/urandom باعتباره البذرة إذا لم يتم تحديد رقم واحد.

لأغراض التشفير، يجب عليك استخدام إحدى مكتبات التشفير القياسية المتوفرة بدلاً من ذلك، مثل opensl) والتي ستستخدم بالفعل /dev/urandom عندما تكون متاحة.

فيما يتعلق بسلامة الخيوط، فإن معظمها لن يكون كذلك، على الأقل مع الواجهات القياسية، لذلك ستحتاج إلى إنشاء طبقة في الأعلى، أو استخدامها في سلسلة رسائل واحدة فقط.تلك التي تعتبر آمنة بالنسبة لمؤشر الترابط، تقوم بتوفير حالة تقوم بتعديلها، بحيث تقوم بدلاً من ذلك بتشغيل عدة مولدات أرقام عشوائية غير متفاعلة بشكل فعال، والتي قد لا تكون ما تبحث عنه.