طريقة المربع الأوسط
في الرياضيات وعلوم الحاسوب ، تُعدّ طريقة المربع الأوسط إحدى طرق توليد الأرقام شبه العشوائية . عمليًا، تُعتبر هذه الطريقة معيبة للغاية في العديد من التطبيقات العملية، نظرًا لأن دورتها عادةً ما تكون قصيرة جدًا، كما أنها تعاني من بعض نقاط الضعف الخطيرة؛ فمع تكرارها مرات كافية، ستبدأ طريقة المربع الأوسط إما بتوليد الرقم نفسه بشكل متكرر، أو ستعود إلى رقم سابق في التسلسل وتدخل في حلقة لا نهائية.
تاريخ
في الرياضيات
اخترع جون فون نيومان هذه الطريقة ، ووصفها في مؤتمر عام 1949. [ 1 ]
في محاضرته عام ١٩٤٩، قال فون نيومان مازحًا: "إن أي شخص يفكر في الطرق الحسابية لإنتاج أرقام عشوائية، فهو بالطبع في حالة إثم". وأوضح أن ما قصده هو أنه لا توجد "أرقام عشوائية" حقيقية، بل مجرد وسائل لإنتاجها، وأن "الإجراء الحسابي الصارم"، مثل طريقة المربع الأوسط، "ليس طريقة من هذا القبيل". ومع ذلك، وجد أن هذه الطرق أسرع بمئات المرات من قراءة الأرقام العشوائية "الحقيقية" من البطاقات المثقبة ، وهو ما كان ذا أهمية عملية لعمله على جهاز إينياك . ووجد أن "تدمير" متواليات المربع الأوسط عاملٌ يصب في مصلحتها، لأنه يمكن اكتشافه بسهولة: "دائمًا ما يخشى المرء ظهور دورات قصيرة غير مكتشفة". [ ١ ] وقد أبلغ نيكولاس متروبوليس عن متواليات من ٧٥٠,٠٠٠ رقم قبل "التدمير" باستخدام أرقام ٣٨ بت مع طريقة "المربع الأوسط". [ ٢ ]
يقدم كتاب The Broken Dice لإيفار إيكيلاند سردًا مطولًا لكيفية اختراع هذه الطريقة من قبل راهب فرنسيسكاني يُعرف فقط باسم الأخ إدوين في وقت ما بين عامي 1240 و 1250. [ 3 ] يُفترض أن المخطوطة مفقودة الآن، لكن خورخي لويس بورخيس أرسل إلى إيكيلاند نسخة قام بنسخها في مكتبة الفاتيكان .
يؤدي تعديل خوارزمية المربع الأوسط باستخدام متتالية ويل إلى تحسين الدورة والعشوائية. [ 4 ] [ 5 ]
الطريقة
لإنشاء سلسلة من الأرقام شبه العشوائية المكونة من n خانة، يتم إنشاء قيمة ابتدائية مكونة من n خانة ثم تربيعها، مما ينتج عنه رقم مكون من 2^ n خانة. إذا كان الناتج أقل من 2^ n خانة، تُضاف أصفار في البداية للتعويض. تُمثل الأرقام n الوسطى من الناتج الرقم التالي في السلسلة، ويُعاد كنتيجة. تُكرر هذه العملية بعد ذلك لإنشاء المزيد من الأرقام.
يجب أن تكون قيمة n زوجية لكي تنجح الطريقة ؛ فإذا كانت n فردية، فلن يكون هناك بالضرورة "أرقام وسطى n " محددة بشكل فريد للاختيار من بينها. لنأخذ المثال التالي: إذا رُبِّعَ عددٌ مكوّنٌ من 3 أرقام، فإنه يُمكن أن يُنتج عددًا مكوّنًا من 6 أرقام (مثلاً 540² = 291600). إذا كانت هناك 3 أرقام وسطى، فسيتبقى 6 - 3 = 3 أرقام لتوزيعها على يسار ويمين الرقم الأوسط. من المستحيل توزيع هذه الأرقام بالتساوي على جانبي الرقم الأوسط، وبالتالي لا توجد "أرقام وسطى". من المقبول إضافة أصفار إلى يسار الأرقام الأساسية لإنشاء عدد مكوّن من n رقمًا بقيمة زوجية (مثلاً 540 → 0540).
بالنسبة لمولد أعداد مكونة من n خانة، لا يمكن أن تتجاوز الدورة 8n . إذا كانت الخانات n الوسطى جميعها أصفارًا، فإن المولد يُخرج أصفارًا إلى ما لا نهاية. إذا كان النصف الأول من عدد في المتتالية أصفارًا، فإن الأعداد اللاحقة ستتناقص حتى تصل إلى الصفر. على الرغم من سهولة اكتشاف هذه التتابعات من الأصفار، إلا أنها تحدث بشكل متكرر جدًا بحيث لا تكون هذه الطريقة عملية. كما أن طريقة المربع الأوسط قد تتعثر عند عدد غير الصفر. عندما تكون قيمة n = 4، يحدث هذا مع القيم 0100 و2500 و3792 و7600. أما قيم البذور الأخرى فتشكل دورات متكررة قصيرة جدًا، على سبيل المثال، 0540 ← 2916 ← 5030 ← 3009. وتكون هذه الظواهر أكثر وضوحًا عندما تكون قيمة n = 2، حيث لا تولد أي من قيم البذور المئة الممكنة أكثر من 14 تكرارًا دون العودة إلى 0 أو 10 أو 50 أو 60 أو حلقة 24 ↔ 57.
مثال على التنفيذ
هنا، يتم عرض الخوارزمية في بايثون 3.12 .
رقم_البذرة = int ( إدخال ( "الرجاء إدخال رقم مكون من أربعة أرقام: \n [####] " )) الرقم = رقم_البذرة تمت رؤيته بالفعل = مجموعة () العداد = 0بينما لا يوجد رقم في قائمة الأرقام المرئية مسبقًا : ...print ( f "بدأنا بـ { seed_number } و" f "كررنا أنفسنا بعد { counter } خطوات" f " مع { number } ." )انظر أيضاً
مراجع
- 1 2 لم تتم إعادة طباعة أوراق عام 1949 حتى عام 1951. جون فون نيومان، "تقنيات مختلفة مستخدمة فيما يتعلق بالأرقام العشوائية"، في أ. س. هاوسهولدر، ج. إ. فورسايث، و هـ . هـ. جيرموند، محررين، طريقة مونت كارلو، سلسلة الرياضيات التطبيقية للمكتب الوطني للمعايير ، المجلد 12 (واشنطن العاصمة: مكتب الطباعة الحكومي الأمريكي، 1951): ص 36-38.
- ↑ دونالد إي. كنوث، فن برمجة الحاسوب، المجلد 2، الخوارزميات شبه العددية ، الطبعة الثانية (ريدينغ، ماساتشوستس: أديسون-ويسلي، 1981)، الفصل 3، القسم 3.1.
- ↑ إيفار إيكيلاند (15 يونيو 1996). النرد المكسور، وقصص رياضية أخرى عن الصدفة . مطبعة جامعة شيكاغو. ISBN 978-0-226-19992-4.
- ↑ كنوسيل، رون (2018). الأرقام العشوائية والحواسيب ( الطبعة الأولى). سبرينغر. الصفحات 13-14 .
- ↑ ويدينسكي، برنارد (أبريل 2017). "مولد الأرقام العشوائية لتسلسل ويل المربع الأوسط". arXiv : 1704.00358 [ cs.CR ].
- مولدات الأرقام شبه العشوائية
- جون فون نيومان