متد middle square

در ریاضیات، روش میان-مربع (به انگلیسی: middle-square) که به اشتباه «مربعِ میانی» نیز گفته می‌شود، روشی برای تولید اعداد شبه تصادفی است. این روش، چندان کارآمد و مناسب نیست؛ زیرا دورۀ تناوب دنبالۀ اعداد تولید شده در آن نسبتاً کوتاه است، و دنباله همیشه به صفر همگرا می‌شود.

این روش توسط جان فُون نُویمان و نیکولاس متروپلیس در سال ۱۹۴۶ در آزمایشگاه‌های لُس‌آلامُوس برای شبیه‌سازی برخورد نوترون، به عنوان قسمتی از پروژه منهتن، توسعه یافت.

این روش در ابتدا بدین صورت عمل می‌کرد: برای تولید یک دنباله از اعداد شبه تصادفی ۴ رقمی، یک عدد ۴ رقمی دلخواه انتخاب شده، به توان ۲ رسانده می‌شود و به‌این‌ترتیب یک عدد ۸ رقمی به‌دست می‌آید. اگر نتیجه کمتر از ۸ رقم داشت، باید با اضافه کردن صفر به اول آن، می‌توان کمبود رقم آن را جبران کرد. ۴ رقم وسط این عدد، مشخص‌کننده رقم بعدی دنباله است. این فرایند ادامه می‌یابد تا اعداد تصادفی بیشتری تولید شوند.

برای یک مولد اعداد $n$ رقمی، دوره تناوب نمی‌تواند بیش از $8^{n}$ باشد. اگر ۴ رقم میانی صفر باشند، مولد تا آخر صفر برمی‌گرداند. اگر نیمه اول یک عدد در دنباله صفر باشد، اعداد بعدی به سمت صفر کاهش می‌یابند. روش میان-مربعی در اعداد غیر از صفر هم به همین ترتیب به دام می‌افتد. مثلاً برای n = ۴، این اتفاق برای اعداد ۰۱۰۰، ۲۵۰۰، ۳۷۹۲ و ۷۶۰۰ رخ می‌دهد. باقی مقادیر اولیه (seeds)، چرخه تکرار کوتاهی را می‌سازند، برای مثال ۰۵۴۰ → ۲۹۱۶ → ۵۰۳۰ → ۳۰۰۹. این پدیده‌ها در حالتی که $n=2$ باشد بیشتر دیده می‌شوند، چون هیچ‌یک از ۱۰۰ حالت ممکن برای مقدار اولیه، بیش از ۱۴ پیمایش را بدون رجوع به ۰، ۱۰، ۵۰، ۶۰ یا حلقه ۲۴ ↔ ۵۷ می‌سازد.

فُون نُویمان در سال ۱۹۴۹ گفته است «هرکس که روش‌های تولید ارقام تصادفی را مطرح کند، حقیقتاً گناهکار است»، و منظورش این بود که، هیچ «عدد تصادفی» معقولی وجود ندارد، تنها آن‌ها را به وسیلهٔ یک روش محاسباتی دقیق می‌سازند. با این حال، وی این روش‌ها را صدها بار سریع‌تر از مطالعه اعداد تصادفی واقعی کارت‌های پانچ می‌دانست، که اهمیت زیادی برای کار ENIAC داشت. نیکولاس متروپلیس دنباله‌هایی با ۷۵۰٬۰۰۰ رقم را (قبل آنکه به اعداد مخرب برسد)، به وسیلهٔ ۳۸ بیت با استفاده از همین روش گزارش کرده‌است.

افسانه

کتاب تاس شکسته (The Broken Dice) نوشته Ivar Ekeland شرح می‌دهد که چگونه این روش توسط یک راهب صومعه فرانسیسکن، ملقب به «برادر ادوین»، در زمانی بین ۱۲۴۰ تا ۱۲۵۰ میلادی اختراع شد. ظاهراً نسخه خطی آن در حال حاضر گم شده‌است، اما خورخه لوییس بورخس یک کپی از آن در کتابخانۀ واتیکان را برای Ekeland ارسال کرد. اگرچه گفته شده‌ که این داستان واقعی‌ست، اما بررسی‌ها نشان داده‌اند که این داستان، تخیل بورخس بوده‌است.

دنبالۀ وِیل (Weyl)

کاستی‌های روش میان-مربع را می‌توان به وسیلهٔ اجرا کردن آن به روش دنبالۀ ویل برطرف کرد. دنبالۀ ویل از همگرایی به صفر جلوگیری می‌کند. پیاده‌سازی آن در زبان C چنین است:

#include <stdint.h>

uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;

inline static uint32_t msws() {
   x *= x;
   x += (w += s);
   return x = (x>>32) | (x<<32);
}

دنباله ویل (w += s) به مربع x اضافه شده‌است. مقدار میانی (middle) با ۳۲ بیت شیفت دادن به سمت راست استخراج می‌شود.

یک بسته نرم‌افزاری آزاد در اینجا قابل دسترس است.

منابع

1. The 1949 papers were not reprinted until 1951. John von Neumann, “Various techniques used in connection with random digits,” in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds. , Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12 (Washington, D.C. : U.S. Government Printing Office, 1951): pp. 36–38.
2. Donald E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, 2nd edn. (Reading, Mass. : Addison-Wesley, 1981), ch. 3, section 3.1.
3. Pierre L’Ecuyer & Richard Simard (2007), "TestU01: A Software Library in ANSI C for Empirical Testing of Random Number Generators", ACM Transactions on Mathematical Software, 33: 22