مولد فيبوناتشي المتأخر

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

يمكن وصف متتالية فيبوناتشي بالعلاقة التكرارية التالية :

${\displaystyle S_{n}=S_{n-1}+S_{n-2}}$

وبالتالي، فإن الحد الجديد هو مجموع الحدين الأخيرين في المتتالية. ويمكن تعميم ذلك على المتتالية التالية:

${\displaystyle S_{n}\equiv S_{nj}\star S_{nk}{\pmod {m}},0<j<k}$

في هذه الحالة، يكون الحد الجديد مزيجًا من أي حدين سابقين. عادةً ما يكون m قوةً للعدد 2 ( m = 2^ ^M )، وغالبًا ما يكون 2 ^{^32} أو 2^ ⁶⁴ .${\displaystyle \star }$يشير المعامل إلى عملية ثنائية عامة . قد تكون هذه العملية جمعًا أو طرحًا أو ضربًا أو عملية XOR (العملية الحصرية الثنائية ). نظرية هذا النوع من المولدات معقدة نوعًا ما، وقد لا يكفي مجرد اختيار قيم عشوائية لـ j و k . كما أن هذه المولدات حساسة جدًا لعملية التهيئة.

تستخدم مولدات هذا النوع k من كلمات الحالة (إنها "تتذكر" آخر k قيمة).

إذا كانت العملية المستخدمة هي الجمع، يُوصف المولد بأنه مولد فيبوناتشي المتأخر الجمعي (ALFG)، وإذا كانت العملية المستخدمة هي الضرب، يُوصف بأنه مولد فيبوناتشي المتأخر الضربي (MLFG)، وإذا كانت العملية المستخدمة هي XOR، يُسمى مسجل إزاحة التغذية الراجعة المعمم ثنائي النقر (GFSR). تُعد خوارزمية ميرسين تويستر أحد أنواع مسجل إزاحة التغذية الراجعة المعمم (GFSR). ويرتبط مسجل إزاحة التغذية الراجعة المعمم (GFSR) أيضًا بمسجل إزاحة التغذية الراجعة الخطية (LFSR).

تعتمد الفترة القصوى لمولدات فيبوناتشي المتأخرة على العملية الثنائية${\displaystyle \star }$إذا استُخدم الجمع أو الطرح، فإن أقصى دورة هي ( ^2k - 1) × ^{2M - 1.} أما إذا استُخدم الضرب، فإن أقصى دورة هي ( ^2k - 1) × ^{2M - 3} ، أي ربع دورة حالة الجمع. وإذا استُخدمت عملية XOR الثنائية، فإن أقصى دورة هي 2k ^- 1.

لكي يحقق المولد هذه الفترة القصوى، فإن متعددة الحدود هي:

ص = س ^ك + س ^ي + 1

يجب أن تكون بدائية على الأعداد الصحيحة modulo 2. وقد تم نشر قيم j و k التي تحقق هذا القيد في الأدبيات.

توجد قائمة أخرى بالقيم المحتملة لـ j و k في الصفحة 29 من المجلد 2 من كتاب فن برمجة الحاسوب :

(24، 55)، (38، 89)، (37، 100)، (30، 127)، (83، 258)، (107، 378)، (273، 607)، (1029، 2281)، (576، 3217)، (4187، 9689)، (7083، 19937)، (9739، 23209)

لاحظ أن الأرقام الأصغر لها فترات قصيرة (يتم توليد عدد قليل فقط من الأرقام "العشوائية" قبل تكرار الرقم "العشوائي" الأول وإعادة بدء التسلسل).

في حال استخدام الجمع، يُشترط أن تكون إحدى القيم k الأولى المختارة لتهيئة المولد فردية. أما في حال استخدام الضرب، فيُشترط أن تكون جميع القيم k الأولى فردية، وأن تكون إحداها على الأقل ±3 mod 8. ^{[ 3 ]}

وقد أشير إلى أن النسب الجيدة بين j و k هي تقريبًا النسبة الذهبية . ^{[ 4 ]}

في ورقة بحثية حول مسجلات الإزاحة ذات الأربع نقاط، يشير روبرت م. زيف ، في معرض حديثه عن مولدات الترددات الخطية التي تستخدم عامل XOR، إلى أنه "من المعروف الآن على نطاق واسع أن هذه المولدات، ولا سيما تلك التي تستخدم قواعد نقطتين مثل R(103, 250)، تعاني من عيوب خطيرة. وقد لاحظ مارساجليا أداءً سيئًا للغاية مع R(24, 55) والمولدات الأصغر حجمًا، ونصح بعدم استخدام هذا النوع من المولدات على الإطلاق. ... تكمن المشكلة الأساسية لمولدات نقطتين R(a, b) في وجود ارتباط ثلاثي النقاط مدمج بينها."${\displaystyle x_{n}}$،${\displaystyle x_{na}}$، و${\displaystyle x_{nb}}$، ببساطة من خلال المولد نفسه ... في حين أن هذه الارتباطات موزعة على الحجم${\displaystyle p=max(a,b,c,\ldots )}$من الواضح أن هذه الأخطاء، حتى وإن كانت متعلقة بالمولد نفسه، قد تؤدي إلى أخطاء كبيرة. ^{[ 5 ]} يشير هذا فقط إلى مولد الأرقام العشوائي القياسي حيث يعتمد كل رقم جديد في التسلسل على رقمين سابقين. وقد ثبت أن مولد الأرقام العشوائي ثلاثي النقرات يُزيل بعض المشكلات الإحصائية مثل فشل اختبارات تباعد أعياد الميلاد واختبارات الثلاثية المعممة. ^{[ 4 ]}

قد يبدو تطبيق بسيط بلغة البرمجة C كما هو موضح أدناه. يستخدم هذا التطبيق كلمات 64 بت، ودورته ( ²⁶⁰⁷ - 1) × ²⁶³

#define R (607) #define S (273)#include <stdint.h>uint64_t X [ R ];uint64_t gen_rand () { static int j = S - 1 , k = R - 1 ; uint64_t r ; r = X [ k ] = X [ k ] + X [ j -- ]; k -- ; if ( j < 0 ) j = R - 1 ; else if ( k < 0 ) k = R - 1 ; return r ; }

• يستخدم برنامج Freeciv مولد فيبوناتشي المتأخر مع {j = 24، k = 55} لمولد الأرقام العشوائية الخاص به.
• تتضمن مكتبة Boost تطبيقًا لمولد فيبوناتشي المتأخر.
• تم تضمين محرك توليد فيبوناتشي المتأخر، Subtract with carry ، في مكتبة C++11 .
• تقوم قاعدة بيانات أوراكل بتنفيذ هذا المولد في حزمة DBMS_RANDOM الخاصة بها (المتوفرة في أوراكل 8 والإصدارات الأحدث).

تتضمن صفحة ويكيبيديا " قائمة مولدات الأرقام العشوائية " قائمة بمولدات أرقام عشوائية زائفة أخرى، بما في ذلك بعض المولدات ذات الجودة الإحصائية الأفضل:

• مولد التوافق الخطي
• مولد ACORN
• ميرسين تويستر
• Xoroshiro128+
• سمكة (شفرة)
• رمح
• تشفير VIC

نحو مولد أرقام عشوائية شامل ، بقلم ج. مارساجليا، أ. زمان