أكورن (مولد الأرقام العشوائية)

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
الموسوعة الحرة

تُعد مولدات ACORN أو " الأرقام العشوائية المتطابقة المضافة " عائلة قوية من مولدات الأرقام العشوائية الزائفة ( PRNGs) لتسلسلات الأرقام العشوائية الزائفة الموزعة بشكل منتظم ، والتي تم تقديمها في عام 1989 ولا تزال صالحة في عام 2019، أي بعد ثلاثين عامًا .

تم تقديم برنامج ACORN بواسطة RSWikramaratna، [ 1 ] وقد صُمم في الأصل للاستخدام في عمليات المحاكاة الإحصائية الجيولوجية والجيوفيزيائية باستخدام طريقة مونت كارلو ، وتم توسيعه لاحقًا للاستخدام على الحواسيب المتوازية . [ 2 ]

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

فوائد

تتمثل المزايا الرئيسية لبرنامج ACORN في بساطة المفهوم والبرمجة، وسرعة التنفيذ، وطول الفترة الزمنية، والتقارب المثبت رياضياً. [ 3 ]

يمكن توسيع الخوارزمية، إذا تطلبت التطبيقات المستقبلية أرقامًا عشوائية زائفة "ذات جودة أفضل" وفترة أطول، وذلك بزيادة الرتبة والمعامل حسب الحاجة. بالإضافة إلى ذلك، أظهرت الأبحاث الحديثة أن مولدات ACORN تجتاز جميع الاختبارات في مجموعة اختبارات TestU01 ، الإصدار الحالي 1.2.3، مع اختيار مناسب للمعاملات وبعض القيود البسيطة جدًا على اختيار التهيئة؛ ومن الجدير بالذكر، كما أشار مؤلفو TestU01، أن بعض مولدات الأرقام العشوائية الزائفة شائعة الاستخدام تفشل فشلاً ذريعًا في بعض الاختبارات.

تتميز خوارزمية ACORN بسهولة تنفيذها باستخدام الحساب الصحيح الدقيق ، في لغات برمجة مختلفة، باستخدام بضعة أسطر فقط من التعليمات البرمجية. [ 4 ] يُفضل استخدام الحساب الصحيح على الحساب الحقيقي بتردد 1 في العرض الأصلي، لأن الخوارزمية قابلة للتكرار، وتنتج نفس التسلسل تمامًا على أي جهاز وبأي لغة برمجة، [ 2 ] كما أن دوريتها قابلة للإثبات رياضيًا.

لم يحظَ مولد الأرقام العشوائية ACORN بالانتشار الواسع الذي حظيت به بعض مولدات الأرقام العشوائية الأخرى، على الرغم من تضمينه في روتينات مكتبة NAG العددية المكتوبة بلغة Fortran و C. [ 5 ] وقد طُرحت أسبابٌ عديدةٌ لذلك. [ 6 ] ومع ذلك، لا تزال الأبحاث النظرية والتجريبية جارية لتبرير استمرار استخدام ACORN كمولد أرقام عشوائية قوي وفعال.

الشروط

أظهر برنامج ACORN أداءً ممتازًا في الاختبارات، وذلك عند استخدام المعايير المناسبة. [ 6 ] ومع ذلك، لم يثبت أن برنامج ACORN بصيغته الحالية مناسب للتشفير .

لم تُجرَ سوى تقييمات نقدية قليلة بشأن برنامج ACORN. أحد هذه التقييمات، [ 7 ]، يُحذّر من وجود خلل في تهيئة دالة acorni() عند استخدام مكتبة GSLIB للنمذجة والمحاكاة الإحصائية الجغرافية، [ 8 ] ويقترح حلاً بسيطاً لهذه المشكلة. ويتمثل الحل في زيادة قيمة المعامل modulus لتجنب هذه المشكلة. [ 9 ] [ 6 ]

يشير مرجع موجز آخر إلى ACORN ببساطة إلى أن "... مولد ACORN المقترح مؤخرًا [...] هو في الواقع مكافئ لـ MLCG مع المصفوفة A بحيث يكون a~ = 1 لـ i 2 j، aq = 0 خلاف ذلك" [ 10 ] ولكن التحليل لم يتم التطرق إليه أكثر.

إن ACORN ليس هو نفسه ACG (المولد التوافقي الإضافي) ولا ينبغي الخلط بينهما - يبدو أن ACG قد تم استخدامه لنوع مختلف من LCG ( المولد التوافقي الخطي ) الذي وصفه كنوت (1997).

التاريخ والتطور

في البداية، تم تنفيذ ACORN في الحساب الحقيقي في FORTRAN77، [ 1 ] وقد تبين أنه يعطي سرعة تنفيذ وأداء إحصائي أفضل من مولدات التوافق الخطي ومولدات تشيبيشيف.

في عام 1992، تم نشر نتائج أخرى، [ 11 ] تطبيق مولد الأرقام العشوائية الزائفة ACORN في الحساب الصحيح الدقيق الذي يضمن إمكانية إعادة الإنتاج عبر منصات ولغات مختلفة، وذكر أنه بالنسبة للحساب الحقيقي ذي الدقة التعسفية، من الممكن إثبات تقارب تسلسل ACORN إلى k-distributed مع زيادة الدقة.

في عام 2000، تم ذكر أن ACORN حالة خاصة من مولد متعدد التكرار (وبالتالي، من مولد المصفوفة)، [ 2 ] وتم إثبات ذلك رسميًا في عام 2008 [ 12 ] في ورقة بحثية نشرت أيضًا نتائج اختبارات Diehard التجريبية والمقارنات مع NAG LCG ( مولد التوافق الخطي ).

في عام 2009، تم تقديم برهان رسمي [ 4 ] على التقارب النظري لـ ACORN إلى التوزيع k لمعامل M=2 m عندما يؤول m إلى اللانهاية (كما أشير إليه سابقًا في عام 1992 [ 11 ] )، إلى جانب النتائج التجريبية التي تدعم ذلك، والتي أظهرت أن مولدات ACORN قادرة على اجتياز جميع الاختبارات في مجموعة TESTU01 القياسية [ 13 ] لاختبار مولدات الأرقام العشوائية الزائفة (عند اختيار معلمات الترتيب والمعامل المناسبة).

منذ عام 2009، أُدرج برنامج ACORN ضمن مكتبات NAG ( مجموعة الخوارزميات العددية ) المكتوبة بلغة FORTRAN وC، [ 14 ] [ 5 ] إلى جانب برامج توليد الأرقام العشوائية الزائفة الأخرى المعروفة. يعمل هذا التطبيق لبرنامج ACORN مع قيم كبيرة للمعامل والرتبة، وهو متاح للباحثين للتنزيل. [ 5 ]

تم تطبيق برنامج ACORN أيضًا في مكتبة GSLIB للنمذجة والمحاكاة الإحصائية الجغرافية. [ 8 ]

في الآونة الأخيرة، عُرض برنامج ACORN في أبريل 2019 خلال جلسة ملصقات في مؤتمر حول الخوارزميات العددية للعلوم الحاسوبية عالية الأداء [ 15 ] في الجمعية الملكية بلندن، وفي يونيو 2019 في ندوة لمجموعة التحليل العددي في المعهد الرياضي بجامعة أكسفورد [ 16 ] . وقد ذُكر أن الأداء الإحصائي للبرنامج أفضل من بعض المولدات الشائعة الاستخدام (بما في ذلك Mersenne Twister MT19937 ) ومقارب لأفضل الطرق المتاحة حاليًا، وأن مولدات ACORN أثبتت جدارتها في اجتياز جميع اختبارات TestU01 بنجاح، بينما لم تجتز بعض المولدات الأخرى، بما في ذلك Mersenne Twister، جميع هذه الاختبارات. يمكن الاطلاع على الملصق والعرض التقديمي على الرابط [ 9 ] .

مثال على الكود

تم نشر المثال التالي في Fortran77 في عام 2008 [ 12 ] والذي يتضمن مناقشة حول كيفية التهيئة  :

دالة الدقة المزدوجة ACORNJ ( XDUMMY ) C C تنفيذ Fortran لمولد الأرقام العشوائية ACORN C من رتبة أقل من أو تساوي 120 (يمكن الحصول على رتب أعلى C عن طريق زيادة قيمة المعامل MAXORD) و C معامل أقل من أو يساوي 2^60. C C بعد التهيئة المناسبة للكتلة المشتركة /IACO2/ C كل استدعاء لـ ACORNJ يُولّد متغيرًا واحدًا مُستمدًا من C توزيع منتظم على الفترة 1. C IMPLICIT DOUBLE PRECISION ( A - H , O - Z ) PARAMETER ( MAXORD = 120 , MAXOP1 = MAXORD + 1 ) COMMON / IACO2 / KORDEJ , MAXJNT , IXV1 ( MAXOP1 ), IXV2 ( MAXOP1 ) DO 7 I = 1 , KORDEJ IXV1 ( I + 1 ) = ( IXV1 ( I + 1 ) + IXV1 ( I )) IXV2 ( I + 1 ) = ( IXV2 ( I + 1 ) + IXV2 ( I )) IF ( IXV2 ( I + 1 ). GE . MAXJNT ) THEN IXV2 ( I + 1 ) = IXV2 ( I + 1 ) - MAXJNT IXV1 ( I + 1 ) = IXV1 ( I + 1 ) + 1 ENDIF IF ( IXV1 ( I + 1 ). GE . MAXJNT ) IXV1 ( I + 1 ) = IXV1 ( I + 1 )- MAXJNT  7 متابعة ACORNJ = ( DBLE ( IXV1 ( KORDEJ + 1 )) 1 + DBLE ( IXV2 ( KORDEJ + 1 )) / MAXJNT ) / MAXJNT نهاية العودة

مراجع

  1. 1 2 ويكراماراتنا، آر إس (1989). ACORN - طريقة جديدة لتوليد متواليات من الأرقام شبه العشوائية الموزعة بشكل منتظم. مجلة الفيزياء الحاسوبية. 83. 16-31.
  2. 1 2 3 R.S. Wikramaratna، توليد الأرقام العشوائية الزائفة للمعالجة المتوازية - نهج التقسيم، SIAM News 33 (9) (2000).
  3. ↑ "مفهوم وخوارزمية ACORN" . acorn.wikramaratna.org/concept.html .
  4. 1 2 ر.س. ويكراماراتنا، نتائج التقارب النظرية والتجريبية لمولدات الأرقام العشوائية التوافقية الجمعية، مجلة الرياضيات الحسابية والتطبيقية (2009)، doi : 10.1016/j.cam.2009.10.015
  5. 1 2 3 " g05 مقدمة الفصل : مكتبة NAG، الإصدار 26" . www.nag.co.uk. 
  6. 1 2 3 "التهيئة والنقد لـ ACORN" . acorn.wikramaratna.org/critique.html .
  7. ^ أورتيز، جوليان وفي. دويتش، كلايتون. (2014). توليد أرقام عشوائية باستخدام الجوز: ملاحظة تحذيرية.
  8. 1 2 GsLib حزمة مفتوحة المصدر مخصصة للإحصاء الجغرافي، شفرة المصدر مكتوبة بلغة فورتران 77 و90.
  9. 1 2 "مراجع وروابط ACORN" . acorn.wikramaratna.org/references.html .
  10. ^ لوكوير، بيير. (1990). أرقام عشوائية للمحاكاة.. Commun. ايه سي ام. 33. 85-97. 10.1145/84537.84555.
  11. 1 2 R.S. Wikramaratna، الخلفية النظرية لمولد الأرقام العشوائية ACORN، التقرير AEA-APS-0244، AEA Technology، Winfrith، Dorset، المملكة المتحدة، 1992.
  12. 1 2 ويكراماراتنا، روي (2008). "مولد الأرقام العشوائية التوافقي الجمعي - حالة خاصة من مولد تكراري متعدد" . مجلة الحوسبة والرياضيات التطبيقية . 216 (2): 371-387 . Bibcode : 2008JCoAM.216..371W . doi : 10.1016/j.cam.2007.05.018 .
  13. ↑ P. L'Ecuyer, R. Simard, TestU01: مكتبة AC للاختبار التجريبي لمولدات الأرقام العشوائية، ACM Trans. on Math. Software 33 (4) (2007) المقالة 22.
  14. ↑ NAG، مكتبة فورتران مارك 22 لمجموعة الخوارزميات العددية (NAG)، مجموعة الخوارزميات العددية المحدودة، أكسفورد، المملكة المتحدة، 2009.
  15. ↑ "الخوارزميات العددية للعلوم الحاسوبية عالية الأداء" . الجمعية الملكية .
  16. ↑ "مولد الأرقام العشوائية التوافقية الجمعية (ACORN) - متواليات شبه عشوائية موزعة بشكل جيد في k-أبعاد" . معهد الرياضيات بجامعة أكسفورد .